ch09_ex31 判定给定二叉树是…

9.31④  试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。
实现下列函数：Status IsBSTree(BiTree t);
二叉树的类型BiTree定义如下：typedef struct {    KeyType key;     ... ...  // 其他数据域} ElemType;
typedef struct BiTNode {    ElemType data;    BiTNode *lchild,*rchild;}BiTNode, *BiTree;
答案以及解析：void BSTree(BiTree t,int &flag,int &last);//声明Status IsBSTree(BiTree t){    int flag = 1;    int last =0;   BSTree(t,flag,last);    return flag;}
void BSTree(BiTree t,int &flag,int&last)//取地址不需要返回值{   if(t->lchild&&flag)BSTree(t->lchild,flag,last);//遍历左子树    if(t->data.key    last =t->data.key;//last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，让后开始向上反馈key   if(t->rchild&&flag)BSTree(t->rchild,flag,last);}