| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1517 人关注过本帖
标题:设计判断一棵二叉树是否为二叉搜索树的算法
只看楼主 加入收藏
小小哥
Rank: 4
等 级:业余侠客
帖 子:139
专家分:224
注 册:2010-11-28
结帖率:75%
收藏
已结贴  问题点数:20 回复次数:8 
设计判断一棵二叉树是否为二叉搜索树的算法
实在没什么思路,只是感觉,用递归会好点,求高手
搜索更多相关主题的帖子: 二叉树 
2011-01-04 10:56
buffer
Rank: 5Rank: 5
等 级:职业侠客
帖 子:73
专家分:326
注 册:2010-12-31
收藏
得分:20 
没错,就是用递归
程序代码:
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));
}
2011-01-04 12:00
buffer
Rank: 5Rank: 5
等 级:职业侠客
帖 子:73
专家分:326
注 册:2010-12-31
收藏
得分:0 
回复 2楼 buffer
呃。。不对,上面的方法是错的
2011-01-04 12:22
buffer
Rank: 5Rank: 5
等 级:职业侠客
帖 子:73
专家分:326
注 册:2010-12-31
收藏
得分:0 
这个应该是对的了
程序代码:
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:46
小小哥
Rank: 4
等 级:业余侠客
帖 子:139
专家分:224
注 册:2010-11-28
收藏
得分:0 
回复 2楼 buffer
代码很精辟,我也这么想过,但是:如果某结点的右孩子的左孩子比该结点大的话,这个算法貌似检测不出来 啊~~
2011-01-04 12:48
buffer
Rank: 5Rank: 5
等 级:职业侠客
帖 子:73
专家分:326
注 册:2010-12-31
收藏
得分:0 
回复 5楼 小小哥
请看4楼,算法改了。。。
2011-01-04 12:50
小小哥
Rank: 4
等 级:业余侠客
帖 子:139
专家分:224
注 册:2010-11-28
收藏
得分:0 
回复 4楼 buffer
恩,这个我感觉也没错,灰常感谢,给分
2011-01-04 12:53
buffer
Rank: 5Rank: 5
等 级:职业侠客
帖 子:73
专家分:326
注 册:2010-12-31
收藏
得分:0 
不对,这样才是对的
程序代码:
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 13:08
小小哥
Rank: 4
等 级:业余侠客
帖 子:139
专家分:224
注 册:2010-11-28
收藏
得分:0 
回复 8楼 buffer
好吧……感谢……
2011-01-04 14:13
快速回复:设计判断一棵二叉树是否为二叉搜索树的算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.058145 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved