判断树是否为二叉搜索树 (BST) 的递归函数（修改后的代码）

Question

我在这里做练习： “http://cslibrary.stanford.edu/110/BinaryTrees.html#s2”
我写了一个函数来决定树是 BST(return 1) 还是不是 (return 0) 但我不确定我的代码是否完全好，我测试了它的 BST 和一个非 BST 树，它似乎工作正常。我想知道社区的意见： 更新代码：

考虑树（不是 BST）：

我的想法是比较 2 和 5，如果好，然后 1 和 5，如果好，然后 6 和 5，如果好，然后 1 和 2，如果好，然后 6 和 2，如果好，然后 5 和7;如果它是好的 isBST() returns 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);
}

判断树是否为二叉搜索树 (BST) 的递归函数（修改后的代码）

recursive function that tells if a Tree is a Binary Search Tree ( BST ) (Modified code)

c

recursion

binary-tree