判断一颗二叉树是否是二叉排序树

二叉排序树（Binary Search Tree）也称为二叉查找树，它是一种特殊的二叉树，它的左子树中所有节点的值都小于根节点的值，而右子树中所有节点的值都大于根节点的值，因此它具有以下性质：

1. 对于任意一个节点，它的左子树上的所有节点的值都小于该节点的值；
2. 对于任意一个节点，它的右子树上的所有节点的值都大于该节点的值；
3. 左右子树都是二叉排序树。

判断一颗二叉树是否是二叉排序树，可以通过中序遍历来实现，具体步骤如下：

1. 对该二叉树进行中序遍历，得到一个序列；
2. 判断该序列是否为递增序列，如果是，则该二叉树为二叉排序树；否则不是。

相关问题

C语言判断一颗二叉树是否为二叉排序树

以下是C语言判断一颗二叉树是否为二叉排序树的代码实现：

#include <limits.h>

// 定义二叉树结构体
typedef struct BT {
    int data;
    struct BT* lChild;
    struct BT* rChild;
} BT;

// 判断是否为二叉排序树
int isBST(BT* root, int MAX) {
    if (root == NULL) { // 空树是二叉排序树
        return 1;
    }
    int bst_l = isBST(root->lChild, MAX); // 判断左子树是否为二叉排序树
    // 当前节点的数据是否大于上一个结点的数据
    if (!bst_l || MAX >= root->data) {
        return 0; // 不是，则该树不为二叉排序树，返回0
    }
    MAX = root->data; // 是，则刷新MAX的值，然后以此方式继续判断下一个结点
    return isBST(root->rChild, MAX) && bst_l; // 判断右子树是否为二叉排序树
}

判断一颗二叉树是否为二叉排序树的完整C代码

以下是判断一棵二叉树是否为二叉排序树的完整C代码：

#include<stdio.h>
#include<stdlib.h>
#include<limits.h> // 引入INT_MIN和INT_MAX

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

// 判断当前节点是否在指定区间内
bool isValidBSTHelper(struct TreeNode* node, int min, int max) {
    if(node == NULL) return true;
    if(node->val <= min || node->val >= max) return false;
    return isValidBSTHelper(node->left, min, node->val) && isValidBSTHelper(node->right, node->val, max);
}

bool isValidBST(struct TreeNode* root) {
    return isValidBSTHelper(root, INT_MIN, INT_MAX);
}

其中，isValidBSTHelper函数是递归判断每个节点是否满足二叉排序树的定义，isValidBST函数则是对isValidBSTHelper函数的封装，使得可以从根节点开始判断整棵树是否为二叉排序树。在isValidBSTHelper函数中，min和max参数代表当前节点所在子树中允许的最小值和最大值，如果当前节点的值小于等于最小值或大于等于最大值，则不满足二叉排序树的定义。如果当前节点满足条件，则需要递归判断左右子树是否也满足条件。在isValidBST函数中，将根节点的最小值和最大值设为INT_MIN和INT_MAX，即不做限制，然后调用isValidBSTHelper函数进行判断。