1

二分探索木の構築に取り組んでおり、各ノードの高さを記録して合計する関数を作成したいと考えています。再帰を使用しようとしています。

私にとって難しいのは、各ノードに高さを割り当ててから、戻って合計することです。1回のパスで高さを割り当てて記録できない限り? 前もって感謝します。

編集：将来これを見る人にとって何がうまくいったかを示す最終的なコード。助けてくれてありがとう。

BST.h

    int totalheight(node);
    int getHeight(node);

    class BST {
    Node root;
    public:
       BST { root = NULL; }
       int totalheight()
       { return ::totalheight(root);
    };


BST.cpp

int totalHeight(BSTNode* node)
{
   if (node == NULL)
      return -1;

   int leftHeight = getheight(node->left);
   int rightHeight = getheight(node->right);
   int totalheight = 1 + leftHeight + rightHeight; // +1 to count the root

   return totalheight;
} 

int getheight(BSTNode* node)
{
   if (node == NULL)
      return 0;

      return 1 + max(getheight(node->left), getheight(node->right)); 
}

main.cpp

    int main() {
       BST tree; // and various inserts

       tree.totalheight();
    } // main
4

1 に答える 1

2

ここに 1 つの問題があります。

int myheight = max(leftheight, rightheight);

そのはず：

int myheight = max(leftheight, rightheight) + 1;

このノードの高さを考慮する必要があります。findHeightまた、再帰するように示されているコードには、getHeight.

全体的な機能は次のとおりです。


int getheight(BSTNode* node)
{
    if (node == null)
        return 0;
    else
        return 1 + max(getHeight(node->left), getHeight(node->right)); 
} // getheight
于 2013-10-11T14:44:04.897 に答える