试设计一个判别给定二叉树是否为二叉排序树的算法,用c语言程序实现完整程序
时间: 2024-02-18 11:00:19 浏览: 73
写一算法,判断一棵二叉树是否是一棵二叉排序树。
算法思路:
1. 判断当前节点是否为空,若为空则返回真。
2. 判断当前节点的左子树是否为二叉排序树,若不是则返回假。
3. 判断当前节点的值是否大于其左子树中最大值,若不是则返回假。
4. 判断当前节点的右子树是否为二叉排序树,若不是则返回假。
5. 判断当前节点的值是否小于其右子树中最小值,若不是则返回假。
6. 若以上条件都满足,则返回真。
C语言代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VALUE 1000000000 // 定义一个大的数作为初始值
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
bool isValidBST(struct TreeNode* root) {
if (root == NULL) {
return true;
}
// 判断左子树是否为二叉排序树
if (!isValidBST(root->left)) {
return false;
}
// 判断当前节点的值是否大于其左子树中最大值
if (root->left != NULL && root->val <= root->left->val) {
return false;
}
// 判断当前节点的值是否小于其右子树中最小值
if (root->right != NULL && root->val >= root->right->val) {
return false;
}
// 判断右子树是否为二叉排序树
if (!isValidBST(root->right)) {
return false;
}
return true;
}
// 创建一棵二叉树
struct TreeNode* createBinaryTree() {
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 5;
root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->val = 3;
root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->left->val = 1;
root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->right->val = 4;
root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->val = 7;
root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->left->val = 6;
root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->right->val = 8;
return root;
}
int main() {
struct TreeNode* root = createBinaryTree();
if (isValidBST(root)) {
printf("给定的二叉树是二叉排序树\n");
} else {
printf("给定的二叉树不是二叉排序树\n");
}
return 0;
}
```
上面的程序中,我们使用了一个 `MAX_VALUE` 常量来表示一个足够大的数,它作为二叉树中的初始值。在判断二叉排序树的时候,我们把左右子树的最大值和最小值初始化为 `MAX_VALUE` 和 `-MAX_VALUE`,这样就可以保证判断过程中不会出现错误。
阅读全文