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语言

可以使用中序遍历二叉树，并判断遍历结果是否为升序排列。具体实现如下：

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

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

void inorderTraversal(TreeNode* root, int* vals, int* idx) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left, vals, idx);
    vals[(*idx)++] = root->val;
    inorderTraversal(root->right, vals, idx);
}

bool isValidBST(TreeNode* root) {
    int vals[10000];
    int idx = 0;
    inorderTraversal(root, vals, &idx);
    for (int i = 1; i < idx; i++) {
        if (vals[i] <= vals[i-1]) {
            return false;
        }
    }
    return true;
}

其中，`inorderTraversal` 函数用于中序遍历二叉树，将遍历结果存储在 `vals` 数组中，并使用 `idx` 变量记录当前遍历到的数组下标。`isValidBST` 函数则调用 `inorderTraversal` 函数，遍历二叉树并判断遍历结果是否为升序排列。如果是，则返回 `true`，否则返回 `false`。

用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;
}