木の深さと子孫の計算

Question

これらのことをするためのアルゴリズムを手伝ってもらえますか？私は予約注文、Inorder、およびPostorderが実装されており、これらの注文のいずれかでツリーを横断するヒントが与えられています。 Dottyを使用してノードにラベルを付けます（または「訪問」します）。

深さは、根から底の葉までのエッジの数なので、私が移動するたびに+1を深さに追加しますか？そんな感じ？

子孫のアルゴリズムについては知りません。彼らは、特定のノードがそれ自体の下に持っているノードの数について尋ねています。

これらは通常の木です。

Answer 1

depth(tree) = 1+ max(depth(tree.left), depth(tree.right));

descendants(tree) = descendants(tree.left) + descendants(tree.right);

どちらの場合も、ヌルポインターのために0を返すと再帰が終了します。

Answer 2

これは宿題の質問ですか？私の答えは、それが宿題のためであると仮定しています。

木は再帰的なデータ構造であるため、それらを動作させるアルゴリズムはしばしば再帰的です。再帰アルゴリズムには、基本ケースと帰納的ケースが必要です。ツリーの場合、ベースケースは、リーフノード（つまり、子供のないノード）にアクセスしているときに行うことです。帰納的ケースは、内部ノードにアクセスしているときに行うことです（つまり、少なくとも1人の子供を持つノード）。

深さ（またはツリーの「高さ」）を計算するには：

• 基本ケース：子供のいないノードの深さはどれくらいですか？
• 帰納的ケース：すべての子供の深さがあることを考えると（これは違う可能性があります）、訪問している現在のノードの深さはどれくらいですか？

子孫数を計算するために：

• 基本ケース：子供のいないノードには何人の子孫がいますか？
• 帰納的ケース：あなたのすべての子供の子孫数を知っていることを考えると、あなたが訪問している現在のノードの子孫数は何ですか？

明確な質問をすることをお勧めします。