algorithm - 如何验证给定树是否为二叉搜索树

Question

我想知道给定的二叉树是否是二叉搜索树。

我不知道该怎么做？

我唯一知道的是，BST 的中序遍历会给你升序输出。

那么，这是我们需要验证的唯一条件还是我们应该检查的其他任何内容。

如果还有其他一些必要条件需要检查，它们是什么？为什么需要检查这些条件？因为，我认为，INORDER 遍历本身可以很容易地告诉你给定的树是否是 BST。

Answer 1

是的，如果树的中序遍历为您提供了一个严格单调的值列表，足以确定该树是 BST。

Answer 2

根据二叉搜索树的定义，如果二叉树的每个节点都满足以下条件，那么它就是一棵二叉搜索树：

• 节点的左子树应该只包含键小于节点键的节点
• 节点的右子树应该只包含键大于节点键的节点
• 左右子树也必须是二叉搜索树。

如果中序遍历是升序的，则上述所有条件都得到验证。

Answer 3

实际上 - 仅进行顺序遍历是不够的 - 您还需要验证每个节点的值是否遵循树的规则。在 BST 的情况下，左子值小于节点值，右子值大于节点值。这是Java中的递归示例。

private static boolean isBST(Node current, Comparable more, Comparable less) {
    if (current == null) 
        return true;

    if (less != null && current.value.compareTo(less) > 0)
        return false;

    if (more != null && current.value.compareTo(more) < 0) 
        return false;

    return isBST(current.left, more, current.value) && 
            isBST(current.right, current.value, less);
}

public static boolean isBST(BinarySearchTree tree) {
    return isBST(tree.getRoot(), null, null);
}

Answer 4

While doing In-Order traversal, we can keep track of previously visited node

代码：

bool isBST(struct node* root)
{
    static struct node *prev = NULL;

    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;

        // Allows only distinct valued nodes 
        if (prev != NULL && root->data <= prev->data)
          return false;

        prev = root;

        return isBST(root->right);
    }

    return true;
}

Answer 5

Java中一个简单而优雅的递归解决方案：

public static boolean isBST(TreeNode node, int leftData, int rightData)
{
    if (node == null) return true;

    if (node.getData() > leftData || node.getData() <= rightData) return false;

    return (isBST(node.left, node.getData(), rightData)
           && isBST(node.right, leftData,  node.getData()));

}

对该函数的初始调用可能是这样的：

if (isBST(root, Integer.MAX_VALUE, Integer.MIN_VALUE))
    System.out.println("This is a BST.");
else
    System.out.println("This is NOT a BST!");

本质上，我们不断创建一个有效范围（从 [MIN_VALUE, MAX_VALUE] 开始）并在递归下降时不断缩小每个节点的范围。

来源：http ://exceptional-code.blogspot.com/2011/08/binary-search-trees-primer.html