编程论坛 → 数据结构与算法

设计判断一棵二叉树是否为二叉搜索树的算法

小小哥发布于 2011-01-04 10:56， 1517 次点击

实在没什么思路，只是感觉，用递归会好点，求高手

8 回复

buffer2011-01-04 12:00

没错，就是用递归

程序代码：

bool isBST(struct tree *root)
{
    if (root == NULL)
        return true;
    if (isBST(root->left) && isBST(root->right))
        return (root->left == NULL ? true : (root->left->v < root->v))
                && (root->right == NULL ? true : (root->v < root->right->v));
}

buffer2011-01-04 12:22

回复 2楼 buffer

呃。。不对，上面的方法是错的

buffer2011-01-04 12:46

这个应该是对的了

程序代码：

bool isBST(struct tree *root)
{
    static int preV = INT_MIN;
    if (root == NULL)
        return true;
    isBST(root->left);
    if (root->v > preV)
        preV = root->v;
    else
        return false;
    isBST(root->right);
}

小小哥2011-01-04 12:48

回复 2楼 buffer

代码很精辟，我也这么想过，但是：如果某结点的右孩子的左孩子比该结点大的话，这个算法貌似检测不出来啊~~

buffer2011-01-04 12:50

回复 5楼小小哥

请看4楼，算法改了。。。

小小哥2011-01-04 12:53

回复 4楼 buffer

恩，这个我感觉也没错，灰常感谢，给分

buffer2011-01-04 13:08

不对，这样才是对的

程序代码：

bool isBST(struct tree *root)
{
    static int preV = INT_MIN;
    if (root == NULL)
        return true;
    if (!isBST(root->left))
        return false;
    if (root->v > preV)
        preV = root->v;
    else
        return false;
    isBST(root->right);
}

小小哥2011-01-04 14:13

回复 8楼 buffer

好吧……感谢……