树遍历和序列化

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中的树是确定性的，所以当您将值列表插入空树时，您始终会得到相同的树。