25

ノードのリストが 2 つある状況を考えてみましょう。一方はあるツリーの前順トラバーサルの表現であり、もう一方は同じツリーの後順トラバーサルの表現です。

これら 2 つのリストからツリーを正確に再構築することは可能だと思います。また、それを行うアルゴリズムがあると思いますが、証明していません。これはマスタープロジェクトの一部になるので、それが可能で正しいことを絶対に確信する必要があります（数学的に証明されています）。しかし、それはプロジェクトの焦点では​​ないので、証明のために引用できる情報源 (紙や本など) があるかどうか疑問に思っていました。(たぶんTAOCPで? セクションを知っている人はいますか?)

要するに、引用可能なリソースで、事前および事後のトラバーサルからツリーを再構築する実証済みのアルゴリズムが必要です。

注: 問題のツリーは、おそらく 2 進法でもバランスの取れたものでもなく、簡単になりすぎるものでもありません。

注 2: 事前注文リストまたは事後注文リストのみを使用する方がよいでしょうが、それは可能ではないと思います。

注 3: ノードは、任意の数の子を持つことができます。

注 4: 兄弟の順序だけを気にします。子供が一人しかいない場合、左右は関係ありません。

4

7 に答える 7

33

preorder と postorder はツリーを一意に定義しません。

一般に、単一のツリー トラバーサルでは、ツリーの構造が一意に定義されません。たとえば、これまで見てきたように、次の 2 つのツリーについて、順不同のトラバーサルは [1,2,3,4,5,6] を生成します。

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

同じあいまいさが、前順と後順のトラバーサルに存在します。上記の最初のツリーの事前順序トラバーサルは [4,2,1,3,5,6] です。これは、同じ事前注文トラバーサルを持つ別のツリーです。

    4
   / \
  2   1
     / \
    3   6
     \
      5

同様に、後順トラバーサル [1,3,2,6,5,4] が上記の最初の木と一致する別の木を簡単に構築できます。

于 2009-07-16T11:54:15.340 に答える
9

ツリーの深さがわからないため、リストを 1 つだけ使用することはできません。したがって、間違いなく 2 つ以上のリストが必要です。

これが私の解決策の試みです：

データの順序を知る手段として、事前順序トラバーサルを使用します。最初のノードが最上位であり、トラバーサルのさらに左側にあるデータがツリーの左側に属していることがわかっているため、これは理にかなっています。

ポスト オーダー トラバーサルは、ツリーの深さを決定できます。たとえば、次のような構造があるとします。

      1
  2   5   6
 3 4  7

Where 2 is the parent of 3 and 4, and 5 is the parent of 7.

Preorder: 1 2 3 4 5 7 6
Postorder: 3 4 2 7 5 6 1

1 から開始することがわかっています。これは、先行順序トラバーサルの最初のノードであるためです。次に、次の番号 2 を確認します。ポスト オーダーでは、番号 2 がノード 1 の前にあるため、2 は 1 の子である必要があることがわかります。次に、3 を確認します。3 は 2 の前にあるため、3 です。は 2 の子です。4 は 2 の前ですが 3 の後であるため、4 は 2 の子ですが、3 の子ではないことがわかります。

現在、ノードが一意でない場合、これは機能しない可能性がありますが、少なくとも解決策への出発点です。

編集:子の順序は、このソリューションで保持されます。単純に、事前順序トラバーサルを介してノードの順序を知り、事後順序トラバーサルを介して構造を知るためです。

Edit2:証拠はここにあります: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel2%2F215%2F626%2F00017225.pdf%3Farnumber% 3D17225&authDecision=-203

ドキュメントを購入する必要があると思いますが...

解決策として提示された書面による証拠を次に示します。

http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf

于 2009-07-16T11:54:47.943 に答える
4

任意のツリーTを4つ（A、B、C、D）と見なします。ここで、Aはルートノード、Bは最初の子のルートノード、CはBの空でない子のベクトル、Dはは、Bの空でない兄弟のベクトルです。CとDの要素は、それ自体がツリーです。

A、B、C、およびDのいずれかが空である可能性があります。Bが空の場合、 CとDも空である必要があります。Aの場合、すべて。

ノードは一意であるため、CとD内の任意の場所に含まれるノードのセットは互いに素であり、AとBのどちらも含まれていません。

関数pre（）およびpost（）は、次の形式の順序付けられたシーケンスを生成します。

pre（T） = [A、B、pre（C）、pre（D） ]

post（T） = [ post（C）、B、post（D）、A]

