9.31.c

来自「数据结构习题及答案」· C语言 代码 · 共 38 行

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);  
}