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
}

私は2番目のチェックに大きな疑問を持っています、

    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ノードは<ではなく<=で順序付けられ、その変更を行うと、2つではなく1つの値のみが予約されます。すべてを修正することは、演習として残されています。

これは、ナイーブテストがどのように間違っているかを示すデモンストレーションです。

#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 に答える