3

我正在研究 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
    }
}
4

1 回答 1

2

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

在您的实现中，您使用一个名为count传递参数的值到递归调用。考虑到我们需要从子节点检索计数，而不是向它们传递一个计数，该值的目的是什么？

如果你：

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

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

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返回它计算的高度来替换它。

于 2013-04-09T09:26:21.330 回答