1

これらのことを行うためのアルゴリズムを手伝ってくれませんか？preorder、inorder、postorderを実装しており、これらの順序の1つでツリーをトラバースするためのヒントが与えられます。私はノードにラベルを付ける（または「訪問する」）ためにdottyを使用しています。

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

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

これらは通常の木です。

4

2 に答える 2

5

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

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

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

  • 基本ケース：子のないノードの深さはどれくらいですか？
  • 帰納的ケース：すべての子の深さが（異なる可能性があります）あるとすると、現在アクセスしているノードの深さはどれくらいですか？

子孫数を計算する場合：

  • 基本ケース：子のないノードには子孫がいくつありますか？
  • 帰納的ケース：すべての子の子孫数がわかっているとすると、アクセスしている現在のノードの子孫数はいくつですか？

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

于 2010-05-05T03:52:57.723 に答える
1 
depth(tree) = 1+ max(depth(tree.left), depth(tree.right));

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

どちらの場合も、nullポインタに対して0を返すと、再帰が終了します。

于 2010-05-05T03:42:14.543 に答える