C 程序判断给定的树是否是二叉搜索树？

Question

我正在用 C 编程语言编写以下代码来确定给定的树是否是二叉搜索树。但我遇到了分段错误。谁能帮助我理解我在这里做错了什么？

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

int isBST(struct node* root) {
    if(root == NULL) {
        return 1;
    }
    if(root->left->val >= root->val || root->right->val <= root->val) {
        return 0;
    }
    return (isBST(root->left) && isBST(root->right));
}

我试图检查左节点的值是否低于当前节点的值，而右节点的值是否大于当前节点的值。同样使用递归，我对左子树和右子树重复此过程。我期待一个真或假，但得到了分段错误。

Answer 1

OP 代码有两个问题：

• 不检查

  left

  或

  right

  指针是否为

  NULL

  。
• 当前值大于左子节点的值且小于右子节点的值的条件是二叉搜索树的必要，但不是*充分*条件。

例如，如果根节点的值为

10

，左节点的值为

5

，而右节点的值为

15

，则直接子节点的检查将通过，但树不是树二叉搜索树。

二叉搜索树是一棵二叉树，其中每个节点的值都大于左子树中的所有值且小于右子树中的所有值。

以下实现的思想是按照二叉搜索树的顺序遍历树，并验证节点实际上是按顺序的，当且仅当该树是二叉搜索树时才是这种情况：

int isBST(struct node* root) {
    struct node* prev = NULL;
    return isBSTTraversal(root, &prev);
}

int isBSTTraversal(struct node* root, struct node** prev) {
    if(root == NULL) {
        return 1;
    }
    int leftBST = isBSTTraversal(root->left, prev);
    if(*prev != NULL && root->val < (*prev)->val) {
        return 0;  // Visited values are out of order: not a BST
    }
    *prev = root;
    int rightBST = isBSTTraversal(root->right, prev);
    return (leftBST && rightBST);
}