関数から何も返さずにBSTの高さを見つける

Question

私はさまざまなデータ構造を学習しようとしています。現在、バイナリ検索ツリーという木について学習しています。 get height関数を除いて、ほとんどすべての関数をダウンさせました。私はこれを再帰的に書く方法と、高さを見つけるために再帰的なパスを返す方法に関するかなりの擬似コードを発見しました。これは結構ですが、私は、私は私の他の機能を書いたかと一致滞在したかった

int getHeight(struct node* node) 
{ 
if (node == nullptr) 
    return 0; 
else 
{ 
    int leftDepth = getHeight(node->left); 
    int rightDepth = getHeight(node->right); 

    if (leftDepth > rightDepth) 
     return(leftDepth+1); 
    else return(rightDepth+1); 
} 
} 

：これは私が思いついたものです。その他の関数はテンプレートであり、それぞれがドライバーで呼び出されるpublicラッパー関数を持っています。次に、このラッパーは、意図したアクションを実際に実行するプライベート関数を呼び出します。だから、私はGETの高さを持っていることはこれです：

template <typename T> 
int binarySearch<T>::getHeight() 
{ 
    int height = 0; 
    getHeight(rootNode, height, 0); 
    return height; 
} 

    template <typename T> 
    void binarySearch<T>::getHeight(Node *node, int &max, int layer) 
    { 
     int tempRight = 0; 
     int tempLeft = 0; 

     if (node == nullptr) 
     { 
      tempRight = -1; 
      tempLeft = -1; 
      max--; 
     } 
     else 
     { 

      if (node->left != nullptr) 
      { 
       tempLeft = 1; 
       getHeight(node->left, max, layer); 
      } 

      if (node->right != nullptr) 
      { 
       tempRight = 1; 
       getHeight(node->right, max, layer); 
      } 

     } 
     if (tempLeft > tempRight) 
     { 
      max++; 
     } 
     else 
     { 
      max++; 
     } 
    } 

私は、深さ優先探索に似た何かをするという点で、私は層のカウンタをインクリメントだろう、私は同じ日午前かどうかをテストするためのものレイヤー、そしてもしあれば、最大カウンターを一度インクリメントするだけです。再帰的な高さの論理的な流れについてはちょっと混乱しているので、私の実装はほとんど意味をなさない。誰かが、高さの再帰関数を取得することの内訳に関する情報を正しい方向に向けることができますか？ありがとう！

Answer 1

私はあなたが達成したいのか、本当にわからないんだけど、ここでのショットです：

void getHeight(struct node* node, int &max, int layer) { 
    if (!node) return; 

    if (layer>max) { 
     max = layer; 
    } 

    getHeight(node->left, max, layer+1); 
    getHeight(node->right, max, layer+1); 
} 

あなたはgetHeightを呼び出す前に0にmaxを初期化する必要がありますが。