4

ポストオーダーのリストのみが提供されている場合、ツリーのプレオーダーのリストを見つけるにはどうすればよいですか。また、ツリーでは、すべての非リーフ ノードに 2 つの子があります (つまり、各ノードには 2 つまたはゼロの子があります)。

EDIT：別の仮定は、各ノードのラベルが一意であり、それを内部ノードまたはリーフとして識別するフィールドがあるということです。単一の事前注文または事後注文でツリーを一意に識別できるという曖昧さを取り除く必要があると思います。

4

3 に答える 3

7

ツリー内のノードに内部またはリーフとして識別されるフィールドがあると仮定しないと、質問に対する一意の答えを見つけることはできません。一意のツリーを見つけるには、その仮定または順序リストが利用可能でなければなりません。この場合、考えられる答えを 1 つ見つけるために、以下に示す形式のツリーを作成して、特定のポストオーダー リストに一致させることができます (ポストオーダー リストが 1 2 3 4 5 6 7 8 9 であると仮定します)。

9[7[5[3[1,2],4],6],8]

これで、このツリーを使用して予約注文リストを作成できます。

ツリーのノードに内部またはリーフとして識別されるフィールドがあると仮定すると、このアルゴリズムを使用して、この種のツリーのポストオーダー リストから一意のツリーを作成できます。

  1. postorder リストの先頭からスイープし、最初の内部ノードを見つけます。このノードには、postorder リストでこのノードの前にあるちょうど 2 つのリーフの子があります。
  2. ツリー構造にその内部ノードを追加し、リスト内の先行する 2 つのノードをその子にします。
  3. それらの 2 つの子をリストから削除し、その内部ノードをリーフにします。
  4. ステップ 1 に進み、リストが空になるまで繰り返します。
于 2009-08-02T21:40:27.253 に答える
1

preorder トラバーサルの再帰的な構造を考えてみましょう:

T(r) = [r, T(r->left), T(r->right)]
where T(r) is the preorder traversal of tree rooted at node r

次に、T(r) によって記述されるツリーのルートは、常にトラバーサルの最初のノードであることがわかります。

このことと、ルートは常にツリー内でそのサブツリーよりも高い位置にあることを知っているので、この情報を使用してツリーを再構築する方法を考えてみてください。再帰的に考えてください。

警告: これは、これが のようなノードを制約する二分探索木left-child < root < right-childである場合にのみ実行できます。一般に、ツリーは 1 回のトラバーサルから再構築することはできません。詳細な説明については、この優れたリソースを参照してください。

0 または 2 人の子に関するルールに関係なく、あいまいさは依然として存在します。

    4
   / \
  2   5
 / \ / \
 1 3 6 7

    4
   / \
  2   7
 / \
1   3
   / \
  5   6

両方とも予約順トラバーサル [4 2 1 3 5 6 7] を持っています。

于 2009-08-02T21:31:11.987 に答える
1

例: ポストオーダー フォームをプリオーダー フォームに変換する必要があります。これは次の方法で行うことができます。ポスト オーダー: DEBFCA プリオーダー: ABDECF A がルートであることがわかります。予約注文から、ノード B は A に残されていると判断できます。したがって、(BED) (CF) である 2 つのサブクラスを作成します。B をトラバースすると、それをルートとして取得し、B の後に D が存在することがわかります。 、これは、D が B の左にあり、E が B の右にあることを意味します。次に、C をトラバースします。それを根として取ります。次に、F は C の後に存在するため、左と見なされます。

于 2014-03-12T06:05:45.733 に答える