我提出了一个递归实现检查二叉搜索树是否是有效的：

i propose a recursive implementation for checking whether binary search tree is valid:

/*
  Return true if binary tree is a binary search tree
*/
bool BinaryTree::isBinarySearchTree(BinaryTree* tree, int& prev)
{
    if(!isBinarySearchTree(tree->left, tree->data)) // left
         return false;

    if(tree->value > prev) // here
        return false;
    else
        prev = tree->value;

    return isBinaryTree(tree->right); // right
}

我有很大的疑问，在第二次检查，

i have big doubt on the second check,

    if(tree->value > prev) // here
        return false;

什么是您最喜欢的C ++实现了这个问题？

whats your favorite c++ implementation for this problem?

修改

你会怎么扩展到找到给树大BST？

how would you extend to find larger BST in given tree?

推荐答案

这是惊人的，有多少人得到这个错误。

It's amazing how many people get this wrong.

下面是一棵树而天真的解决方案，没有拒绝的例子：

Here's an example of a tree which the naive solution fails to reject:

                5
              /   \
             /     \
            4       6
           / \     / \
          1   7   1   7

天真检查每次调用会成功，因为每个家长的孩子之间。然而，这显然不是一个良好的二叉搜索树。

Every invocation of a naive check will succeed, since every parent is between its children. Yet, it is clearly not a well-formed binary search tree.

下面是一个快速的解决方案：

Here's a quick solution:

bool test(Tree* n,
  int min=std::numeric_limits<int>::min(),
  int max=std::numeric_limits<int>::max()) {
  return !n || ( 
         min < n->data && n->data < max
         && test(n->left, min, n->data)
         && test(n->right, n->data, max));
}

这是不完美的，因为它要求的是，无论INT_MIN还是INT_MAX是present树。通常情况下，BST节点以＆lt有序，而不是=＆LT，和使这一变化将只保留一个值，而不是两个。修复整个事情是留作练习。

This isn't perfect, because it requires that neither INT_MIN nor INT_MAX be present in the tree. Often, BST nodes are ordered by <= instead of <, and making that change would only reserve one value instead of two. Fixing the whole thing is left as an exercise.

下面是一个如何的幼稚测试得到它演示错误的：

Here's a demonstration of how the naive test gets it wrong:

#include <iostream>
#include <limits>
#define T new_tree

struct Tree{
  Tree* left;
  int data;
  Tree* right;
};

Tree* T(int v) { return new Tree{0, v, 0}; }
Tree* T(Tree* l, int v, Tree* r) { return new Tree{l, v, r}; }

bool naive_test(Tree* n) {
  return n == 0 || ((n->left == 0 || n->data > n->left->data)
      && (n->right == 0 || n->data < n->right->data)
      && naive_test(n->left) && naive_test(n->right));
}

bool test(Tree* n,
  int min=std::numeric_limits<int>::min(),
  int max=std::numeric_limits<int>::max()) {
  return !n || ( 
         min < n->data && n->data < max
         && test(n->left, min, n->data)
         && test(n->right, n->data, max));
}

const char* goodbad(bool b) { return b ? "good" : "bad"; }

int main(int argc, char**argv) {
  auto t = T( T( T(1),4,T(7)), 5, T(T(1),6,T(7)));
  std::cerr << "Naive test says " << goodbad(naive_test(t))
            << "; Test says " << goodbad(test(t)) << std::endl;
  return 0;
}