0

我一直在尝试在 C++ 中实现 AVL 树，并且我相信我已经正确地编写了除一行之外的所有内容。该程序的结构如下。

    struct AvlNode
{
    int key;
    int height;
    AvlNode *left;
    AvlNode *right;
    AvlNode(int key1, int height1 = 0, AvlNode *left1 = NULL, AvlNode *right1 = NULL)
    {
        key = key1;
        height = height1;
        left = left1;
        right = right1;
    }
};

class AvlTree
{
private:
    AvlNode * root;
    void destroySubTree(AvlNode * v);//destroy a subtree rooted at v
    void displayPreOrder(AvlNode *);//pre-order traversal
    void displayInOrder(AvlNode *);//in-order traversal
    void displayPostOrder(AvlNode *);//post-order traversal
    void remove(AvlNode * &, int);//remove
    void insert(AvlNode * &, int);//insert
    void balance(AvlNode * &); //make the tree balanced after each insert/remove
    void rightRotate(AvlNode * &);//right rotation
    void leftRotate(AvlNode * &);//left rotation
    void doubleLeftRightRotate(AvlNode * &);//left right double rotation
    void doubleRightLeftRotate(AvlNode * &);//right left double rotation

public:
    AvlTree() { root = NULL; }
    ~AvlTree() { destroySubTree(root); }
    AvlNode * search(int);
    void displayPreOrder() { displayPreOrder(root); }
    void displayInOrder() { displayInOrder(root); }
    void displayPostOrder() { displayPostOrder(root); }
    void insert(int x) { insert(root, x); }//insert a new key x
    void remove(int x) { remove(root, x); }//remove a key x
    int getHeight(AvlNode * v);//return the height of node v
    int getTreeHeight() { return getHeight(root); }//return the height of the tree
    int getRoot() { return root->key; }//return the root
    int max(int x, int y);
};

所以我遇到的问题出现在 balance 方法中，如下所示：

void AvlTree::balance(AvlNode * & v)
{
    if (v == NULL)
    {
        return;
    }
    if ((getHeight(v->left) - getHeight(v->right)) > 1)
    {
        if (getHeight(v->left->left) >= getHeight(v->left->right))
            rightRotate(v);
        else
            doubleLeftRightRotate(v);
    }
    if ((getHeight(v->right) - getHeight(v->left)) > 1)
    {
        if (getHeight(v->right->left) >= getHeight(v->right->right))
            doubleRightLeftRotate(v);
        else
            leftRotate(v);
    }
    v->height = 1 + max(getHeight(v->left), getHeight(v->right));
}

该方法的最后一行是编译器吓坏我的地方。当我运行程序时，Visual Studio 说 source.exe 已停止工作。那是因为我不能像我尝试的那样直接分配节点的高度吗？如果没有，这里有什么可能解决这个问题？我尝试了许多不同的方法来设置平衡后节点的高度，但它根本不允许这样做。我在这里先向您的帮助表示感谢！

当我在调试器中运行程序时，它停在 rightRotate 方法的第一行：如下：

void AvlTree::rightRotate(AvlNode * & k2)
{
    AvlNode * k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = 1 + max(getHeight(k2->left), getHeight(k2->right));
    k1->height = 1 + max(getHeight(k1->left), k2->height);
    k2 = k1;
}
4

0 回答 0