c++ - 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 似乎在本地交换，但它并不反射(reflect)其余代码的变化。给我一个无限循环。

Answer 1

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

更改 if (n == NULL) block 的第一行

AVLNode *n = new AVLNode;

到

n = new AVLNode;

关于更新:在您的旋转函数中，n 是一个局部(自动)变量，更改它不会影响函数外部的任何内容。您需要通过引用传递指针，或返回新的指针值(就像您在 insert() 中所做的那样)。