0

特定の走査方法 (インオーダー、ポストオーダー、またはプリオーダー) からバイナリ ツリーを見つけるにはどうすればよいですか?

4

4 に答える 4

4

1つのトラバーサル（インオーダー、プレオーダー、またはポストオーダー）だけではこれを行うことはできません。

ツリーのインオーダーおよびプレオーダートラバーサルが指定されている場合は、次のように実行できます。

  1. 事前注文の最初の要素はツリーのルートになります。（Aだとしましょう）
  2. ルートを順番に並べるので、ルートの左側にあるすべてのノードは左側のサブツリーの順番になり、右側のノードは右側のサブツリーの順番になります。ルートの左側にあるノードの数を計算します。たとえばLです。
  3. 2番目のLノードからのポストオーダーでは、左側のサブツリーのプレオーダーになり、その後、右側のサブツリーのプレオーダーになります。

そこで、ルート要素を見つけて、Inorder inを左サブツリーのInorder、右サブツリーのInorderに、Preorderを左サブツリーのpreorderと右サブツリーのpreorderに分割しました。したがって、ノードが1つだけ残るまで、再帰によってこれを行うことができます。

同様に、ルートがポストオーダーの最後の要素となるインオーダーとポストオーダーに対しても実行できます。

于 2009-09-06T16:36:13.390 に答える
3

inorder、post-order、pre-order ツリー トラバーサルに関するウィキペディアの記事は次のとおりです。

http://en.wikipedia.org/wiki/Tree_traversal。

探しているツリーは、検索語に一致するノードから始まります。

于 2009-09-06T16:11:14.687 に答える
2

（わかりました。修正された質問をここに置くことにしたので、私の回答もここに投稿してください）

二分木のポストオーダートラバーサルとインオーダートラバーサルを以下に示しますが、これらのトラバーサルから一意の二分木を取得することは可能ですか？

可能です。

ポストオーダートラバーサル（左-右-ルート）では、ツリー全体のルートノードが常に最後になります（あなたの場合はAです）。インオーダートラバーサル（左-ルート-右）では、ルートの前のノードは左側のサブツリーに属し、ルートの後のノードは右側のサブツリーに属します。すでにルートを決定しているので、左側のサブツリーと右側のサブツリーのノードを決定できます。

それを決定すると、ポストオーダーリストで左右のサブツリーを分離することができます。これで、左右のサブツリーとルートノードを決定しました。

postorder: left|right|root
inorder  : left|root|right

ここで、左右のサブツリーを再帰的に作成する必要があります。フィン。

于 2009-09-06T16:42:24.690 に答える
1

トラバーサルの結果を使用して元のツリーを復元したい場合は、悪いニュースがあります。明確な解決策はありません。同じトラバーサル結果を生成できるツリーがいくつかあります。

たとえば、次のツリーを順番にトラバーサルすると、同じ結果が得られます。1, 2, 3

    2           3       1
   / \         /         \
  1   3       2           2
             /             \
            1               3
于 2009-09-06T16:27:52.597 に答える