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

我不知道该怎么做呢？

我所知道的唯一的事情就是BST意志的序遍历为您提供了升序输出。

所以，这是我们需要验证或者是还有什么事情，我们想检查的唯一条件。

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

2012-04-16 Jatin

开始[二叉搜索树的定义（http://en.wikipedia.org/wiki/Binary_search_tree）。给出的树是否符合这个定义？（请注意，按顺序遍历规则可以通过递归地应用规则来导出。还要注意，不同的树，例如RB，可能有资格作为BST *和*另一种树类型。） – 2012-04-16 08:44:35

（或者说，RB树*是a * BST等） – 2012-04-16 08:51:06

请问您可以通过下面的链接....我问的问题几乎与此类似。但在这个环节中，除了INORDER遍历之外，人们还提出了其他一些方法。我不知道为什么这些额外的条件需要检查。 http://stackoverflow.com/questions/499995/what-is-validating-a-binary-search-tree – Jatin 2012-04-16 09:02:01

是的，如果序树的遍历给你值的严格单调名单足以确定该树是BST。

来源

2012-04-16 08:42:19

它可以重复吗？单调列表是什么意思？ – 2017-04-22 14:40:35

通过二叉搜索树的定义，若二叉树的每个节点满足下列条件那么它是一个二叉搜索树：

一个节点的左子树应该只包含节点与键小于节点的密钥
节点的右侧子树应只包含密钥大于节点密钥的节点
左侧和右侧子树也必须是二叉搜索树。

如果按顺序遍历按升序排列，则所有上述条件都被验证。

来源

2013-03-05 16:04:23 banarun

其实 - 这是不够的，只是做一个中序遍历 - 你还需要验证每个节点的值如下树的规则。在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); 
}

来源

2013-08-27 13:57:04

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; 
}

来源

2014-05-09 07:12:29 Suraj

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

来源

2014-05-09 21:30:28 Sanj

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

回答

相关问题