ここで、ベクトルに適用される関数は、関数を各要素に順番に適用した結果のシーケンスの連結として定義されます。

次に、ケースを検討します。

  • Aが空の場合、両方の関数の出力は空のシーケンスです[]
  • Bが空の場合、両方の関数の出力は[A]だけです。
  • CとDが空の場合、pre （T） = [A、B]および post（T） = [B、A]
  • Cだけが空の場合、pre（T） = [A、B、D' ]およびpost（T） = [B、D''、A]（素数はD内に含まれるノードの順列を示します）
  • Dだけが空の場合、pre（T） = [A、B、C' ]およびpost（T） = [ C''、B、A]
  • 空の値がない場合、pre（T） = [A、B、C'、D' ]およびpost（T） = [ C''、B、D''、A]

すべての場合において、区切り文字としてAとB（存在する場合）を使用することにより、2つの出力シーケンスのメンバーを適切なサブシーケンスに明確に分割できます。

問題は、ベクトルシーケンスを分割することもできるかということです。可能であれば、それぞれを再帰的に処理して完了です。

pre（）の結果は常にAノードで始まるシーケンスのチェーンになり、 post（）の結果は常にAノードで終わるシーケンスのチェーンになるため、 Aノードがあれば実際にそれらを分割できます。空になることはありません。

これは、独立して空である可能性のある固定された子を持つバイナリ（または実際には任意の）ツリーの場合にプロセスが失敗する場所です。ただし、この場合、空でないノードのみを含むようにCとDを定義しているため、再構築が機能することが保証されます。

とにかく、そう思います。明らかに、これは単なる議論であり、正式な証明ではありません。

于 2010-04-22T18:43:09.330 に答える
1

このノードには子が 1 つしかない (右または左、違いはありません) 少なくとも 1 つのノードを持つ、この制限を持つバイナリ ツリーを作成します。

次に、Preorder リストと Postorder リストを作成します。次に、これらのリストからツリーを再構築してみてください。そして、そのノードでは、その子が右か左かを判断できないことに気付きます。

于 2011-12-30T08:25:09.700 に答える
1

ノードに一意の名前が付けられていると仮定すると、ツリーを再構築するには、事前順序および事後順序のトラバーサルで十分です。そのためのアルゴリズムを作成するための鍵は、それを理解することです。

X は、先行順序で X が Y に先行し、後続順序で Y の後にある場合に Y の祖先です。

これにより、任意のノードのすべての子孫をいつでも見つけることができます。X の子孫は、常に先行順序で X の直後に続き、後続順序で X より先行します。したがって、X をルートとするサブツリーの作成に関心があることがわかったら、X をルートとするサブツリーの前順トラバーサルと後順トラバーサルを抽出できます。X の直後のノードがそれが子孫である場合、その左端の子。

スタックベースの実装もあり、事前注文ノードを反復処理し、次の事前注文ノードの直接の親になる候補であるすべてのノードをスタックに保持します。事前注文ノードごとに、次の事前注文ノードの親ではないすべてのノードをスタックから繰り返しポップします。そのノードをスタックの最上位ノードの子にし、その子をスタックにプッシュします。

于 2013-10-09T20:28:03.993 に答える
0

preorder および postorder トラバーサルから一般的な Binary Tree を構築することはできません (これを参照してください)。しかし、Binary Tree が Full であることがわかっていれば、あいまいさなしにツリーを構築できます。次の例の助けを借りてこれを理解しましょう。

与えられた 2 つの配列を pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7} および post[] = {8, 9, 4, 5, 2, 6, 7 と考えてみましょう。 、3、1}; pre[] では、一番左の要素がツリーのルートです。ツリーがいっぱいで、配列サイズが 1 より大きいため、pre[] の 1 の次の値は、ルートの子のままにする必要があります。したがって、1 がルートで、2 が左の子であることがわかります。左サブツリーのすべてのノードを見つける方法は? 2 が左サブツリーのすべてのノードのルートであることがわかっています。post[] の 2 より前のすべてのノードは、左側のサブツリーにある必要があります。これで、1 がルートであり、要素 {8, 9, 4, 5, 2} が左側のサブツリーにあり、要素 {6, 7, 3} が右側のサブツリーにあることがわかります。

              1
            /   \
           /      \
 {8, 9, 4, 5, 2}     {6, 7, 3}

上記のアプローチを再帰的にたどり、次のツリーを取得します。

      1
    /   \
  2       3
/  \     /  \

4 5 6 7 / \
8 9

于 2015-04-10T05:09:48.457 に答える