樹遍歷和序列化

Question

我想直接在我的頭如何遍歷樹可以用來唯一標識一棵樹，它的癥結似乎是樹是否是香草二叉樹（BT），或者如果它也有更嚴格的規定是二叉搜索樹（BST）。這個article似乎表明，對BT來說，單一的inorder，preorder和postorder遍歷不會唯一地標識一棵樹（唯一的意思是在這種情況下key的結構和值）。下面是文章的快速摘要：

的BT
1.我們可以唯一重構BT與序+序和後序+序。
2.如果我們還規定遍歷跟蹤節點的空子節點，我們也可以使用前序+後序。

（一個開放的問題（對我來說）是，如果上述情況仍然如此，如果BT可以有非唯一元素）

BSTS
我們不能爲一個唯一的ID序使用。我們需要inorder +預購，或者order + postorder。

現在，（終於）我的問題是，我們可以使用只是預訂或只是後序來唯一標識BST嗎？我認爲我們可以，因爲這個問題和 answer 似乎是說，我們可以使用預訂，但任何輸入非常讚賞。

Answer 1

我不能說這裏有什麼要求。 任何二叉樹，無論是否有序，都可以通過寫出重構樹所需的一系列操作來序列化。想象一下，一個簡單的堆棧機只有兩個指令：

• 推空樹（或者，如果你喜歡NULL指針）壓入堆棧

• 分配一個新的內部節點ñ，東東一個值N，彈出堆棧頂部的兩棵樹，並使它們成爲N的左右兒童，最後將N推入堆棧。

不限二進制樹可以被序列化爲一個「節目」用於這樣的機器。 序列化算法使用後序遍歷。

Answer 2

好的，你可以使用預定義來識別一棵樹。這是可能的，因爲只有在前序遍歷中，id-of-current-node纔出現在孩子的id之前。所以你可以閱讀遍歷輸出的根到葉。

您可以檢查http://en.wikipedia.org/wiki/Tree_traversal#Pre-order確認

所以，你可以考慮前序遍歷作爲插入的名單成樹。因爲插入到BST中的樹是確定性的，所以當您將值列表插入空樹時，您始終會得到相同的樹。