1

私は、ツリー トラバーサルを使用してツリーを一意に識別する方法を頭の中で理解しようとしています。その核心は、ツリーがバニラ バイナリ ツリー (BT) であるかどうか、またはより厳密な規定があるかどうかのようです。二分探索木（BST）です。この記事は、BT の場合、単一のインオーダー、プリオーダー、ポストオーダーのトラバーサルではツリーを一意に識別できないことを示しているようです (一意とは、このコンテキストではキーの構造と値を意味します)。記事の簡単な要約は次のとおりです。

BTs
1. preorder + inorder および postorder + inorder で BT を一意に再構築できます。
2. トラバーサルがノードの null の子を追跡することも規定する場合、事前順序 + 事後順序を使用することもできます。

（（私にとって）未解決の問題は、BTが一意でない要素を持つことができる場合、上記が依然として当てはまるかどうかです）

BST
3. 一意の ID に inorder を使用することはできません。inorder + preorder、またはinorder + postorderが必要です。

さて、（最後に）私の質問は、事前注文または事後注文だけを使用して BST を一意に識別できるかということです。この質問と 回答 は「はい」と答えているようですので、事前注文を使用できますが、ご意見をいただければ幸いです。

4

2 に答える 2

0

ここで何が求められているのかわかりません。 順序付けられているかどうかに関係なく、ツリーを再構築するために必要な一連の操作を書き出すことにより、任意のバイナリツリーをシリアル化できます。命令が2つしかない単純なスタックマシンを想像してみてください。

  • 空のツリー（または必要NULLに応じてポインター）をスタックにプッシュします

  • 新しい内部ノードNを割り当て、値をNに詰め込み、スタックから上位2つのツリーをポップして、それらをNの左右の子にし、最後にNをスタックにプッシュします。

任意の二分木は、そのようなマシンの「プログラム」としてシリアル化できます。シリアル化アルゴリズムは、ポストオーダートラバーサルを使用します。

于 2012-04-20T00:40:02.643 に答える
0

オーケー、プレオーダーはツリーを識別するためだけに使用できます。id-of-current-node が子の id の前に来るのは、preorder トラバーサルでのみなので、これが可能です。したがって、ルートから葉へのトラバーサル出力を読み取ることができます。

http://en.wikipedia.org/wiki/Tree_traversal#Pre-orderで確認できます

したがって、事前注文トラバーサルをツリーへの挿入のリストと見なすことができます。BST へのツリーの挿入は決定論的であるため、空のツリーに値のリストを挿入すると、常に同じツリーが得られます。

于 2014-08-26T14:51:36.240 に答える