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-> 进行比较对 等，但您永远不会将根节点与子树中的其他节点进行比较。问题是您不会将树的根与其右子树和左子树上的每个元素进行比较，而您应该这样做。

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

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