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

Question

给定一个简单的二叉树,我们如何证明树是二叉搜索树？当我们遍历二叉树时,我们如何知道我们所在的节点是否是其父节点的左子节点？我提出了一个解决方案,我将在递归函数调用中传递一些标志,它可以跟踪节点是否是其父节点的左子节点或者我们需要一个父节点指针,我们可以通过它来比较:

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

以同样的方式,需要一个条件R.除此之外你能想到其他任何有效的方法吗？

提前致谢 :)

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

没有测试它所以我不知道它在性能上是否重要.

Answer 2

简单的答案是进行有序深度优先树遍历并检查节点是否有序.

示例代码(Common 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))))