プレオーダー、オーダー、ポストオーダートラバーサル

Question

予約注文、ABAB、ポストオーダー：BABA、オーダー：AABB 。

私は、ルートがPreとPostの最初と最後の要素だと理解していますが、バイナリツリーを構築する仕方を理解できません。

Answer 1

あなたの投稿はあいまいであり、あまり意味がありませんが、私は、プレ、ポストオーダー、バイナリツリーの作成について説明します。

あなたの質問が理にかなっていない理由の1つは、注文時に記述した要素に順序を設定していないことです。ABAB BABAとAABBは、各要素がどこに行くのかを適切に示すために、それぞれの要素の文字ですか？なぜ複製するのですか）

あなたの質問が理にかなっていないもう一つの理由は、プレ、ポジションが二分木の作成に関係していると思われることですしないでください。

Pre ordering、In Ordering、およびPost Orderingはtree traversalためDepth First Searchアルゴリズムのすべてのタイプです。つまり、それらはツリーをナビゲートする方法であり、ツリーを作成する方法ではありません。これらのアルゴリズムを使用して要素を検索したり、ツリーのすべての内容を単純に出力したりすることができます。ノードがpointers（array based binary heapのように）にしかリンクされていないツリーに特に便利です。

 A 
    B C 
    D E F G 

プリオーダートラバーサルは、あなたが常に最初に一番左のパスを取るツリートラバーサルアルゴリズムのタイプです。（すべての例で同じ）以下のバイナリツリーを想像してみてあなたが遠くに行くことができないときは、次に左端のパスを取って、次のノードで同じことを再帰的に行います。上の例のツリーでは、プリオーダーのトラバースはルートから始まり、（A）左へ（A、B）は左に、（D）は左に行くことはできませんでした。 A B D E C F G

トラバーサルは、事前注文トラバーサルに似ていますが、各ステップで表示する代わりに、トラバーサルが最も深く左に移動してから表示できるようになります。もう十分に深くなれば、それは元に戻って表示され（したがって '順番に'）、同じことをその行為が完了するまで再帰的に再試行します。ツリーの例では、まず最初にDを印刷し、Bに戻ってBを印刷し、次にEに、Aに戻って戻って最終的な出力をD B E A F G Cにします。注記ウィキペディアの例は、より複雑なので、より理にかなっているかもしれません。

ポストオーダーでは、本質的に、左のサブツリーに最も深いノードを見つけ、そこに最も深いノードを再帰的に印刷して、右のサブツリーに行き、最終的にルートを印刷します。 ：D E B F G C A。この例は、より複雑なツリーを持つため、ウィキペディアの方が意味があります。

ツリーを構築する方法はたくさんありますが、どのような順序構造を必要とするかはまったく異なります。バイナリ構造かn-ary構造を使いたいですか？あなたはどの要素が上にあるか気になりますか、または最小/最大（例えばpairing heapまたはバイナリヒープpriority queueのような）だけを必要としますか？ツリーの各部分のルーツが、子どもまたはその親に対して、より大きく/より小さく/他の条件でなければならないような検索条件がありますか？（binary search treeのような）

This postでも十分ではない場合、適切な接続を持つノードのシーケンスからツリーを構築するために、さまざまなタイプの順序が必要な理由が説明されています元の意図はバイナリツリー構造をコピーすることでした）