2

二分木の勉強を始めたばかりです。Inorder と Postorder OR Inorder と Preorder を指定して、バイナリ ツリー構造を見つけるアルゴリズムはありますか? 私は手動でそれをやろうとしてきましたが、決して正しくはなりません.たとえば、これらの2つは、特定のツリーの有効なInorderおよびPostorderトラバーサルです。

インオーダー: DBFEAGCLJHK ポストオーダー: DFEBGLJKHCA

Postorder の最後の要素であるため、明らかに A がルートです。Inorder で見ると、左側のサブツリーは {DBFE} になり、右側のサブツリーは {GCLJHK} になります。右のサブツリーのルートは、先行順序で最後から 2 番目の要素、つまり C になります。これで、右のサブツリーをさらに分割して (C をルートとして)、{G} を右のサブツリーとして、{LJHK} を左のサブツリーとして指定できます。したがって、私はこの構造を持っています：

                               A
                                \
                                 C
                                /  
                               G

しかし、私が適用するアルゴリズムが何であれ、次はツリーごとに異なる動作をするようです。誰か説明してください。

4

2 に答える 2

1

あなたの求めていることを理解できれば、前と後の状態の生データを指定して、特定の二分木検索アルゴリズムの基礎となる構造をリバース エンジニアリングしようとしています。この場合、基本的なアルゴリズムは同じですが、実際には開発者が純粋なこれらのアルゴリズムの実装。

二分木をよりよく理解しようとしているだけなら、これで少しよく説明できるかもしれません: http://www.youtube.com/watch?v=ZkH3SSPwcwI

于 2012-09-23T22:47:55.407 に答える
0

inorder と preorder トラバーサルが配列 iorder と porder でそれぞれ与えられるとします。

ツリーを構築する関数は buildTree(i,j,k) で表されます。ここで、i,j は参照する inorder 配列の範囲を指し、k は preorder 配列内の位置です。

最初の呼び出しは buildTree(0,n-1,0) になります

アルゴリズムには次のステップがあります。

  1. 最初からトラバースします。最初のノードがルートで、次に左のサブツリー、次に右のサブツリーがあります。これを要素としてノードを作成します。

  2. iorder 配列でノードを検索します。xで見つかったとします。k を減らします。k は、現在いる porder 配列内の位置を指します。k は参照渡しする必要があります。

  3. 最後に、左の子と右の子に再帰呼び出しの戻り値を入力します。 left child = buildTree(i,x-1,k) right child = buildTree(x+1,j,k)

  4. 最後にノードを返します

PS: で上記のアルゴリズムで受け入れられたコードを取得しました

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=477

于 2012-09-27T19:24:13.990 に答える