使用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对树进行序列化

回答

相关问题