算法解析

根据二叉排序树的定义，对二叉树进行递归遍历，左子树关键字比根结点关键字小，右子树的关键字比根结点的关键字大，一旦有不满足条件则可判断不是二叉排序树。通过参数 flag 的值来判断，flag 为 1 表示是二叉排序树，为 0 则表示非二叉排序树，flag 初值为 1。设定全局变量 pre(初始值为 NULL)来指向遍历过程结点的前驱。

代码

void JudgeBST(BiTree T, int &flag)
{
//判断二叉树是否为二叉排序树
	if(T != NULL && flag)
	{
		JudgeBST(T->lchild, flag); //中序遍历左子树
		if(pre == NULL) //中序遍历的第一个结点不必判断
			pre = T;
		else if(pre->data < T->data)
			pre = T; //前驱指针指向当前结点
		else flag = 0; //不是二叉排序树
		JudgeBST(T->rchild, flag); //中序遍历右子树
	}
}

思路2

对二叉排序树来说，其中序遍历序列为一个递增有序序列，因此，对
给定的二叉树进行中序遍历，如果始终能保持前一个值比后一个值小，则说明该二叉树是一棵二叉排序树，算法如下。

代码

KeyType predt=-32767; //predt为全局变量，保存当前节点中序前驱的值，初值为
-∞
int judgeBST(BSTNode *bt)
{
	int b1, b2;
	if (bt==NULL) //空树是一棵二叉排序树
		return 1;
	else
	{
		b1=judgeBST (bt->lchild); //判断左子树
		if(b1==0ll predt>=bt->key)
			return 0;
		predt=bt->key; //保存当前节点的关键字
		b2=judgeBST (bt->rchild); //判断右子树
		return b2;
	}
}