Javaで再帰呼び出しの数を計算する方法は？

Question

Iは、二分木の高さを計算する

int height(Node root) 
{ 
    if (root == null) 
     return 0; 
    else 
    { 
     int lheight = height(root.left); 
     int rheight = height(root.right); 

     if (lheight > rheight) 
      return(lheight+1); 
     else return(rheight+1); 
    } 
} 

を下記の方法を使用していたこれは、最初私は高さに各再帰呼び出し（root.left）で1によってlheightインクリメントと考えlheight = 2返します。しかし、この0 1 0 2 0は、どのようlheightの値は、各再帰呼び出しに変更されて印刷されたprintf文を、私はprintf文を追加して、もう一度それを実行した、

int height(Node root) 
{ 
    if (root == null) 
     return 0; 
    else 
    { 
     int lheight = height(root.left); 
     System.out.print(lheight); 
     int rheight = height(root.right); 

     if (lheight > rheight) 
      return(lheight+1); 
     else return(rheight+1); 
    } 
} 

？私は新しい解決策を探しているわけではありません。私はこれがいろいろなやり方でできることを知っています。私はちょうどこのコードスニペットで何が起こっているのか理解したい。ここにバイナリツリーの画像リンクがあります。 Binary tree

Answer 1

メソッドのパラメータとしてcountを渡します。最初は0または1（設定に応じて）に設定し、メソッドを再帰的に呼び出すたびに増加させます。

EDIT：正直なところ、このコードをテストしていないので、高さの値を変更する方法を理解できません。このような感じは、無限に再帰的になります。

とにかく、ここで追跡再帰回数の基本的な考え方は次のとおりです。

int height(Node root, int lCount, int rCount) 
{ 
    if (root == null){ 
     return 0; 
    } 
    else { 
     int lheight = height(root.left, lCount + 1, rCount); 
     int rheight = height(root.right, lCount, rCount + 1); 

     if (lheight > rheight){ 
      return(lheight); 
     } 
     else return(rheight); 
    } 
} 

あなたは高さ（根、0、0）、非常に最後のLの実行およびR "のメソッド呼び出しを初期化実行「」の「ブランチ」はのそれぞれの合計を得ます。サブツリーと、右側のサブツリーの高さを残したあなたは関数が

int i; //it has to be initialized with 0 


int height(Node root) 
{ 
    if (root == null) 
     return 0; 
    else 
    { 
     i++; 
     int lheight = height(root.left); 
     printf("%d ", lheight); 
     i++; 
     int rheight = height(root.right); 

     if (lheight > rheight) 
      return(lheight); 
     else return(rheight); 
    } 
} 

Answer 2

はそれの高さの最大値です。だからあなたのコードを見れば、それは再帰的に左と右のサブツリーの高さを計算し、最大であるかをチェックしています。あなたが本当にそれを視覚化したい場合。呼び出されたメソッドのツリー構造を作ります。簡単に視覚化することができます。

Answer 3

ツリーの高さは、自分自身を呼び出すことをするたびに増加しているグローバル変数を作成することができます

Answer 4

このような何か - しかし、これは、ツリーの高さの（c /取得する方法である - 私はそれをコンパイルしていないこの

int height = height(root); //this is the height not inside the function 

のような高さの呼び出しを計算するには

int height(Node root) 
{ 
    if (root == null) 
     return 0; 
    else 
    { 
     return 1+ Math.max(height(root.left),height(root.right)); 
    } 
} 

をC++/Javaの/ ..）

Answer 5

例えば

 1 

    / \ 
    2  3 
/\ 
4  5 

0123これを取ります

最初に1は左の[height（root.left）]を渡します.2が呼び出されます.2は左に渡され、4は呼び出されます.4は左を呼び出します。

4は左にないのでヌルまたは0になりますlheight。今度はコードが次のステップ、つまり[height（root.right）]に移動します。

4の右にはnullがあるため、rheightに0が返されます。今すぐ の助けを借りて[リターン（rheight + 1）; ]関数では、値1が関数2の呼び出しに渡されます。

2はlheightを1とします。今度は2がそのrightを呼び出します。ループが続き、2は2つの値l = 1とr = 1を持ち、呼び出しに1 + 1 = 2を返します。機能すなわち1。

1の右が呼び出され、前と同じループで1が返されます。最後に、l = 2、r = 1とする。したがって、私たちの最終的な価値は[lheight + 1] = 3になります。ツリーの高さは3