前两天写过一篇博文《二叉搜索树基本操作实现》，为了更深入了解二叉搜索树的性质，本文实现判断一棵树是否为二叉搜索树算法。

 

二叉搜索树的性质：

任意节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。

构造二叉树的节点定义为：

struct TreeNode{    int data;    TreeNode *left;    TreeNode *right;};

 

方法1 (错误)

对每一个节点，检测其值是否大于左子树节点，是否小于右子树节点。思路很简单，代码实现如下：

bool isBST(TreeNode* root){    if (root == NULL)        return true;    if (root->left != NULL && root->left->data> root->data)        return false;    if (root->right != NULL && root->right->data < root->data)        return false;    if (!isBST(root->left) || !isBST(root->right))        return false;    return true;}

但是，这种方法是错误的，如下面例子，节点4大于根节点3，但上面函数检测这棵树是BST。

               3

            /      \

          2         5

       /     \

    1         4

 

 

方法2 

对每个节点，检测其值是否大于左子树的最大值，是否小于右子树的最小值。思路正确，但效率较低，代码实现如下：

int maxValue(TreeNode *root){    int max = root->data;    if(root->left != NULL)    {        int maxLeft = maxValue(root->left);        max = max > maxLeft ? max : maxLeft;    }    if(root->right != NULL)    {        int maxRight = maxValue(root->right);        max = max > maxRight ? max : maxRight;    }    return max;}int minValue(TreeNode *root){    int min = root->data;    if(root->left != NULL)    {        int minLeft = maxValue(root->left);        min = min > minLeft ? min : minLeft;    }    if(root->right != NULL)    {        int minRight = maxValue(root->right);        min = min > minRight ? min : min;    }    return min;}bool isBST(TreeNode *root){    if(root == NULL)        return true;    if(root->left != NULL && maxValue(root->left) > root->data)        return false;    if(root->right != NULL && minValue(root->right) < root->data)        return false;    return isBST(root->left) && isBST(root->right);}

其中，maxValue及minValue函数，分别返回一棵非空二叉树的最大值和最小值。

 

方法3

方法2需要重复遍历树中的部分数据，故效率较低，如果只需每个节点遍历一次，那么效率将大大提高。方法3的巧妙之处在于限定了子树节点的值得范围，从而每个节点只需遍历一次。节点值的初始范围可限定为TNT_MIN以及TNT_MAX。代码实现如下：

bool isBSTUtil(TreeNode *root, int min, int max){    if(root == NULL)        return true;    if(root->data < min || root->data > max)        return false;    return isBSTUtil(root->left, min, root->data - 1) && isBSTUtil(root->right, root->data + 1, max);}bool isBST(TreeNode *root){    return isBST02(root, INT_MIN, INT_MAX);}

 

方法4

使用中序遍历的方法实现：

1）对树进行中序遍历，将结果保存在temp数组中；

2）检测temp数组是否为升序排列，如果是，则为BST，反之则不是。

此方法还可以进一步的优化，不用temp数组，避免使用额外的内存开销。在中序遍历时使用静态变量保存前驱节点，如果当前节点小于前驱节点，则该树不是BST。代码实现如下：

//中序遍历的方法实现bool isBST(TreeNode *root){    static TreeNode *prev;    if(root != NULL)    {        if(!isBST(root->left))            return false;        if(prev != NULL && root->data < prev->data)            return false;        prev = root;        if(!isBST(root->right))            return false;    }    return true;}

二叉搜索树的判断是一个重要的算法，个人认为该算法的实现在考研或找工作中都非常重要，从这个算法可以考核到对二叉树特别是二叉搜索树的特性的了解。所以掌握好这个算法的思想和实现时非常必要的。

 

本文参考于https://www.2cto.com/kf/201506/408372.html，只是在其基础上加上自己的一些见解，谢谢原作者。