3

2 つの二分探索木の構造的同等性を、トラバーサル、前順、順順、後順の結果だけで判断することは可能ですか。すべてのトラバーサルの結果配列しかないとします。トラバーサルだけではどうにもならないことはわかっています。しかし、他のトラバーサル結果については視覚化できませんでした。BFS が役立つことは理解しています。Pre および Post オーダー トラバーサルについて知りたいです。そして、可能であれば、これに関するリンクを投稿してください。

4

2 に答える 2

3

答えは、次のとおりです。二分探索木は、事前順序走査から復元できます。

あなたの数学的なバックグラウンドが何であるかわかりませんので、さらに説明が必要かどうか尋ねてください。

簡単にするために、ノードは整数 1,2... n でラベル付けされていると仮定しています。ここで、n はノードの番号です。次に、ツリー t の事前順序トラバーサルにより[n] = {1,2,...,n}、特定のプロパティを持つ順列が得られます。順列に文字 b があるたびに、順列で の後に 2 つの連続する文字を見つけることができませcaん。このような順列は、パターン(- は任意の文字数を表す)を回避すると言われています。ba<b<cb-ac

たとえば、4 2 1 3 は b-ac を回避しますが、3 1 4 2 は 3 - 4 2 であるため回避しません。

これは実際には同等です。順列は、b-ac を回避する場合を除いて、ツリーの事前順序読み取りです。

b-ac を回避する順列と同じ数のサイズ n の木があることがわかっているため、これは全単射です。それらの数はカタロニア数として知られています。おそらくこれは、Stanley の著書「列挙的組み合わせ論」の演習として見つけることができます。

よりアルゴリズム的な説明は次のとおりです。

RecTree: Recovering a tree from is Pre-order traversal:

input: list l
output: tree t

b <- l[0]
find an index i such that 
   - for 1<=j<=i then l[j] < b and
   - for i<j<=n  then l[j] > b
if there isn't exists such an index return Failure
else return Node(key=b, RecTree(l[1..i]), RecTree(l[i+1..n]))

結果として

2 つの二分探索木が等しいのは、前の順序のトラバーサルが同じ場合のみです。

それはあなたにとって理にかなっていますか？

いくつかのより多くの参照

于 2013-07-26T08:57:24.250 に答える
0

BST では、左の子 (L)、右の子 (R)、または上 (U) に移動できます。トラバーサルは、{L, R, U} 上の文字列で記述できます。「ルルルルル」。同等の構造を持つ BST の場合、これらの文字列は同じになります。

于 2013-07-26T09:44:21.150 に答える