判别给定二叉树,是否为二叉树?设此二叉树以二叉列表为存储结构。且树中结点的关键字不同。C语言编程
时间: 2024-01-23 09:17:10 浏览: 80
判断给定的二叉树是否为二叉查找树,可以按照以下步骤进行:
1. 对于二叉树中的每个结点,检查其左子树中的所有结点的关键字是否小于该结点的关键字,右子树中的所有结点的关键字是否大于该结点的关键字。
2. 如果步骤1中的检查全部通过,则该树为二叉查找树,否则不是。
下面是基于上述思路的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //bool类型头文件
//定义二叉树结点类型
typedef struct BiTNode {
int data;
struct BiTNode* lchild;
struct BiTNode* rchild;
}BiTNode, * BiTree;
//创建二叉树
void CreateBiTree(BiTree* T) {
int data;
scanf_s("%d", &data);
if (data == 0) {
*T = NULL;
}
else {
*T = (BiTNode*)malloc(sizeof(BiTNode));
(*T)->data = data;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
//判断是否为二叉查找树
bool IsBST(BiTree T, int min, int max) {
if (T == NULL) {
return true;
}
if (T->data < min || T->data > max) {
return false;
}
return IsBST(T->lchild, min, T->data - 1) && IsBST(T->rchild, T->data + 1, max);
}
int main() {
BiTree T;
printf("请按前序遍历输入二叉树结点的值,0表示空结点:\n");
CreateBiTree(&T);
if (IsBST(T, INT_MIN, INT_MAX)) {
printf("该二叉树是二叉查找树。\n");
}
else {
printf("该二叉树不是二叉查找树。\n");
}
return 0;
}
```
注:上述代码中使用了bool类型,需要在头文件中包含stdbool.h。INT_MIN和INT_MAX是C语言中定义的int类型的最小值和最大值。
阅读全文