algorithm - 使用 DFS 序列化树

Question

根据 this post on Wikipedia ，给定一棵具有不同元素的树，无论是前序还是后序与中序配对都足以唯一地描述树。然而，预排序和后排序在树结构中留下了一些歧义。

我正在寻找一个简单的例子来证明这一说法。

所以给出下面的树:

顺序是:

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

我如何使用它的Pre Order 和In Order 或Post Order 和In Order 反序列化这棵树？

谢谢

Answer 1

所以声明是，给定树的先序和中序遍历，我们可以唯一地构造树。

在你的例子中
预购: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/