10
/
5 15 -------- binary tree (1)
/
6 20
那么，根据二叉搜索树的定义，可以想到一种暴力搜索的方法来判定二叉树是否为二叉搜索树。
假定当前结点值为k。则对于二叉树中每个结点，其左子树所有结点的值必须都小于k，其右子树所有结点的值都必须大于k。
暴力搜索算法代码如下，虽然效率不高，但是它确实能够完成工作。该解法最坏情况复杂度为O(n^2)，n为结点数目。（当所有结点都在一边的时候出现最坏情况）
/*判断左子树的结点值是否都小于val*/
bool isSubTreeLessThan(BinaryTree *p, int val)
{
if (!p) return true;
return (p->data < val &&
isSubTreeLessThan(p->left, val) &&
isSubTreeLessThan(p->right, val));
}
/*判断右子树的结点值是否都大于val*/
bool isSubTreeGreaterThan(BinaryTree *p, int val)
{
if (!p) return true;
return (p->data > val &&
isSubTreeGreaterThan(p->left, val) &&
isSubTreeGreaterThan(p->right, val));
}
/*判定二叉树是否是二叉搜索树*/
bool isBSTBruteForce(BinaryTree *p)
{
if (!p) return true;
return isSubTreeLessThan(p->left, p->data) &&
isSubTreeGreaterThan(p->right, p->data) &&
isBSTBruteForce(p->left) &&
isBSTBruteForce(p->right);
}
一个类似的解法是：对于结点node，判断其左子树最大值是否大于node的值，如果是，则该二叉树不是二叉搜索树。如果不是，则接着判断右子树最小值是否小于或等于node的值，如果是，则不是二叉搜索树。如果不是则接着递归判断左右子树是否是二叉搜索树。（代码中的maxValue和minValue函数功能分别是返回二叉树中的最大值和最小值，这里假定二叉树为二叉搜索树，实际返回的不一定是最大值和最小值）
