为何我的BST验证函数返回false？代码问题排查求助

问题描述 #

我实现了二叉搜索树（BST）的push插入函数和验证BST有效性的check函数。我认为自己构建的输入是合法BST，但check函数返回false，无法找到原因。

我设计的check函数做了四项检查：

• 左子节点数据小于当前节点
• 右子节点数据大于当前节点
• 递归检查左子树
• 递归检查右子树

按逻辑应该返回true，但实际返回false，需要排查问题。

原始代码 #

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct tree{
    int data;
    struct tree* left;
    struct tree* right;
};

struct tree* push(int d,struct tree*head1) {
    if(head1==NULL){
        head1=(struct tree*) malloc(sizeof(struct tree));
        head1->data=d;
        head1->left=head1->right=NULL;
        return head1;
    }
    else if(head1->data>d){
        head1->right=push(d,head1->right);
    }
    else{
        head1->left=push(d,head1->left);
    }
    return head1;
}

bool small(struct tree* a,int b){
    if(a==NULL){return true;}
    if(a->data<b){return true;}
    else {return false;}
}

bool large(struct tree* a,int b){
    if(a==NULL){return true;}
    if(a->data>b ){return true;}
    else {return false;}
}

bool check(struct tree*head ){
    if(head==NULL){
        printf("empty\n");
        return true;
    }
    printf("2");
    if(small(head->left,head->data)&& large(head->right,head->data) && check(head->left) && check(head->right)){
        printf("true");
        return true;
    }
    else {
        printf("false\n");
        return false;
    }
}

int main(){
    struct tree*head;
    head=push(3,head);
    head=push(10,head);
    head=push(5,head);
    check(head);
    // printf("%d",head->data);
    return 0;
}

错误排查与修正 #

1. push函数插入逻辑完全颠倒 #

BST的核心规则是左子树所有节点值小于当前节点，右子树所有节点值大于当前节点，但你的push函数逻辑写反了：

• 当当前节点值大于插入值时，应该插入左子树，你却插入到了右子树
• 当当前节点值小于等于插入值时，应该插入右子树，你却插入到了左子树

这直接导致构建的树根本不是BST：

• 插入3 → 根节点为3
• 插入10：3<10，按错误逻辑插入到左子树
• 插入5：根节点3<5，插入到左子树；左子树节点10>5，插入到10的右子树
  最终树结构完全不符合BST规则，check函数自然返回false。

修正后的push函数：

struct tree* push(int d, struct tree* head1) {
    if (head1 == NULL) {
        head1 = (struct tree*)malloc(sizeof(struct tree));
        head1->data = d;
        head1->left = head1->right = NULL;
        return head1;
    }
    // 小于当前节点，插入左子树
    else if (head1->data > d) {
        head1->left = push(d, head1->left);
    }
    // 大于等于当前节点，插入右子树
    else {
        head1->right = push(d, head1->right);
    }
    return head1;
}

2. check函数验证逻辑不完整 #

你的check函数只检查了直接子节点与当前节点的大小关系，但BST要求左子树所有节点都小于当前节点，右子树所有节点都大于当前节点，而非仅直接子节点。比如下面的树：

5
   / \
  3   7
   \
    6

直接子节点3<5、7>5，但左子树里的6>5，属于无效BST，但你的check函数会误判为有效。

需要修改check函数，传递当前节点允许的取值范围（下界和上界）：

修正后的check函数及辅助逻辑：

#include <limits.h> // 需引入此头文件使用INT_MIN和INT_MAX

bool checkRange(struct tree* head, int minVal, int maxVal) {
    if (head == NULL) return true;
    // 当前节点值必须在[minVal, maxVal]范围内
    if (head->data <= minVal || head->data >= maxVal) return false;
    // 左子树的上界是当前节点值，下界不变
    // 右子树的下界是当前节点值，上界不变
    return checkRange(head->left, minVal, head->data) && checkRange(head->right, head->data, maxVal);
}

bool check(struct tree* head) {
    // 初始范围设为int的极值，确保根节点不受限制
    return checkRange(head, INT_MIN, INT_MAX);
}

3. 主函数初始化问题 #

主函数中struct tree* head;未初始化，直接传递给push会导致未定义行为，需要初始化为NULL：

int main(){
    struct tree* head = NULL; // 初始化
    head = push(3, head);
    head = push(10, head);
    head = push(5, head);
    if (check(head)) {
        printf("是有效BST\n");
    } else {
        printf("不是有效BST\n");
    }
    return 0;
}

最终修正后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

struct tree{
    int data;
    struct tree* left;
    struct tree* right;
};

struct tree* push(int d, struct tree* head1) {
    if (head1 == NULL) {
        head1 = (struct tree*)malloc(sizeof(struct tree));
        head1->data = d;
        head1->left = head1->right = NULL;
        return head1;
    }
    else if (head1->data > d) {
        head1->left = push(d, head1->left);
    }
    else {
        head1->right = push(d, head1->right);
    }
    return head1;
}

bool checkRange(struct tree* head, int minVal, int maxVal) {
    if (head == NULL) return true;
    if (head->data <= minVal || head->data >= maxVal) return false;
    return checkRange(head->left, minVal, head->data) && checkRange(head->right, head->data, maxVal);
}

bool check(struct tree* head) {
    return checkRange(head, INT_MIN, INT_MAX);
}

int main(){
    struct tree* head = NULL;
    head = push(3, head);
    head = push(10, head);
    head = push(5, head);
    if (check(head)) {
        printf("是有效BST\n");
    } else {
        printf("不是有效BST\n");
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者vatsal