C++ AVL树重新计算高度

Question

我正在研究 AVL 树的实现，我的重新计算高度函数有问题。当我调用它时，我传入了树的根和一个值为 1 的变量。我单步执行它，发现一旦它到达 while 循环，它就会按预期执行，但之后它会返回到只有一个。你能看看它，看看我做错了什么吗？如果需要，我会发布更多代码，但我认为仅此功能就能为您提供足够的信息。谢谢

void BinaryTree::recalculate(Node *leaf, int count)
{
    if(leaf == NULL)//if we are at the root
    {
        return;//exit the function
    }

     if((leaf->getLeft() != NULL))//if we are not at the end of the subtree
    {
        recalculate(leaf->getLeft(), count);//advance to the next node and re-enter the function

    }

     if(leaf->getRight() != NULL)//if we are not at the end of the right subtree
    {
        recalculate(leaf->getRight(), count);//advance to the next node and re-enter the program
    }

    else
    {
        while(leaf->getParent() != NULL)//calculate each subtree until we are at the root
        {
            leaf = leaf->getParent();//get the parent node
                count++;//increment the height          

            if(leaf->getLeft() != NULL)//if there is an item in the left
            {

                leaf->getLeft()->setHeight(count-1);//sets the hight of the left child
            }

             if(leaf->getRight() != NULL)//if there is an item in the right
            {
             leaf->getRight()->setHeight(count -1);//sets the height of the right child

            }
        }

        return;//exit the function
    }
}

Answer 1

您的函数应该计算二叉树的每个子树的高度，并将该值保存在该子树的根节点中。您选择遵循递归方法，这是标准方法。在这种方法中，必须先计算左右子树的高度，然后取两者中最高的作为当前节点。

在您的实现中，您使用名为 count 的值作为参数传递给递归调用。如果我们需要从子节点检索一个计数，而不是将一个传递给它们，那么该值的用途是什么？

如果你:

• 从重新计算参数中删除该值
• 如果适用，让重新计算方法首先在两个 child 上调用自己
• 使重新计算从每个子节点高度更新当前节点高度

你应该让它工作。以下是基于该算法的可能实现:

void BinaryTree::recalculate(Node *leaf) {
     int count = 0;
    if (leaf == NULL)  {
        return;
    }
    if (leaf->getLeft() == NULL && leaf->getRight() == NULL) {
        // no child, the height is 0
        setHeight(0);
        return;
    }
    if (leaf->getLeft() != NULL) {
        recalculate(leaf->getLeft());
        count = leaf->getLeft()->getHeight();
    }
    if (leaf->getRight() != NULL){
        recalculate(leaf->getRight());
        count = max(count, leaf->getRight()->getHeight());
    }
    // include leaf in the height
    setHeight(count+1);
}

如果不能使用 getHeight 方法，您可以通过让 recalculate 返回它计算的高度来替换它。