0

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

/*
  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
}

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

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

对于这个问题，你最喜欢的 C++ 实现是什么？

编辑

你将如何扩展以在给定的树中找到更大的 BST？

4

2 回答 2

3

令人惊讶的是有多少人犯了这个错误。

这是一个简单的解决方案无法拒绝的树的示例：

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

每次调用幼稚检查都会成功，因为每个父级都在其子级之间。然而，它显然不是一个格式良好的二叉搜索树。

这是一个快速的解决方案：

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。通常，BST 节点是按 <= 而不是 < 排序的，并且进行该更改只会保留一个值而不是两个值。修复整个事情留作练习。

这是一个简单的测试如何出错的演示：

#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;
}
于 2012-10-06T14:45:13.827 回答
-1

递归实现： 

bool is_bst (node *root, int min = INT_MIN, int max = INT_MAX)
{
    if (root)
    {
        // check min/max constaint
        if (root->data <= min || root->data >= max) 
          return false;

        if (root->left != NULL)
         {
           // check if the left node is bigger
           // or if it is not BST tree itself
           if (root->data < root->left->data ||
               !is_bst (root->left, min, root->data))
            return false;
         }

        if (root->right != NULL)
         {
           // check if the right node is smaller
           // or if it is not BST tree itself
           if (root->data > root->right->data ||
               !is_bst (root->right, root->data, max))
            return false;
         }
    }
    return true;
}

迭代执行

    node_type curr = root;
    node_type prev = null;
    std::stack<node_type> stack;
    while (1)
    {
        if(curr != null)
        {
            stack.push (curr);
            curr = curr->left;
            continue;
        }
        if(stack.empty()) // done
            return true;

        curr = stack.pop ();
        if (prev != null)
        {   
            if(curr->data < prev->data)
                return false;
        }
        prev = curr;
        curr = curr->right;
    }
于 2012-10-06T10:35:28.847 回答