2、试设计一个判别给定二叉树是否为二叉排序树的算法

以下是判断给定二叉树是否为二叉排序树的算法：
1. 对于空树，返回True。
2. 对于非空树，递归判断左右子树是否为二叉排序树。
3. 判断当前节点的值是否大于左子树中的最大值，小于右子树中的最小值，如果满足则返回True，否则返回False。

def isBST(root):
    if not root:
        return True
    if root.left and root.left.val > root.val:
        return False
    if root.right and root.right.val < root.val:
        return False
    return isBST(root.left) and isBST(root.right)

相关问题

试写一个判别给定二叉树是否为二叉排序树的算法。用C语言

以下是一个简单的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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

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

bool isValidBSTHelper(struct TreeNode* root, struct TreeNode* minNode, struct TreeNode* maxNode) {
    if (root == NULL) {
        return true;
    }
    if ((minNode != NULL && root->val <= minNode->val) || (maxNode != NULL && root->val >= maxNode->val)) {
        return false;
    }
    return isValidBSTHelper(root->left, minNode, root) && isValidBSTHelper(root->right, root, maxNode);
}

int main() {
    // 构造一个二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 5;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 1;
    root->left->left = NULL;
    root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right->val = 4;
    root->left->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right->left->val = 3;
    root->left->right->left->left = NULL;
    root->left->right->left->right = NULL;
    root->left->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right->right->val = 6;
    root->left->right->right->left = NULL;
    root->left->right->right->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 8;
    root->right->left = NULL;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 10;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    // 判断是否为二叉排序树
    if (isValidBST(root)) {
        printf("Given binary tree is a binary search tree.\n");
    } else {
        printf("Given binary tree is not a binary search tree.\n");
    }

    return 0;
}

该算法使用递归的方法来判断二叉树是否为二叉排序树。对于当前节点，需要保证其左子树中的所有节点值都小于当前节点的值，右子树中的所有节点值都大于当前节点的值，并且左右子树也分别是二叉排序树。为了实现这一点，算法需要同时维护一个最小值和最大值，这两个值分别表示当前节点的左子树中的最大值和右子树中的最小值。如果当前节点的值不满足上述条件之一，则返回false。否则递归判断左右子树即可。

在实现过程中，为了方便起见，我使用了一个结构体来表示二叉树节点。该结构体包含一个整数值，以及左右子树指针。同时，为了方便测试，我在main函数中构造了一个二叉树，并判断其是否为二叉排序树。

用C语言设计一个判别给定二叉树是否为二叉排序树的算法

以下是用C语言设计一个判别给定二叉树是否为二叉排序树的算法：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *lchild, *rchild;
} TreeNode, *Tree;

int pre = -32767; // pre为全局变量，保存当前结点中序前驱的值，初始值为-∞

int IsBST(Tree T) {
    int left, right; // 保存左右子树的判断结果
    if (T == NULL) // 空树也是二叉排序树，返回1
        return 1;
    else {
        left = IsBST(T->lchild); // 判断左子树是否是二叉排序树
        if (left == 0 || pre >= T->data) // 若左子树返回0或前驱大于等于当前结点
            return 0; // 则不是二叉排序树，返回0
        pre = T->data; // 保存当前结点的值
        right = IsBST(T->rchild); // 判断右子树是否是二叉排序树
        // 因为执行到这里时，left的值一定为1，如果left为0上面的则if判断为真已经返回0了
        // 所以最后直接返回右子树的结果就可以判断给定的二叉树是否是二叉排序树了
        return right;
    }
}

int main() {
    // 构造一颗二叉排序树
    Tree T = (Tree)malloc(sizeof(TreeNode));
    T->data = 4;
    T->lchild = (Tree)malloc(sizeof(TreeNode));
    T->lchild->data = 2;
    T->lchild->lchild = (Tree)malloc(sizeof(TreeNode));
    T->lchild->lchild->data = 1;
    T->lchild->lchild->lchild = NULL;
    T->lchild->lchild->rchild = NULL;
    T->lchild->rchild = (Tree)malloc(sizeof(TreeNode));
    T->lchild->rchild->data = 3;
    T->lchild->rchild->lchild = NULL;
    T->lchild->rchild->rchild = NULL;
    T->rchild = (Tree)malloc(sizeof(TreeNode));
    T->rchild->data = 6;
    T->rchild->lchild = (Tree)malloc(sizeof(TreeNode));
    T->rchild->lchild->data = 5;
    T->rchild->lchild->lchild = NULL;
    T->rchild->lchild->rchild = NULL;
    T->rchild->rchild = (Tree)malloc(sizeof(TreeNode));
    T->rchild->rchild->data = 7;
    T->rchild->rchild->lchild = NULL;
    T->rchild->rchild->rchild = NULL;

    // 判断是否为二叉排序树
    if (IsBST(T))
        printf("给定的二叉树是一颗二叉排序树。\n");
    else
        printf("给定的二叉树不是一颗二叉排序树。\n");

    return 0;
}