3

私はAVLツリーの実装に取り​​組んでおり、高さの再計算機能に問題があります。それを呼び出すと、ツリーのルートと値が 1 の変数を渡します。ステップ実行したところ、while ループに到達すると期待どおりに実行されますが、その後は 1 に戻ります。それを見て、私が間違っていることを確認してください。必要に応じてさらにコードを投稿しますが、関数だけで十分な情報が得られると思います。ありがとう

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 に答える