判断一颗二叉树是否是二叉排序树（C/C++递归实现）

判断条件

对于一颗二叉树，若它中序遍历得到的数据是一个升序序列，那么它就是二叉排序树。

思路

在中序遍历递归函数的基础之上额外添加一个升序判断条件：对于中序遍历下的任意一个结点，若当前结点的数据大于上一个结点的数据，则该树为二叉排序树；否则不是。

代码

bool isBST(BT* root, int MAX)
{
	if (root == NULL) {//空树是二叉排序树 
		return true;
	}
	bool bst_l = isBST(root->lChild, MAX);//判断左子树是否为二叉排序树

	//当前节点的数据是否大于上一个结点的数据
	if (!bst_l || MAX >= root->data) {
		return false;//不是，则该树不为二叉排序树，返回false
	}
	MAX = root->data;//是，则刷新MAX的值，然后以此方式继续判断下一个结点

	return isBST(root->rChild, MAX);//判断右子树是否为二叉排序树
}

注：

1. C语言中没有“bool”类型，所以可以把int类型设为“0,1”来替代“true,false”。
2. 使用“INT_MIN”和“INT_MAX”需要额外引入<>头文件。