0

下面的代码让我很困惑。

班级

class AVLTree {
   private:
struct AVLNode
{
    AVLNode *leftchild;
    AVLNode *rightchild;
    int data;
    int height;
};

AVLNode *root;

public:

AVLTree()
{
    root = NULL;
}

bool isEmpty() const { return root == NULL; }
void print();
void inorder(AVLNode *n, int l);
void insert(int d);
void rotateLeft(AVLNode* n);
void rotateRight(AVLNode* n);
void rotateLeftTwice(AVLNode* n);
void rotateRightTwice(AVLNode* n);
AVLTree::AVLNode* insert(int d, AVLNode* n);
int max( int a, int b);
int height( AVLNode* n); };

插入功能。

  AVLTree::AVLNode* AVLTree::insert(int d,AVLNode *n){
    if (n == NULL)
    {
        AVLNode *n = new AVLNode;
        n->data = d;
        n->leftchild = NULL;
        n->rightchild = NULL;
        n->height = 0;
    } else if( d < n->data) {
        n->leftchild = insert(d,n->leftchild);

    } else if (d > n->data) {
        n->rightchild = insert(d,n->rightchild);
    }
    else {      
        n->height = max(height(n->leftchild), height(n->rightchild));
        return n;
         }
        -----> This section of the code gives be "EXC_BAD_ACCESS".
    n->height = max(height(n->leftchild), height(n->rightchild));
       return n;
}

这是高度函数。

int AVLTree::height(AVLNode* node)
{   cout << "HEIGHT"; 
    if(node == NULL)
    {
        return -1;
    }
    else {
        return node->height;
    }
}

有谁知道为什么？

=== 更新：

旋转时

 void AVLTree::rotateLeft(AVLNode* n)
    {
            AVLNode *child = n->leftchild;
            n->leftchild = child->rightchild;
            child->rightchild = n;

            n->height = max(height(n->leftchild),height(n->rightchild))+1;
            child->height = max(height(child->leftchild),height(child->rightchild))+1;
            n = child;
}

它似乎没有按应有的方式交换值。虽然 n = child 似乎在本地交换，但它并未反映其余代码的更改。给我一个无限循环。

4

1 回答 1

2

如果n在进入函数时为 null，则该行将尝试取消引用它，并给出错误。您分配新节点的代码应该将其分配给它n自己，而不是一个具有相同名称的单独变量来隐藏函数参数。

将块的第一行if (n == NULL)从

AVLNode *n = new AVLNode;

到

n = new AVLNode;

关于更新：在您的旋转函数中，n是一个本地（自动）变量，并且更改不会影响函数之外的任何内容。您将需要通过引用传递指针，或者返回新的指针值（就像您在 中所做的那样insert()）。

于 2011-03-05T21:39:30.923 回答