使用DFS對樹進行序列化

根據this post on Wikipedia，給定一棵具有不同元素的樹，無論是按順序配對的前序還是後序都足以描述該樹的唯一性。但是，預購後訂單在樹結構中留下了一些不明確之處。使用DFS對樹進行序列化

我正在尋找一個快速示例來證明這一說法。

因此，考慮下面的樹：

enter image description here

的排序是：

Pre Order: 1, 2, 4, 3, 5, 7, 8, 6 
In Order: 4, 2, 1, 7, 5, 8, 3, 6 
Post Order: 4, 2, 7, 8, 5, 6, 3, 1

我如何反序列化利用其預購和爲了或後這棵樹訂單和請訂購？

感謝

來源

2014-10-16 barak manos

樹製成的樹不是二叉搜索樹，而是二叉樹。 – 2014-10-16 10:27:30

@NikunjBanka：好的，謝謝，我相應地更新了標題。 – 2014-10-16 10:28:18

@barakmanos檢查維基百科文章引用的來源，它在那裏解釋：http://cs.stackexchange.com/questions/439/which-combinations-of-pre-post-and-in-order-sequentialisation-are-獨特 – 2014-10-16 10:41:59

所以要求是，給預購和樹，我們可以構建獨特的樹的中序遍歷。

在您的例子
預訂：1，2，4，3，5，7，8，6
依次是：4,2，1,7，5,8，3，6

現在樹中的根節點將成爲預序遍歷中的第一個節點。而且，所有出現在中序遍歷中的數值將位於以該節點爲根的左子樹中。類似地，所有出現在值後面的值都位於右邊的子樹中。因此，繼續以這種遞歸方式將對樹進行反序列化。您可以在這裏閱讀更多關於它的信息http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

同樣，您可以反序列化給定其後序和中序遍歷的樹。這裏在後序遍歷中出現的最後一個值將是樹的根。您可以閱讀有關後序和從這裏開始的反序列化http://www.programcreek.com/2013/01/construct-binary-tree-from-inorder-and-postorder-traversal/

來源

2014-10-16 10:39:19

所以樹的根是1，樹的左邊是4和2，樹的右邊是7,5,8,3和6.下一步是什麼？ – 2014-10-16 10:50:16

對於左半部分inorder = {4,2}和preorder = {2，4}遞歸地遞歸。返回的樹是樹的左邊的孩子，樹的根是1.右半邊inorder = {7,5,8,3,6}和preorder = {3,5,7,8,6}。 – 2014-10-16 10:51:58

好的，所以我使用** PreOrder **找到樹的根，然後使用** InOrder **找到樹的左側和右側。然後，我走左邊，我發現哪個值是第一個出現在** PreOrder **中的。該值是左側子樹的根。現在，我回到** InOrder **並找到該子樹的左側和右側。在這個例子中，左側僅包含值4.但確定右側包含的內容並不那麼容易。在這個例子中它是空的，但你如何有效地確定？ – 2014-10-16 11:07:10

使用DFS對樹進行序列化

回答

相關問題