2

このmaxDepthコードを理解するのに問題があります。どんな助けでもいただければ幸いです。これが私が従ったスニペットの例です。

int maxDepth(Node *&temp)
{
  if(temp == NULL)
  return 0;

 else
{
 int lchild = maxDepth(temp->left);
 int rchild = maxDepth(temp->right);

 if(lchild <= rchild)
 return rchild+1;

 else
  return lchild+1;

 }

}

基本的に、私が理解しているのは、関数が最後のノードに到達するまで、関数が（左右のケースごとに）再帰的に自分自身を呼び出すということです。一度実行すると、0を返し、次に0+1を実行します。その場合、前のノードは1+1です。次は2+1です。左の子が3つあるbstがある場合、int lchildは3を返し、余分な+1がルートになります。だから私の質問は、これらすべての+1はどこから来るのかということです。最後のノードで0を返しますが、左右の子ノードを上るときに0+1などを返すのはなぜですか。理由がわかりません。私はそれがそれをすることを知っています、しかしなぜですか？

4

8 に答える 8

8

（より大きな木の）この部分を考えてみましょう：

       A
        \
         B

ここで、このツリーパーツの深さを計算したいので、ポインタをAそのパラメータとして渡します。

明らかに、へのポインタAはではないNULLので、コードは次のことを行う必要があります。

  • maxDepthそれぞれAの子（左と右のブランチ）を呼び出します。A->rightですがB、A->left明らかにですNULL（A左のブランチがないため）

  • これらを比較し、最大の値を選択してください

  • この選択した値+1を返します（Aそれ自体がレベルを取るので、そうではありませんか？）

maxDepth(NULL)次に、とmaxDepth(B)の計算方法を見ていきます。

前者は非常に簡単です。最初のチェックでmaxDepth0が返されます。他の子もそうである場合NULL、両方の深さは（0）に等しくなり、Aそれ自体に対して0+1を返す必要があります。

しかしB、空ではありません。ただし、ブランチがないため、（気付いたように）その深さは1です（NULL両方の部分のsの最大値0 +Bそれ自体の1）。

では、に戻りましょうA。maxDepth左側のブランチ（NULL）は0、maxDepth右側のブランチは1です。これらの最大値は1であり、Aそれ自体に1を追加する必要があります。つまり2になります。

A重要なのは、が大きなツリーの一部にすぎない場合と同じ手順を実行することです。この計算の結果（2）は、より高いレベルのmaxDepth呼び出しで使用されます。

于 2012-10-22T16:47:02.790 に答える
5

深さは前のノード+1を使用して計算されています

于 2012-10-22T16:54:41.607 に答える
4

すべてのものは、コードのこの部分から来ています：

if(lchild <= rchild)
    return rchild + 1;
else
    return lchild + 1;

+1あなたは木の葉で得られた結果に自分自身を追加します。これらは、関数のすべての再帰呼び出しを終了してルートノードに到達するまで加算され続けます。

于 2012-10-22T16:34:03.383 に答える
2

深さは前のノード+1で計算されるため

于 2012-10-22T16:34:14.937 に答える
2

二分木では、ノードには最大2つの子（左と右）があることを覚えておいてください。

これは再帰的なアルゴリズムであるため、何度も何度も呼び出します。

temp（監視対象のノード）がnullの場合、このノードは何もないのでカウントされないため、0を返します。それが基本ケースです。

調べているノードがnullでない場合は、子が存在する可能性があります。したがって、左側のサブツリー（および現在のノードのレベルに1を加算）と右側のサブツリー（および現在のノードのレベルに1を加算）の最大深度を取得します。次に、2つを比較し、2つのうち大きい方を返します。

2つのサブツリー（temp->leftとtemp->right）に飛び込み、子のないノードに到達するまで操作を繰り返します。その時点で、左右でmaxDepthを呼び出します。これは、nullで0を返し、その後、呼び出しのチェーンに戻って戻り始めます。

したがって、3つのノードのチェーン（たとえば、root-left1-left2）がある場合、それはleft2に到達し、maxDepth（左）とmaxDepth（右）を呼び出します。それらのそれぞれは0を返します（それらはnullです）。その後、left2に戻ります。比較すると、両方とも0であるため、2つのうち大きい方はもちろん0です。0+1を返します。次に、left1にいます-繰り返し、1が左n右の大きい方であることがわかり（おそらく同じであるか、右の子がない）、1+1を返します。今、私たちはルートにいます、同じことです、それは深さである2 + 1=3を返します。

于 2012-10-22T16:38:02.333 に答える
0

二分木の最大深度を見つけるには、左に進み、ツリーをトラベレスします。基本的に、DFS
を実行する か、3つの異なる再帰的な方法で二分探索木の深さを見つけることができます。

– using instance variables to record current depth and total depth at every level
– without using instance variables in top-bottom approach
– without using instance variables in bottom-up approach
于 2013-07-13T19:15:33.363 に答える
0

コードスニペットは次のように減らすことができます。

int maxDepth(Node *root){
    if(root){ return 1 + max( maxDepth(root->left), maxDepth(root->right)); }
    return 0;
}

このコードを見る良い方法は、上から下へです。

BSTにノードがない場合はどうなりますか？がroot = NULLあり、関数はすぐに予想される深さを返し0ます。

ここで、ツリーにいくつかのノードが配置されているとします。上から順に、ルートノードのif条件になります。true次に、これらのサブツリーのルートをに渡すことにより、LEFTSUBTREEとRIGHTSUBTREEの最大深度を尋ねますmaxDepth。ルートのLSTとRSTはどちらもルートよりも1レベル深いため、関数に渡されるツリーのツリーの 深さを取得するには、1つ追加する必要があります。root

于 2015-09-09T00:10:43.260 に答える
0

これが正しい答えだと思います

int maxDepth(Node *root){
    if(root){ return 1 + max( maxDepth(root->left), maxDepth(root->right)); }
    return -1;
}
于 2019-07-04T05:59:33.237 に答える