[数据结构与算法]判断二叉树(21.6.22)

题目描述：

给定一棵二叉树，设计一个算法判断该二叉树是否为二叉排序树。

算法思路：

对二叉排序树来说，其中序遍历序列是一个有序的递增序列，因此，对给定的二叉树进行中序遍历，若能保证是一个递增有序序列则说明二叉树是一个二叉排序树。

代码如下：

KeyType predt=-32767; //predt为全局变量，记录当前结点中序前驱的值，初值为负无穷 
int Judge(BiTree bt){
	int b1,b2;
	if(bt==NULL) return 1; //空树 
	else{
		b1=Judge(bt->lchild); //判断左子树是否为二叉排序树 
		if(b1==0 || predt >= bt->data) //若左子树返回值为0或者前驱大于等于当前结点 
			return 0;
		predt=bt->data;  //保存当前结点的关键字 
		b2=Judge(bt->rchild);
		return b2;
	
	}
}