data-structures - 树遍历和序列化

Question

我正试图弄清楚如何使用树遍历来唯一标识一棵树，其症结似乎在于该树是否是香草二叉树（BT），或者它是否还有更严格的规定是二叉搜索树（BST）。本文似乎表明，对于 BT，单个中序、前序和后序遍历不会唯一标识一棵树（在此上下文中唯一表示键的结构和值）。以下是这篇文章的快速摘要：

BTs
1. 我们可以用前序+中序和后序+中序唯一地重构一个BT。
2. 如果我们还规定遍历跟踪节点的空子节点，我们也可以使用前序+后序。

（一个悬而未决的问题（对我来说）是如果 BT 可以有非唯一元素，上述情况是否仍然正确）

BSTs
3. 我们不能使用 inorder 作为唯一的 id。我们需要中序 + 预购，或中序 + 后序。

现在，（最后）我的问题是，我们可以仅使用预购还是仅使用后购来唯一标识 BST？我认为我们可以，因为这个问题和 答案 似乎是肯定的，我们可以使用预购，但非常感谢任何输入。

Answer 1

我不知道这里问的是什么。 任何二叉树，无论它是否有序，都可以通过写出重建树所需的一系列操作来序列化。想象一个只有两条指令的简单堆栈机：

• 将一棵空树（或NULL指针，如果你喜欢）压入堆栈

• 分配一个新的内部节点N，将一个值填充到N中，将顶部的两棵树从堆栈中弹出并使其成为N的左右子节点，最后将N压入堆栈。

任何二叉树都可以序列化为此类机器的“程序”。序列化算法使用后序遍历。

Answer 2

好的，您只能使用预购来识别一棵树。这是可能的，因为只有在前序遍历中，当前节点的 id 才会出现在子节点的 id 之前。因此，您可以读取从根到叶的遍历输出。

您可以查看http://en.wikipedia.org/wiki/Tree_traversal#Pre-order进行确认

因此，您可以将前序遍历视为插入树的列表。因为插入 BST 的树是确定性的，所以当您将值列表插入空树时，您总是得到相同的树。