为什么我的 BST 验证函数的输出是 false？

Question

我编写了一个函数来填充 BST，另一个函数来验证给定的树是否是有效的 BST。

我无法理解为什么我的

check

函数返回 false，因为我已将输入创建为 BST。

当我通过

check

函数传递一棵树时，它会检查四件事：

1. 首先检查左子节点中的数据是否小于当前子节点中的数据；
2. 它检查右侧的数据是否大于当前子级中的数据；
3. 然后它将左子节点的地址作为下一个操作的根传递，它将对左子节点（现在作为根传递）执行相同的操作：这里它将再次检查根（现在是根，之前的左子节点）是否有比当前节点小的左子节点和比当前节点更大的右侧子节点类似。
4. 我们将右侧地址作为节点传递，以便我们可以检查它的左侧是否较小，右侧是否较大。

...所有这些操作返回后，我们得到

true

（如果有效）else

false

。

它应该返回我

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;
}

Answer 1

除了缺少初始化

head

之外，问题中提到的问题的主要原因在于你的

push

函数：

• 它进入了递归调用的错误一侧。与

  d

  的比较应该是相反的：

       else if(head1->data < d){  // Fix comparison
  

但是我们甚至可以在您的算法描述中看到一个错误：要验证 BST，您不仅应该验证左孩子的数据较少，而且右孩子的数据较多。您应该验证左侧子树中的 all 节点的值是否较小，右侧子树中的 all 节点的值是否较大。

这个你还没有实现，所以你会得到误报，就像这棵树一样，它不是 BST：

             5
           /
          1
            \
             10

这是一种正确的方法：

#include <limits.h>

// Helper function: arguments define a "window" for the (sub)tree
bool checkWindow(struct tree*head, int low, int high) {
    return head == NULL 
           || low <= head->data  && head->data <= high
               && checkWindow(head->left, low, head->data)
               && checkWindow(head->right, head->data, high);
}

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

Answer 2

在功能中

main()

你有

struct tree*head;
head=push(3,head);

但是编译器反对你传递未初始化的变量。

在

push()

功能中，您有

if(head1==NULL)

但这没有用，因为

head1

的值是不确定的。在

main()

你应该有

struct tree *head = NULL;
head = push(3, head);

但可能还有其他问题。