21

我对不同站点上的许多文章感到非常困惑，这些文章涉及Binary Search Tree从任何一个遍历（pre，post或in-order）或其中任何两个的组合构建一个。例如，在这个页面上，它说给定pre,post或level顺序遍历，连同in-order遍历，可以构造BST. 但是在这里和那里，他们向我们展示了如何单独构建一个BST。pre-order此外，他们在这里向我们展示了如何构造BSTfrom givenpre和post-ordertraversals。在其他一些站点中，我找到了一个BST仅从post-order遍历构造 a 的解决方案。

现在我知道给定inorder和pre-order遍历，可以唯一地形成一个BST. 至于我提供的第一个链接，虽然他们说我们不能构造BSTfrompre-order和post-order，但我不能对post-order数组进行排序以获取它的inorder遍历，然后使用它和pre-order数组来形成BST? 这与第四个链接中的解决方案相同还是不同？并且pre-order仅给出，我可以对它进行排序以获得in-order，然后使用它和pre-order来获得BST. 同样，这是否必须与链接 2 和 3 的解决方案不同？

具体来说，什么足以唯一地生成BST？如果不需要唯一性，那么我可以简单地对其进行排序以获取遍历，并从中递归地in-order构建 N 个可能的 s 之一。BST

4

2 回答 2

26

要构造 BST，您只需要一次（不是按顺序）遍历。

通常，要构建二叉树，您将需要两次遍历，例如按顺序和预排序。但是，对于 BST 的特殊情况 - 中序遍历始终是包含元素的排序数组，因此您始终可以重建它并使用算法从前序遍历和中序遍历中重建通用树。

因此，树是 BST 的信息，以及其中的元素（甚至是无序的）等价于中序遍历。

奖励：为什么对于一般树来说一次遍历还不够，（没有信息它是 BST）？
答：假设我们有n不同的元素。但是，这些元素有n!可能的列表n- 树的可能数量要大得多（2 * n！n 个元素的可能树都是腐烂的树，因此node.right = null在每个节点中，树实际上是右侧的列表. 有n!这样的树，并且总是有另外 n! 棵树node.left = null）因此，根据鸽子洞原理 - 至少有一个列表生成 2 棵树，因此我们无法从一次遍历中重建树。(QED)

于 2012-10-14T09:14:15.993 回答
0

如果给定 BST 节点的值，则只需遍历一次就足够了，因为其余数据由节点的值提供。但是，如果这些值是未知的，那么根据我的理解，从一次遍历中构建一个唯一的 BST 是不可能的。但是，我愿意接受建议。

于 2017-06-01T05:05:14.127 回答