9.31.c

部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)严蔚敏版的课后习题答案.专门提供给在anyview上运行,全部为通告代码

9.31④  试写一个判别给定二叉树是否为二叉排序树
的算法，设此二叉树以二叉链表作存储结构。且树中
结点的关键字均不同。

实现下列函数：
Status IsBSTree(BiTree t);
/* 判别给定二叉树t是否为二叉排序树。*/
/* 若是，则返回TRUE，否则FALSE      */

二叉树的类型BiTree定义如下：
typedef struct {
    KeyType key;  
    ... ...   // 其他数据域
} ElemType;

typedef struct BiTNode {
    ElemType data;
    BiTNode  *lchild,*rchild;
}BiTNode, *BiTree;
void BSTree(BiTree t,int &last,int &flag);
Status IsBSTree(BiTree t)
/* 判别给定二叉树t是否为二叉排序树。*/
/* 若是，则返回TRUE，否则FALSE      */
{ 
 int last=0;
 int flag=1;
 BSTree(t,last,flag);
 return flag ;
}
void BSTree(BiTree t,int &last,int &flag)
{
  if(t->lchild&&flag) BSTree(t->lchild,last,flag);
  if(t->data.key<last) flag=0;                          //与其中序前驱相比较
  last=t->data.key;
  if(t->rchild&&flag) BSTree(t->rchild,last,flag);  
}