用c语言编写一个函数实现判定二叉树是否为二叉排序树,status JudgeBiTree(BiTree T)
时间: 2024-01-16 10:02:38 浏览: 123
好的,我来为您编写这个函数。
首先,需要明确二叉排序树的定义:对于任意一个节点,它的左子树中所有的节点的值都小于该节点的值,它的右子树中所有节点的值都大于该节点的值。
那么,我们可以采用递归的方式来判断一棵二叉树是否为二叉排序树。对于每一个节点,递归判断其左子树和右子树是否为二叉排序树,并且判断左子树中所有节点的值是否小于该节点的值,右子树中所有节点的值是否大于该节点的值。具体实现如下:
```
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 判断二叉树是否为二叉排序树
// 返回值:1表示是二叉排序树,0表示不是二叉排序树
int JudgeBiTree(BiTree T) {
if (T == NULL) {
return 1;
}
// 判断左子树是否为二叉排序树
if (!JudgeBiTree(T->lchild)) {
return 0;
}
// 判断右子树是否为二叉排序树
if (!JudgeBiTree(T->rchild)) {
return 0;
}
// 判断左子树中所有节点的值是否小于该节点的值
if (T->lchild != NULL) {
BiTree p = T->lchild;
while (p->rchild != NULL) {
p = p->rchild;
}
if (p->data >= T->data) {
return 0;
}
}
// 判断右子树中所有节点的值是否大于该节点的值
if (T->rchild != NULL) {
BiTree p = T->rchild;
while (p->lchild != NULL) {
p = p->lchild;
}
if (p->data <= T->data) {
return 0;
}
}
return 1;
}
```
希望这个函数能够帮到您!
阅读全文