ツリートラバーサルとシリアライズ

Question

私は、ツリートラバーサルがツリーを一意に識別するためにどのように使用されるのか、私の頭の中でまっすぐにしようとしています。そして、そのツリーがバニラバイナリツリー（BT）バイナリ検索ツリー（BST）であるという厳しい規定もあります。このarticleは、BTの場合、単一のinorder、preorder、postorder traversalがツリーを一意に識別しないことを示しているようです（このコンテキストでは、構造とキーの値を一意に意味します）。

BTの
1.私たちは、独自にinorderを行きがけ+ INORDERと後順+とBTを再構築することができます：ここに記事を簡単にまとめたものです。
2.トラバーサルがノードのヌルの子を追跡することも規定している場合は、preorder + postorderを使用することもできます。

分探索木
3.私たちは、ユニークなIDのinorderを使用することはできませんが（私）のためのオープンな質問は、（BTは、非ユニークな要素を持つことができる場合は、上記の、まだ真である場合です）。我々はinorder + preorder、またはinorder + postorderが必要です。

私の質問は、BSTを一意に識別するために予約注文またはポストオーダーを使用できますか？この質問や answer のように思われるようですので、あらかじめご了承いただけると思いますが、何卒ご了承ください。

Answer 1

ここで何が尋ねられているのかわかりません。 バイナリツリーは、ツリーの再構築に必要な一連の操作を書き出すことによって、順序付けされているかどうかに関わらずシリアル化できます。 、

が新しい内部ノードNを割り当てスタックに

• プッシュ空ツリー（またはあなたが好きならNULLポインタ）値に変換を詰め込む：ちょうど2つの命令で、単純なスタックマシンを想像してみてNの場合、スタックから2つ上のツリーをポップしてNの左右の子にして、最後にNをスタックにプッシュします。

任意バイナリツリーは、そのような機械のための「プログラム」としてシリアライズすることができます。 シリアライゼーションアルゴリズムは、ポストオーダートラバーサルを使用します。

Answer 2

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

あなたは、あなたが木への挿入のリストとして前順走査を考慮することができる

を確認するためにhttp://en.wikipedia.org/wiki/Tree_traversal#Pre-orderを確認することができます。 BSTへのツリーの挿入は確定的なので、値のリストを空のツリーに挿入すると、常に同じツリーが取得されます。