试写一个判别给定二叉树是否为二叉排序树的算法。用C语言
时间: 2024-01-14 09:06:51 浏览: 108
以下是一个简单的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函数中构造了一个二叉树,并判断其是否为二叉排序树。
阅读全文