如何证明二叉树确实是二叉搜索树？

Question

给定一个简单的二叉树，我们如何证明这棵树是一个二叉搜索树？当我们遍历二叉树时，我们如何知道当前节点是其父节点的左孩子还是右孩子？我提出了一种解决方案，在递归函数调用中传递一些标志，以便跟踪当前节点是其父节点的左孩子还是右孩子，同时我们需要一个父节点指针进行比较：-

if(flag == 'L' && node->value < node->parent->value)
   then continue recursion;
else{
   print "not a binary search tree"
   exit;
}

同样地，R 需要一个条件语句。除此之外，您能想到其他更有效的方法吗？

提前感谢 :)

- TCM

Answer 1

我只需要检查：

currentNode.Left.max() < currentNode.Value和currentNode.Left.isBinarySearchTree()。 如果两者都满足，则为二叉搜索树。

编辑：

以上内容确实对左侧树进行了两次遍历（一次用于max()，一次用于isBinarySearchTree）。然而，可以仅使用一次遍历来完成：

在您的树类中存储最小和最大元素。更新等操作当然可以在O(1)空间和时间内执行。

然后，不要使用max()，而是制作一个名为isInRange(m,M)的方法，该方法检查（子）树是否仅包含范围(m,m+1,...,M)中的元素。

按以下方式定义isInRange(m,M)：

bool isInRange(m,M){
 if (m < currentNode.Value <= M){
  return (currentNode.Left.isInRange(m, currentNode.Value) && currentNode.Right.isInrange(currentNode.Value+1, M));
 }
 return false;
}

然后，最初的调用将是root.isInRange(globalmin, globalmax)。

由于没有测试过，所以不知道它是否会影响性能。

- phimuemue

---

当然，右子树的标准也要与左子树相同。 - Jerry Coffin

非常好 :). 不知道为什么我脑子里没有反应过来。 - TCM

+1：非常出色的递归答案。这使得验证子节点是否为左节点的检查变得不必要（我们可以通过检查 node == node->parent->left 来完成）。 - kbrimington

Answer 2

简单的答案是进行“按顺序深度优先遍历”并检查节点是否有序。

示例代码（通用Lisp）：

(defun binary-search-tree-p (node)
  (let ((last-value nil))
    (labels ((check (value)
               (if (or (null last-value)        ; first checked value
                       (>= value last-value))
                   (setf last-value value)
                   nil))
             (traverse (node)
               (if (null node)
                   t
                   (and (traverse (left node))        ; \
                        (check (value node))          ;  > in-order traversal
                        (traverse (right node))))))   ; /
      (traverse node))))

- Svante

Answer 3

您是否已经有一种遍历树中元素的方法？那么您可以简单地遍历树，并检查每个元素是否大于前一个元素。

- John La Rooy

---

必须进行深度优先遍历。 - H H

@Henk，是的，当然。我认为如果树具有此功能，它将会是深度优先搜索。 - John La Rooy

Answer 4

您可以在树上进行深度优先搜索，而无需在单次遍历中缓存每个子树的最小值和最大值，但是您必须小心，因为仅比较父节点和其子节点之间的值是不够的。例如，在以下树中：

(10
   (7
     nil
     (20 nil nil)
   )
   nil
)

根节点（10）的左子节点（7）满足不等式（7 <= 10），7的右子节点（20）也满足（20 >= 7）。然而，该树不是BST（二叉搜索树），因为20不应该在10的左子树中。

要解决这个问题，您可以进行遍历，并传递额外的参数来指定子树的有效区间。

// The valid interval for the subtree root's value is (lower_bound, upper_bound).
bool IsBST(const node_t* tree, int lower_bound, int upper_bound) {
  if (tree == NULL) return true;  // An empty subtree is OK.
  if (tree->value <= lower_bound) return false;  // Value in the root is too low.
  if (tree->value >= upper_bound) return false;  // Value in the root is too high.

  // Values at the left subtree should be strictly lower than tree->value
  // and be inside the root valid interval.
  if (!IsBST(tree->left, lower_bound, tree->value))
    return false;

  // Values at the left subtree should be strictly greater than tree->value
  // and be inside the root valid interval.
  if (!IsBST(tree->right, tree->value, upper_bound))
    return false;

  // Everything is OK, it is a valid BST.
  return true;  
}

注意保留原始有效区间，函数将会检测到20在该位置是无效的，因为它不在（7，10）之内。第一次调用应该使用无限区间，例如：

IsBST(tree, INT_MIN, INT_MAX);

希望这能帮到你。

- jbernadas