680 字

2 分钟

判断是否为二叉搜索树

2026-04-15

数据结构

/

c

/

c++

/

二叉树

判断是否为二叉搜索树#

一、引言#

众所周知啊，我们的二叉搜索树的定义是：左子树所有节点都小于根节点，右子树所有节点都大于根节点。

二叉搜索树既然满足上面的特性，那么对于他的子树来说，也是一个二叉搜索树，如下图，是一个递归结构。

那么我们利用这个定义就能来判断是否为二叉搜索树。

二、初次尝试#

一种比较直观的思路就是通过递归遍历左子树，来判断是否每个节点都小于根。右子树同理。

我们来用cpp实现一下。

1
bool issubtreeless(Node* root,int value){
2
    //判断子节点是否小于根节点
3
    if(root==NULL)return true;
4
    if(root->data<=value
5
       &&issubtreeless(root->left,value)
6
       &&issubtreeless(root->right,value)
7
      ){
8
        return true;
9
    }
10
    else return false;
11
}
12
bool issubtreegreater(Node* root,int value){
13
    //判断子节点是否大于根节点
14
    if(root==NULL)return true;
15
    if(root->data>value
16
       &&issubtreeless(root->left,value)
17
       &&issubtreeless(root->right,value)
18
      ){
19
        return true;
20
    }
21
    else return false;
22
}

这里是比较了左右子树每一个节点与根节点大小的两个函数，同样，你也可以写一个找到左右最大最小值的函数，效果和开销是一样的！

1
bool isbinarysearchtree(Node *root){
2
  if(root==NULL)return true;
3
  if(issubtreeless(root->left,root->data)
4
  &&issubtreegreater(root->right,root->data)
5
  &&isbinarysearchtree(root->left)
6
  &&isbinarysearchtree(root->right)
7
  )
8
     return true;
9
    else
10
        return false;
11
}

这是判断是否为二叉搜索树的函数，判断原则是：左子树小于等于根，右子树大于根，左右子树均为二叉搜索树！

这里几乎用了四次递归！甚至不包含比较函数里面的递归，开销大的一批！但凡树的高度要大一点，那么我们的栈随时都可能溢出~！

很显然，这个方案不理想。

三、头铁#

既然解决不了，那就换方法🤔

众所周知啊，我们的二叉搜索树的定义是：左子树所有节点都小于根节点，右子树所有节点都大于根节点。

回想一下这句话，我们依然要拟合出这种效果，那么有没有更好的方法。

有的，兄弟有的。

我们可以对每个节点设置范围限制。

什么意思？就是约束一个节点，让其处于自己该处于的位置。看看我精心画的图，你绝对猜不到我的无穷符号是怎么弄出来的😎

根节点任意范围，其他节点则收到约束（左孩子比他小，右孩子比他大）

现在我们来实现一下吧！

1
bool isbinarysearchtree(Node *root,int minvalue, int maxvalue){
2
    if(root==NULL)return true;
3
    if(root->data>=minvalue
4
    &&root->data<maxvalue
5
       &&isbinarysearchtree(root->left,minvalue,root->data)
6
       &&isbinarysearchtree(root->right,root->data,maxvalue)
7
      )
8
        return true;
9
    else return false;
10
}