已知二叉树T采用二叉链表结构存储,每个结点有三个域:data、lchild、rchild,且二叉树T各结点的数据值均不相同。请设计一个算法判别该二叉树是否为二叉排序树,并简单说明判别方法,用C语言
时间: 2024-09-28 13:08:33 浏览: 48
为了判断一个给定的二叉树 T 是否为二叉排序树(BST),我们可以采用递归的方式遍历树节点。对于每一个节点,我们需要检查它是否满足以下条件:
1. 如果当前节点为空,则它是有效的。
2. 它的左子树所有节点的数据都小于当前节点的数据。
3. 它的右子树所有节点的数据都大于当前节点的数据。
这里是一个简单的 C 语言算法实现:
```c
// 假设有一个结构体 TreeNode,包含 data, lchild, rchild 的属性
typedef struct TreeNode {
int data;
struct TreeNode* lchild;
struct TreeNode* rchild;
} TreeNode;
int isBST(struct TreeNode* root) {
return helper(root, INT_MIN, INT_MAX);
}
int helper(struct TreeNode* node, int min, int max) {
if (node == NULL) {
// 空节点视为有效
return 1;
}
if (node->data < min || node->data > max) {
// 节点数据不在范围内,返回0表示无效
return 0;
}
// 递归检查左右子树
if (!helper(node->lchild, min, node->data - 1)) {
return 0; // 左子树不满足BST规则
}
if (!helper(node->rchild, node->data + 1, max)) {
return 0; // 右子树不满足BST规则
}
// 如果所有子树都通过检查,返回1
return 1;
}
```
阅读全文