algorithm - 使用标准遍历确定 BST 的结构等价性

Question

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

Answer 1

答案是:您可以从其前序遍历中恢复二叉搜索树。

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

为简单起见，我假设节点由整数 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。

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

这里有一个更算法化的解释:

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]))

结果

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

这对你有意义吗？

更多引用

• Catalan number in the On-Line Encyclopedia of Integer Sequences
• Anders Claesson Generalized Pattern Avoidance, European Journal of Combinatorics 22 (2001) 961–971