0

各ノードがリーフノードまたは内部ノードのいずれかにラベル付けされている完全な二分木のプレオーダートラバーサルを考えると、ツリーの高さを見つけるための優れたアルゴリズムはありますか？たとえば、Nが内部ノードを表し、Lがリーフを表す場合、プレオーダートラバースNLNNLLLが与えられると、高さは3になります。

4

1 に答える 1

1

よし、マルティをコメント欄に残しておくのは残念だ。彼は本当にどこから始めればいいのか分からず、少なくとも問題について考えていることを証明したと思います。

完全な二分木について何がわかっていますか? 各ノードはリーフであるか、2 つの子を持ちます。

preorder トラバーサルは、ルート、左のサブツリー、次に右のサブツリーを再帰的に訪問します。

次の質問について考えてみてください: (完全なバイナリ ツリーの) プレオーダー トラバーサルのどの時点で、サブツリーを使い果たしたことがわかりますか? その根を訪れ、次に 2 つの葉 (葉の場合は根だけ) を調べます。

特別な構造のスタックを作りましょう:

struct StackNode{
   size_t count; //initialize to 0
   char nodeType; //'N' or 'L'
};

この「StackNode」オブジェクトは、「nodeType」変数を使用して事前注文トラバーサルでアクセスしたノードのタイプを追跡しますが、これは明らかです。また、0 に初期化する特別なカウンター「count」もあります。

ソリューションの背後にあるアイデアは次のとおりです。

  • 「N」に遭遇するたびに、StackNode を作成し、それをスタックにプッシュします。
  • 「L」に遭遇するたびに、StackNode を作成し、スタックにプッシュします
  • スタックに最後にプッシュしたノードが「L」の場合、最後のノードをポップしてから、stack.top() のカウントを 1 増やします。
  • stack.top() のカウントが 2 の場合、スタックからトップをポップし、stack.top() のカウントを 1 増やします (スタックが空になるか、スタックからのポップが停止するまで繰り返します)

ノードをスタックにプッシュするたびに、ツリーの現在の高さを確認できます。これは、スタック 1 内のアイテムの数です (最下部のアイテムがルートであることを考慮して)。

これまでに遭遇した最大の高さを追跡する限り、木の高さがわかります。

あなたの例を見てみましょう：NLNNLLL

スタックは最初は空です。

int maxHeight = -1;

最初の文字を処理する:N

ノードをスタックにプッシュします。

スタック: タイプ数

  • いいえ、0

    最大高さ = 0;

次の文字を処理:L

ノードをスタックにプッシュします。

  • L、0

  • いいえ、0

    最大高さ = 1; //(1ずつインクリメント)

処理された最後の文字は葉だったので、ポップしてインクリメントします:

スタック：

  • N、1

    最大高さ = 1;

次の文字を処理:N

ノードをスタックにプッシュします。

  • いいえ、0

  • N、1

    最大高さ = 1; //変更なし

次の文字を処理:N

ノードをスタックにプッシュします。

  • いいえ、0
  • いいえ、0

  • N、1

    最大高さ = 2; //(1ずつインクリメント)

次の文字を処理:L

ノードをスタックにプッシュします。

  • L、0
  • いいえ、0
  • いいえ、0

  • N、1

    最大高さ = 3; // 1 ずつインクリメント

最後のノードはリーフだったので、ポップしてインクリメント

スタック：

  • N、1
  • いいえ、0

  • N、1

    最大高さ = 3; //変更なし

次の文字を処理:L

ノードをスタックにプッシュします。

  • L、0
  • N、1
  • いいえ、0

  • N、1

    最大高さ = 3; //変更なし

最後のノードはリーフだったので、ポップしてインクリメントします:

  • N、2
  • いいえ、0
  • N、1

最上位ノードのカウントは 2 であるため、ポップしてインクリメントします。

  • N、1
  • N、1

次のノードを処理します:L

ノードをスタックにプッシュします。

  • L、0
  • N、1

  • N、1

    最大高さ = 3; //変更なし

最後のノードはリーフだったので、ポップしてインクリメントします:

  • N、2
  • N、1

最上位ノードのカウントは 2 であるため、ポップしてインクリメントします。

  • N、2

最上位ノードのカウントは 2 であるため、ポップしてインクリメントします。

(empty stack), finished

maxHeight = 3; //the maximum height discovered during a preorder of a full binary tree
于 2013-02-01T05:41:21.133 に答える