递归函数,告诉树是否是二进制搜索树(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等等,但你永远不与子树中的其他节点比较根.问题是你没有将树的根与其右边和左边的子树上的每个元素进行比较,你应该这样做.

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

以下是它如何与你显示的示例树一起工作:你看到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);
}