//
typedef struct BiTNode{
	int data; // 为简便起见，这里的data就是key
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

#define MAXKEY 1000
#define MINKEY -1
/*************************************************************************
 * 功能：判断一棵二叉树是否是二叉排序树
 * 算法思想：基于二叉排序树的递归定义
 * 输入：T - 指向当前二叉树的根节点
 * 输出：返回值
 * 					TRUE- T所指向的二叉树是二叉排序树；
 *					FALSE-T所指向的二叉树不是二叉排序树；
 *				maxkey: 当返回值为TRUE时，放的是T所指向的二叉树中各关键字的最大值
 *				minkey: 当返回值为TRUE时，放的是T所指向的二叉树中各关键字的最小值
 **************************************************************************/
Status isBSTree1(BiTree T, int &maxkey, int &minkey )
{
	if (!T){	// T为空树时，直接求解
		maxkey = MAXKEY; minkey = MINKEY;
		return TRUE;
	}
	lret = isBSTree1(T->lchild, lmaxkey, lminkey);
	if (lret==FALSE)	// 左子树不为二叉排序树，则T不为二叉排序树
		return FALSE;
	rret = isBSTree1(T->rchild, rmaxkey, rminkey);
	if (rret==FALSE)	// 右子树不为二叉排序树，则T不为二叉排序树
		return FALSE;
	// 左、右子树均为二叉排序树
	maxkey = max(lmaxkey, T->data, rmaxkey);	//max是求三个数中的最大值
	minkey = min(lminkey, T->data, rminkey);	//min是求三个数中的最小值
	if ( T->data < lmaxkey || T->data > rminkey )	
		return FALSE;
	return TRUE;
}

/*************************************************************************
 * 功能：判断一棵二叉树是否是二叉排序树
 * 算法思想：基于二叉排序树的性质（中序遍历序列按值有序）
 * 输入：T - 指向当前二叉树的根节点
 * 输出：返回值
 * 					TRUE- T所指向的二叉树是二叉排序树；
 *					FALSE-T所指向的二叉树不是二叉排序树；
 *	pre: 保存上次访问的节点的指针
 **************************************************************************/
Status isBSTree2(BiTree T, BiTree &pre)
{
	if (!T)	// T为空树时，直接求解
		return TRUE;
	if ( isBSTree2(T->lchild, pre)==FALSE )
		return FALSE;
	if ( pre!=NULL && pre->data > T->data )	// 出现反序
		return FALSE;
	pre = T;
	return isBSTree2(T->rchild, pre);
}