判断二叉树是否是二叉搜索树

ゝ一世哀愁。 2021-12-21 07:39 287阅读 0赞

## 问题 ##

给定一棵二叉树，判定该二叉树是否是二叉搜索树（Binary Search Tree）？

解法1:暴力搜索

首先说明一下二叉树和二叉搜索树的区别。二叉树指这样的树结构，它的每个结点的孩子数目最多为2个；二叉搜索树是一种二叉树，但是它有附加的一些约束条件，这些约束条件必须对每个结点都成立：

*  结点node的左子树所有结点的值都小于node的值。
 *  结点node的右子树所有结点的值都大于node的值。
 *  结点node的左右子树同样都必须是二叉搜索树。

该问题在面试中也许经常问到，考察的是对二叉搜索树定义的理解。初看这个问题，也许会想这样来实现：

假定当前结点值为k。对于二叉树中每个结点，判断其左孩子的值是否小于k，其右孩子的值是否大于k。如果所有结点都满足该条件，则该二叉树是一棵二叉搜索树。

**很不幸的是，这个算法是错误的。考虑下面的二叉树，它符合上面算法的条件，但是它不是一棵二叉搜索树。**

10
       /  \
      5   15     -------- binary tree (1)
         /  \
        6    20

那么，根据二叉搜索树的定义，可以想到一种暴力搜索的方法来判定二叉树是否为二叉搜索树。

假定当前结点值为k。则对于二叉树中每个结点，其左子树所有结点的值必须都小于k，其右子树所有结点的值都必须大于k。

暴力搜索算法代码如下，虽然效率不高，但是它确实能够完成工作。该解法最坏情况复杂度为O（n^2)，n为结点数目。（当所有结点都在一边的时候出现最坏情况）

[![复制代码][copycode.gif]][copycode.gif 1]

1 /*判断左子树的结点值是否都小于val*/
     2 bool isSubTreeLessThan(BinaryTree *p, int val) 
     3 {
     4   if (!p) return true;
     5   return (p->data < val &&
     6           isSubTreeLessThan(p->left, val) &&
     7           isSubTreeLessThan(p->right, val));
     8 }
     9  /*判断右子树的结点值是否都大于val*/
    10 bool isSubTreeGreaterThan(BinaryTree *p, int val) 
    11 {
    12   if (!p) return true;
    13   return (p->data > val &&
    14           isSubTreeGreaterThan(p->left, val) &&
    15           isSubTreeGreaterThan(p->right, val));
    16 }
    17  /*判定二叉树是否是二叉搜索树*/
    18 bool isBSTBruteForce(BinaryTree *p) 
    19 {
    20   if (!p) return true;
    21   return isSubTreeLessThan(p->left, p->data) &&
    22          isSubTreeGreaterThan(p->right, p->data) &&
    23          isBSTBruteForce(p->left) &&
    24          isBSTBruteForce(p->right);
    25 }

[![复制代码][copycode.gif]][copycode.gif 1]

一个类似的解法是：对于结点node，判断其左子树最大值是否大于node的值，如果是，则该二叉树不是二叉搜索树。如果不是，则接着判断右子树最小值是否小于或等于node的值，如果是，则不是二叉搜索树。如果不是则接着递归判断左右子树是否是二叉搜索树。（代码中的 maxValue和minValue函数功能分别是返回二叉树中的最大值和最小值，这里假定二叉树为二叉搜索树，实际返回的不一定是最大值和最小值）

[![复制代码][copycode.gif]][copycode.gif 1]

1 bool isBST(struct node* node) 
     2 { 
     3   if (node==NULL) return true;
     4   //如果左子树最大值>=当前node的值，则返回false
     5   if (node->left!=NULL && maxValue(node->left) >= node->data) 
     6     return false;
     7   // 如果右子树最小值<=当前node的值，返回false
     8   if (node->right!=NULL && minValue(node->right) <= node->data) 
     9     return false;
    10   // 如果左子树或者右子树不是BST，返回false
    11   if (!isBST(node->left) || !isBST(node->right)) 
    12     return false;
    13   // 通过所有测试，返回true
    14   return true; 
    15 }

[![复制代码][copycode.gif]][copycode.gif 1]

## 解法2：更好的解法 ##

以前面提到的binary tree（1）为例，当我们从结点10遍历到右结点15时，我们知道右子树结点值肯定都在 **10和****+INFINITY（无穷大）**之间 **。** 当我们遍历到结点15的左孩子结点6时，我们知道结点15的左子树结点值都必须在10到15之间。显然，结点6不符合条件，因此它不是一棵二叉搜索树。该算法代码如下：

[![复制代码][copycode.gif]][copycode.gif 1]

bool isBST2(struct node* node) 
    {
          return isBSTUtil(node, INT_MIN, INT_MAX);
    }
    /*
    给定的二叉树是BST则返回true，且它的值  >min 以及 < max.
    */
    bool isBSTUtil(struct node* node, int min, int max) 
    {
          if (node==NULL) return true;
          // 如果不满足min和max约束，返回false
          if (node->data<=min || node->data>=max) return false;
          // 递归判断左右子树是否满足min和max约束条件
          return
              isBSTUtil(node->left, min, node->data) &&
              isBSTUtil(node->right, node->data, max)
          );
    }

