AVLツリーのPreOrderトラバーサルを指定します。ツリーはユニークですか？

Question

私はクラスのAVLツリーで作業しています。

ハッシュを作成するために、指定されたツリーを識別する必要があります。ツリー内のすべての要素の事前序列を探し、その後、各要素のハッシュを連結してハッシュを構築します。

最初に、同じプリオーダー文字列の繰り返しAVLtreeがないことを確認したかったのです。私は反例を見つけられませんでしたが、私は本当にそれについてあまりよく分かりません。

ご協力いただきましてありがとうございます。

Answer 1

異なる要素のBST（バイナリ検索ツリー）は、そのプレオーダートラバーサルリストLによって一意に決定されます。これは誘導によって示すことができます。実際

：

1. ルートrはRの左側のサブツリーはR未満のすべての要素が含まれている必要があり、その先行順走査を含むLのサブリストであるL.
2. の最初の要素でなければなりませんこれらの要素：したがって、左のサブツリーは誘導によって一意的に決定される。 RそれはBSTの特別なタイプであるので、この結果も、AVLにも当てはまる

の右側のサブツリーの同じ

。