5

How can I construct a tree given its inorder and preorder traversal? I am just looking for an efficient algorithm.

4

2 に答える 2

4

Sun の (現在は Oracle だと思います...) フォーラムからのあからさまなコピー アンド ペースト:

質問:
インオーダーおよびポストオーダー トラバーサルからバイナリ ツリーを構築する方法について誰か助けてくれませんか?適用できるようにアルゴリズムを知りたいだけです。

回答:
を後順 トラバーサルp_1とし、p_2 ... p_nをインオーダー トラバーサルとします。postorder トラバーサルから、ツリーのルートが であることがわかります。この要素を順不同のトラバーサルで見つけます。順不同のトラバーサルから、左側のサブツリー ( ) と右側のサブツリー ( ) のすべての要素をそれぞれ見つけます。i_1i_2 ... i_np_ni_1i_2 ... i_k-1 p_n i_k+1 ... i_ni_1i_2 ... i_k-1i_k+1 ... i_n

p_n要素(および要素) を削除しますi_k == p_n。の右端の要素を見つけp_jます。ここで、p_1はの要素です.... これは、元のツリーの左側のサブツリーのルートです。と...と とを分割します。これで、元のツリーの 2 つのサブツリーの後順トラバーサルとインオーダートラバーサルを表す 2 つのサブシーケンスができました。p_2 ... p_j ... p_n-1p_ji_1i_2i_k-1p_1p_2 ... p_jp_j+1p_n-1i_1i_2 ... i_k-1i_k+1 ... i_n

著者: JosAH .

Jos の指示に従ってアルゴリズムを実装したところ、完全に機能しました。

于 2010-02-02T15:14:33.323 に答える
1

これは宿題なので、完全な回答はしませんが、うまくいけば、あなたを動かすのに十分です.

たとえば、このツリーの事前注文トラバーサルがあるとします。

トラバーサルにより、2-7-2-6-5-11-5 ... などが得られます。5 は実際にはルートの右の子であることに注意してください。

明らかに、数字を見ただけではそれを知ることはできないので、ツリーの構造について知るか、追加のデータを保存する必要があります (つまり、ノードが左の子であるか右の子であるか)。 、 例えば）。

ツリーの解析は、入力として事前順序トラバーサルを受け取る単純な再帰関数です (入力を渡すときのスコープについて考えてください)。先に述べたように、事前注文のトラバーサルには、いくつかの追加データが添付されている必要があります。

効率：

このツリーを構築するときに各ノードにアクセスする回数を考慮しますが、入力を読み取る操作も考慮してください。ツリーを構築するよりも早く入力を再編成する方法はありますか? データを操作する必要がある場合、どの構造を使用する必要がありますか。

順序: 理解するには同じアイデアが必要なので、ここでは説明しません。あなたがそれを切望しているなら、他の誰かがそうするだろうと確信しています。

于 2010-02-02T15:22:34.850 に答える