AVL 树奇怪的行为

Question

下面的代码让我非常困惑。

类

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 似乎在本地交换，但它并不反映代码其余部分的更改。给我一个无限循环。

Answer 1

如果 n 在进入函数时为 null，则该行将尝试取消引用它，从而给出错误。分配新节点的代码应该将其分配给 n 本身，而不是一个与函数参数同名的单独变量。

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

AVLNode *n = new AVLNode;

为

n = new AVLNode;

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