[![复制代码][copycode.gif]][copycode.gif 1]

由于该算法只需要访问每个结点1次，因此时间复杂度为O（n），比解法1效率高很多。

## 解法3：中序遍历算法 ##

因为一棵二叉搜索树的中序遍历后其结点值是从小到大排好序的，所以依此给出下面的解法。该解法时间复杂度也是O（n）。

[![复制代码][copycode.gif]][copycode.gif 1]

bool isBSTInOrder(BinaryTree *root) 
    {
      int prev = INT_MIN;
      return isBSTInOrderHelper(root, prev);
    }
    /*该函数判断二叉树p是否是一棵二叉搜索树，且其结点值都大于prev*/
    bool isBSTInOrderHelper(BinaryTree *p, int& prev) 
    {
      if (!p) return true;
      if (isBSTInOrderHelper(p->left, prev)) 
      { // 如果左子树是二叉搜索树，且结点值都大于prev
        if (p->data > prev) 
        { //判断当前结点值是否大于prev，因为此时prev已经设置为已经中序遍历过的结点的最大值。
          prev = p->data;
          return isBSTInOrderHelper(p->right, prev); //若结点值大于prev，则设置prev为当前结点值，并判断右子树是否二叉搜索树且结点值都大于prev。
         } else {
          return false;
        }
      }
      else {
        return false;
      }
    }

[![复制代码][copycode.gif]][copycode.gif 1]

转：[http://blog.csdn.net/ssjhust123/article/details/7771096][http_blog.csdn.net_ssjhust123_article_details_7771096]

Wayne学习园地 http://www.cnblogs.com/Bob-FD

[copycode.gif]: http://common.cnblogs.com/images/copycode.gif
[copycode.gif 1]: /images/20211221/53b91189b11947cfb6e6d7c521a80248.png
[http_blog.csdn.net_ssjhust123_article_details_7771096]: http://blog.csdn.net/ssjhust123/article/details/7771096

发表评论取消回复

表情：

评论列表（有 0 条评论，287人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】判断二叉树是否是平衡二叉树

问题：判断一个二叉树是否是平衡二叉树。分析：平衡二叉树要求左子树和右子树的高度相差为1，且左右子树都是平衡二叉树。递归可以很好的解决这个问题。但是首先要求树的深度。代码

迈不过友情╰/ 2022年08月09日 05:08/ 0 赞/ 250 阅读

相关判断二叉树是否是平衡树

面试题39：输入一颗二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中节点的左右子树的深度相差不超过1，那么它就是一颗平衡二叉树 //判断二叉树是不是平衡树

「爱情、让人受尽委屈。」/ 2022年06月17日 07:08/ 0 赞/ 244 阅读

相关判断一棵二叉树是否是平衡二叉树

![这里写图片描述][70] class TreeNode { int val = 0; TreeNode left = null;

た入场券/ 2022年05月25日 12:44/ 0 赞/ 268 阅读

相关判断二叉树是否是对称二叉树

![这里写图片描述][70] import java.util.; class TreeNode { int val = 0;

约定不等于承诺〃/ 2022年05月24日 07:43/ 0 赞/ 268 阅读

相关判断一棵二叉树是否是对称二叉树

![70][] class TreeNode { int val; TreeNode left; TreeNod

朱雀/ 2022年05月17日 04:39/ 0 赞/ 253 阅读

相关判断二叉树是否是平衡二叉树

平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。思路：如

àì夳堔傛蜴生んèń/ 2022年04月18日 01:47/ 0 赞/ 316 阅读

相关判断二叉搜索树

二叉查找树（Binary Search Tree），（又：[二叉搜索树][Link 1]，二叉排序树）它或者是一棵空树，或者是具有下列性质的[二叉树][Link 2]：若它的

灰太狼/ 2022年04月15日 01:06/ 0 赞/ 190 阅读

相关判断二叉树是否是二叉搜索树

问题给定一棵二叉树，判定该二叉树是否是二叉搜索树（Binary Search Tree）？解法1:暴力搜索首先说明一下二叉树和二叉搜索树的区别。二叉树指这

ゝ一世哀愁。/ 2021年12月21日 07:39/ 0 赞/ 288 阅读

相关是否二叉搜索树

6-1 是否二叉搜索树 (25 分) 本题要求实现函数，判断给定二叉树是否二叉搜索树。函数接口定义： bool IsBST ( BinTree T ); 其中B

左手的ㄟ右手/ 2021年11月29日 08:58/ 0 赞/ 347 阅读

相关【数据结构】（平衡二叉树）判断二叉树是否是平衡二叉树

> 算法思想：判断一棵树是否为平衡二叉树可以采取高度差的递归方式来判断这个方法比较简单但是复杂度较高（因为高度被重复计算了很多次）O（nlogn） //递归求高度

短命女/ 2021年10月29日 14:50/ 0 赞/ 417 阅读