1

假设我必须比较两个二叉搜索树是否相似。现在，基本方法是递归公式，检查根是否相等，然后继续检查相应的左右子树的相等性。

但是，如果二叉搜索树具有相同的级别顺序遍历，那么它们是否相同是正确的吗？换句话说，每个 BST 是否都有唯一的级别顺序遍历？

4

2 回答 2

2

不，不是。

第一个：

1
 \
  \
   2
    \
     \
      3

第二：

   1
  / \
 /   \
2     3

级别顺序将为这两个提供 1 - 2 - 3。

由于表示具有 n 个节点的二叉树的信息论下限是2n - THETA(log n)，因此我认为任何简单的遍历都不应该能够识别二叉树。

谷歌搜索确认下限：

下界位二叉树

从 BST 到二叉树有一个简单的简化。考虑节点值为 1..n 的 BST。这些 BST 的数量是具有 n 个节点的二叉树的数量（您始终可以进行前序遍历并按该顺序插入值）。如果您可以使用级别顺序遍历来识别这样的 BST，您可以使用 1 表示“层内”节点，使用 0 表示“端层”节点。第一棵树变成“000”，第二棵树变成“010”。这将使 BST 仅用 n 位来识别，不符合信息论的下限。

于 2013-07-03T15:34:01.980 回答
1

嗯，我和我的一个朋友讨论过这个问题，所以答案不完全是我的！，但是这就是出现的情况，可以对您为 BST 执行的级别顺序遍历进行排序，因此您可以获得特定 BST 的中序遍历。现在你得到了两个遍历，然后可以用来唯一地标识 BST。因此，说每个 BST 都有一个唯一的级别顺序遍历是不正确的。

算法：

ConstructBST(levelorder[] , int Size)
   1. Declare array A of size n.
   2. Copy levelorder into A
   3. Sort A
   From two traversals A and levelorder of a Binary Search Tree , of which one is inorder, construct the tree.
于 2013-08-30T05:41:31.690 回答