在序列化BST的時候爲什麼有序？

Question

我瞭解到，爲了保留BST的結構並將其串行化，需要按順序存儲樹的預定義順序或後序符號中的一個。

什麼使按序符號變得重要？

Answer 1

注意：重寫了答案，以前的版本是不正確的。

對於一般二叉樹（具有獨特的元素）您的陳述將是正確的。考慮這兩個輸入（不是很嬌滴滴地繪製;-)）：

如果這些序列使用中序遍歷，無論是產量ABC。其他遍歷類型也存在類似的情況。

那麼，爲什麼有序和預購的組合足夠？

預購的序列化形狀爲[root][left subtree][right subtree]。根很容易識別，但是你不知道左側子樹的結束位置和右側子樹開始的位置。

現在考慮按序序列化：[left subtree][root][right subtree]。你知道根源是什麼（感謝預購），所以識別左右子樹非常容易。

請注意，如果權重不是唯一的，這仍然不夠。如果在上面的示例中，我們將B更改爲A，那麼對於這兩種遍歷類型，兩棵樹都會產生[AAC]。

---

對於二叉搜索樹反序列化要容易得多。爲什麼？那麼，每個子樹都具有左子樹中的節點小於根，而右子樹中的節點更大的屬性。因此，預購序列號[root][left subtree][right subtree]可以很容易和明確地再次解析。所以，最後，告訴你至少需要兩個序列化方法的B​​ST的人是錯誤的（也許他也忘記了BST的屬性）。

Answer 2

在序列化時按某種順序存儲BST可能會使構建時的檢索更簡單。想象一下，你有你的BST，只是隨機挑選節點來序列化和存儲。當檢索時，它將按照存儲的順序檢索，然後將不得不通過並連接所有節點。雖然這應該是可能的 - 所有的信息都在那裏 - 似乎沒有必要。每個節點都是浮動的;反序列化過程/程序必須保持所有節點（或類似節點）的列表，當它逐行瀏覽連接的列表時。另一方面，如果您按照某種規定的順序存儲它們，則它可以構建樹，而在每個節點中讀取 - 它知道在哪裏連接節點，因爲它們按順序排列（爲了清楚起見：並不意味着下一個節點必須連接到先前讀取的節點，在相鄰的樹葉的情況下;只需將足夠的級別跳轉到適當的分支就簡單多了）。這應該更快，並可能使用更少的內存（建設時沒有列表/容器）。