0

次のコードの動作を説明してください。私は再帰を得ることができません。

int depth(struct tree *q)
{ 
    int h1,h2;
    if(q==NULL)
       return 0;
    else
    {
       h1=depth(q->left);
       h2=depth(q->right);
    }
    return (max(h1,h2) +1 );
}

上記のコードで再帰はどのように機能しますか? h1 と h2 はどのように値を取得しますか?

4

1 に答える 1

4

ノードが3つ、ルートが1つ、子が2つしかない単純なツリーを想像してみてください。

      Node R
     /      \
    /        \
Node A      Node B

深さへの最初の呼び出しは、ノードRを引数として取ります。

呼び出し1）qはNULLそうではありませんdepth()ノードR左==ノードAに対して呼び出されます

呼び出し2）qはNULLそうではありませんdepth()ノードAに対して呼び出されます左==NULL

呼び出し3）qはNULL0を返します。

呼び出し2）h1 = 0; ノードAを呼び出しますright = NULL

4）を呼び出すと、0qがNULL返されます。

電話2）h1 = 0; h2 = 0; return max(0, 0) + 1

呼び出し1）h1 = 1; ノードR右=ノードBを呼び出します

呼び出し5）qはNULLそうではありませんdepth()ノードBに対して呼び出されます左== NULL

6）を呼び出すと、0qがNULL返されます。

呼び出し5）h1 = 0; ノードBを呼び出しますright = NULL

呼び出し7）qはNULL0を返します。

5）に電話するh1 = 0; h2 = 0; return max(0, 0) + 1;

電話1）h1 = 1; h2 = 1; return max(1, 1) + 1;

2を返します。

于 2012-08-01T10:59:34.037 に答える