用c语言编写一个函数实现判定二叉树是否为二叉排序树,status JudgeBiTree(BiTree T),typedef int status; typedef int KeyType; typedef struct { KeyType key; char others[20]; } TElemType; //二叉树结点类型定义 typedef struct BiTNode{ //二叉链表结点的定义 TElemType data; struct BiTNode *lchild,*rchild; }
时间: 2024-02-05 14:05:12 浏览: 91
C语言判定一棵二叉树是否为二叉搜索树的方法分析
5星 · 资源好评率100%
好的,根据您的要求,我已经为您编写了一个判定二叉树是否为二叉排序树的函数,代码如下:
```
typedef int status;
typedef int KeyType;
typedef struct {
KeyType key;
char others[20];
} TElemType;
// 二叉树结点类型定义
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 判断以T为根的二叉树是否为二叉排序树
// 返回值:1表示是二叉排序树,0表示不是二叉排序树
int JudgeBST(BiTree T, int min, int max) {
if (T == NULL) {
return 1;
}
// 判断左子树是否为二叉排序树
if (!JudgeBST(T->lchild, min, T->data.key)) {
return 0;
}
// 判断右子树是否为二叉排序树
if (!JudgeBST(T->rchild, T->data.key, max)) {
return 0;
}
// 判断当前节点是否满足二叉排序树的条件
if (T->data.key <= min || T->data.key >= max) {
return 0;
}
return 1;
}
// 判断二叉树是否为二叉排序树
// 返回值:1表示是二叉排序树,0表示不是二叉排序树
int JudgeBiTree(BiTree T) {
return JudgeBST(T, INT_MIN, INT_MAX);
}
```
这个函数的实现采用了递归的方式,对于每一个节点,递归判断其左子树和右子树是否为二叉排序树,并且判断当前节点是否满足二叉排序树的条件(即其左子树中所有节点的值都小于该节点的值,右子树中所有节点的值都大于该节点的值)。
希望这个函数能够帮到您!
阅读全文