3

是否可以仅通过遍历的结果，前序，中序和后序来确定两个二叉搜索树的结构等价。假设我只有所有遍历的结果数组。我知道单单为了遍历，没办法。但是，我无法想象其他遍历结果。我了解 BFS 有帮助。我想知道前后顺序遍历。如果可能，请在此发布任何链接。

4

2 回答 2

3

答案是：你可以从它的前序遍历中恢复二叉搜索树。

我不确定您的数学背景是什么，所以请询问您是否需要更多解释。

为简单起见，我假设节点由整数 1,2...n 标记，其中 n 是节点数。然后树 t 的前序遍历为您提供了一个[n] = {1,2,...,n}具有特定属性的排列：每次您的排列中有一个字母 b 时，您在排列中找不到两个连续ca的字母，b使得a<b<c. 据说这样的排列可以避免这种模式b-ac（- 代表任意数量的字母）。

例如，4 2 1 3 避免了 b-ac，而 3 1 4 2 则没有，因为 3 - 4 2。

这实际上是一个等价：排列是一棵树的前序读取，当且仅当是避免 b-ac。

众所周知，大小为 n 的树与避免 b-ac 的排列一样多，因此这是一个双射。他们的号码被称为加泰罗尼亚号码。您可能会发现这是对斯坦利的书“枚举组合学”的练习。

这是一个更算法的解释：

RecTree: Recovering a tree from is Pre-order traversal:

input: list l
output: tree t

b <- l[0]
find an index i such that 
   - for 1<=j<=i then l[j] < b and
   - for i<j<=n  then l[j] > b
if there isn't exists such an index return Failure
else return Node(key=b, RecTree(l[1..i]), RecTree(l[i+1..n]))

作为结果

两棵二叉搜索树相等当且仅当它们具有相同的前序遍历

这对你有意义吗？

更多参考资料

于 2013-07-26T08:57:24.250 回答
0

在 BST 中，您可以选择左孩子 (L)、右孩子 (R) 或上孩子 (U)。然后可以通过 {L, R, U} 上的字符串来描述遍历，例如。“鲁鲁鲁鲁鲁”。对于具有等效结构的 BST，这些字符串将是相同的。

于 2013-07-26T09:44:21.150 回答