0

您在二叉树中拥有最大 BST 的方法是什么？最大，我的意思是：最高。

我参考了这篇文章，其中找到了一个非常好的实现来查找树是否是 BST

bool isBinarySearchTree(BinaryTree * n,
int min=std::numeric_limits<int>::min(),
int max=std::numeric_limits<int>::max()) 
{
     return !n || (min < n->value && n->value < max
     && isBinarySearchTree(n->l, min, n->value)
     && isBinarySearchTree(n->r, n->value, max));
}

实现一个解决方案来查找一棵树是否包含二叉搜索树是很容易的。我认为以下方法可以做到：

bool includeSomeBST(BinaryTree* n)
{ 
      return includeSomeBST(n->left)  ||  includeSomeBST(n->right) ;

      if(n == NULL)
           return false ; 

      return true ;
}

但是如果我想要最大的 BST 怎么办？这是我的第一个想法

BinaryTree largestBST(BinaryTree* n)
{ 
      if(isBinarySearchTree(n))
           return n;

      if(!isBinarySearchTree(n->left))
      {
           if(!isBinarySearchTree(n->right))
               if(includeSomeBST(n->right))
                    return largestBST(n->right);

               else if(includeSomeBST(n->left))
                    return largestBST(n->left);

               else
                   return NULL;

           else
               return n->right;
      }
      else 
          return n->left;
}

但实际上它并没有告诉最大的。我很难进行比较。应该如何进行？

谢谢

4

2 回答 2

1

是的，你的函数 includeSomeBST 是错误的。您只需检查节点 n,n->left 和 n->right，但必须递归检查节点。

bool includeSomeBST(BinaryTree* n) {

  if(!isBinarySearchTree(n))
  {

       return includeSomeBST(n->left) || includeSomeBST(n->right);
  }

  if(n==NULL) return false; 
  return true;

}

于 2012-10-07T10:30:08.257 回答
0

这是与驱动程序一起成功的代码实现：

#include <iostream>
using namespace std;

class BinaryTree {
    public:
        BinaryTree *right;
        BinaryTree *left;
        int value;
        BinaryTree(int value) {
            this->value = value;
        }
};


int max_value(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

int min_value(int a, int b) {
    if (a < b) {
        return a;
    } else {
        return b;
    }
}

BinaryTree* findLargestBST(BinaryTree *n, int* maxSize, int *max, int *min, bool *is_bst) {
    if (n == NULL) {
        *maxSize = 0;
        *is_bst = true;
        return n;
    }
    int *lc_max_size = new int;
    int *rc_max_size = new int;
    int *lc_max = new int;
    int *lc_min = new int;
    int *rc_max = new int;
    int *rc_min = new int;
    *lc_max = std::numeric_limits<int>::min();
    *rc_max = *lc_max;
    *lc_min = std::numeric_limits<int>::max();
    *rc_min = *lc_min;
    BinaryTree* returnPointer;

    bool is_curr_bst = true;
    BinaryTree* lc = findLargestBST(n->left, lc_max_size, lc_max, lc_min, is_bst);
    if (!*is_bst) {
        is_curr_bst = false;
    }

    BinaryTree* rc = findLargestBST(n->right, rc_max_size, rc_max, rc_min, is_bst);
    if (!*is_bst) {
        is_curr_bst = false; 
    }

    if (is_curr_bst && *lc_max <= n->value && n->value <= *rc_min) {
        *is_bst = true;
        *maxSize = 1 + *lc_max_size + *rc_max_size;
        returnPointer = n;
        *max = max_value (n->value, *rc_max);
        *min = min_value (n->value, *lc_min);
    } else {
        *is_bst = false;
        *maxSize = max_value(*lc_max_size, *rc_max_size);
        if (*maxSize == *lc_max_size) {
            returnPointer = lc;
        } else {
            returnPointer = rc;
        }
        *max = *min = n->value;
    }

    delete lc_max_size;
    delete rc_max_size;
    delete lc_max;
    delete lc_min;
    delete rc_max;
    delete rc_min;
    return returnPointer;
}

int main() {

    /* Let us construct the following Tree
          50
       /      \
     10        60
    /  \       /  \
   5   20    55    70
            /     /  \
          45     65    80
  */

  BinaryTree *root = new BinaryTree(50);
  root->left        = new BinaryTree(10);
  root->right       = new BinaryTree(60);
  root->left->left  = new BinaryTree(5);
  root->left->right = new BinaryTree(20);
  root->right->left  = new BinaryTree(55);
  root->right->left->left  = new BinaryTree(45);
  root->right->right = new BinaryTree(70);
  root->right->right->left = new BinaryTree(65);
  root->right->right->right = new BinaryTree(80);

  /* The complete tree is not BST as 45 is in right subtree of 50.
     The following subtree is the largest BST
        60
      /  \
    55    70
   /     /  \
  5     65    80
  */

  int *maxSize = new int;
  int *min_value = new int;
  int *max_value = new int;
  *min_value = std::numeric_limits<int>::max();
  *max_value = std::numeric_limits<int>::min();
  bool *is_bst = new bool;
  BinaryTree *largestBSTNode = findLargestBST(root, maxSize, max_value, min_value, is_bst);
  printf(" Size of the largest BST is %d", *maxSize);
  printf("Max size node is %d", largestBSTNode->value);
  delete maxSize;
  delete min_value;
  delete max_value;
  delete is_bst;
  getchar();

  return 0;
}

使用的方法相当简单，可以理解如下：

这是一种自下而上的方法，而不是我们在确定树是否为 BST 时使用的自上而下的方法。它使用与确定树是否为 BST 时相同的最大最小方法。

以下是以递归方式在每个节点上执行的步骤： 注意：请记住，这是一种自下而上的方法，信息将从底部流向顶部。

1）确定我是否存在。如果我不是（我是 null），我不应该以任何方式影响算法，并且应该在不做任何修改的情况下返回。

2) 在每个节点，存储到该点的 BST 的最大大小。如果此特定节点处的树满足 BST 属性，则使用左子树的总大小 + 右子树的总大小 + 1（对于节点本身）来确定。否则，从左子树和右子树返回的最大值中算出。

3) 如果在给定节点处满足 BST 属性，则返回当前节点作为直到这一点的最大大小 BST，否则从左子树和右子树确定。

于 2012-10-08T18:37:58.977 回答