C语言 递归函数，告诉树是否是二叉搜索树(BST)(修改代码)

Question

我在这里做练习:"http://cslibrary.stanford.edu/110/BinaryTrees.html s2"
我写了一个函数，决定如果树是一个BST(返回1)或不是(返回0)，但我不确定我的代码是完全好的，我测试了它的BST和非BST树，它似乎工作正常。我想知道社会的意见:更新代码:

考虑树(不是BST):

     5  
    /  
   2   7 
  /  
 1   6

我的想法是比较2和5，如果它是好的，那么1和5，如果它是好的，那么6和5如果它是好的，那么1和2如果它是好的，那么6和2如果它是好的，那么5和7;如果正确，isBST()返回1。这段代码应该递归地完成它。

节点结构:

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

代码:

int lisgood(struct node* n1,struct node* n2)
{
    if(n2 == NULL)
        return 1;
    else{
    int r = lisgood(n1,n2->left)*lisgood(n1,n2->right);
        if(r){
            if(n1->data >= n2->data)
            {
                return r;
            }
            else return 0;
        }
        else return r;
    }
}
int risgood(struct node* n1,struct node* n2)
{
    if(n2 == NULL)
        return 1;
    else{
        int r = risgood(n1,n2->right)*risgood(n1,n2->left);
        if(r){
            if(n1->data < n2->data)
            {
                return r;
            }
            else return 0;
        }
        else return r;
    }
}
int isBST(struct node* node)
{
    if(node == NULL)
        return 1;
    else{
        if(lisgood(node,node->left)&&risgood(node,node->right)){
            return (isBST(node->left)&&isBST(node->right));
        }
        else return 0;
    }
}

Answer 1

您的代码并没有真正工作-甚至对于您展示的示例也没有。你永远不会比较5和6。基本上，你是在比较子树的根与root->left, root->left->left, root->left->left->left等。然后将root与root->right、root->right->right等进行比较，但从不将root与子树中的其他节点进行比较。问题是，您不需要将树的根与其左右子树上的每个元素进行比较，而您应该这样做。

这是一个众所周知的面试问题。更简单的解决方法是将允许的最小值和最大值作为参数传递给子树。

下面是它如何与您展示的示例树一起工作的:您看到5，因此，5的左子树上的任何节点的最大值是5。同样，5的右子树上的任何节点的最小值都是5。递归地应用此属性以检查每个节点的值是否与要求一致。下面是一个工作实现(假设树没有重复项):

#include <stdio.h>
#include <limits.h>
struct tree_node {
    int key;
    struct tree_node *left;
    struct tree_node *right;
};
static int is_bst_aux(struct tree_node *root, int min, int max) {
    if (root == NULL) {
        return 1;
    }
    if (!(min < root->key && root->key < max)) {
        return 0;
    }
    if (!is_bst_aux(root->left, min, root->key)) {
        return 0;
    }
    return is_bst_aux(root->right, root->key, max);
}
int is_bst(struct tree_node *root) {
    return is_bst_aux(root, INT_MIN, INT_MAX);
}