新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     >>计算机科学论坛<<     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → [分享][原创]DS第四章习题解答IsBST()函数的更正 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 9670 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [分享][原创]DS第四章习题解答IsBST()函数的更正 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客楼主
    发贴心情 [分享][原创]DS第四章习题解答IsBST()函数的更正

    第四章习题解答中的判断二叉搜索树的函数IsBST仅仅只比较各节点与其子节点的大小关系，这是不够的～因为其左子树可存在比根节点大的元素但仍满足习题解答的约束。下面是我的程序，暂时没上机验证，树的验证输入比较麻烦。
    bool IsBST(TreeNode<T>* root, T& min, T& max)
    {
                                                         //min，max分别是root为根的子树的最小值和最大值
         if(root == NULL) return true;       //空树必是BST
         T lmax, rmin;                             //lmax为左子树的最小值，rmin为右子树最小值
          min = max = root->value();       //以root为根的子树的最小最大值初始化为树根的值
          bool lb = IsBST(root->LeftChild, min, lmax);       //递归计算左子树
          bool rb = IsBST(root->RightChild, rmin, max);    //递归计算右子树
          return lb && rb && root->value()>lmax && root->value()<rmin;
    }

    其中子树最小值的计算由其左子树完成，最大值的计算由右子树完成。


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/23 22:41:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第2楼
    发贴心情 
    如觉得有错误的希望指正，免得误了他人
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/24 13:34:00
     
     hanshumin 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究汇编)
      文章：37
      积分：238
      门派：XML.ORG.CN
      注册：2007/3/24

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给hanshumin发送一个短消息 把hanshumin加入好友 查看hanshumin的个人资料 搜索hanshumin在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看hanshumin的博客第3楼
    发贴心情 
    我感觉习题解答没有错误。
      “这是不够的～因为其左子树可存在比根节点大的元素但仍满足习题解答的约束。”这句话好象有问题，因为只要是满足每个节点都比它的子节点小，则该节点比它的子子节点要小，依次递推，则不会出现你所说的那种情况。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/24 17:19:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第4楼
    发贴心情 
    hanshumin请注意这不是堆，你说的情况是当树中的结点都是依次插入的时候才会之需要满足根与其子节点的关系，否则需要考虑根与其子树的关系

    我来举个例子：
    v1          8
    v2     7
    v3          4
    v4 6
    v5          7
    v6     5
    v7          3

    v4为根，v2和v6是子树的根～很显然可见该树不是二叉搜索树，但是各节点满足与其孩子之间的关系：左孩子<结点<右孩子

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/24 22:57:00
     
     buddha 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(每天看1小时莱昂氏)
      文章：164
      积分：1022
      门派：XML.ORG.CN
      注册：2006/5/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给buddha发送一个短消息 把buddha加入好友 查看buddha的个人资料 搜索buddha在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看buddha的博客第5楼
    发贴心情 
    这个对应的习题集勘误上有说明.
    程序是不对的.
    但是勘误中给出的判断是否是BST的方法是中序遍历是否有序的方法.
    而不是按原思路在原来函数上的改进.
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/25 12:53:00
     
     buddha 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(每天看1小时莱昂氏)
      文章：164
      积分：1022
      门派：XML.ORG.CN
      注册：2006/5/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给buddha发送一个短消息 把buddha加入好友 查看buddha的个人资料 搜索buddha在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看buddha的博客第6楼
    发贴心情 
    以下是引用chenminyi在2007-12-23 22:41:00的发言：
    第四章习题解答中的判断二叉搜索树的函数IsBST仅仅只比较各节点与其子节点的大小关系，这是不够的～因为其左子树可存在比根节点大的元素但仍满足习题解答的约束。下面是我的程序，暂时没上机验证，树的验证输入比较麻烦。
    bool IsBST(TreeNode<T>* root, T& min, T& max)
    {
                                                          //min，max分别是root为根的子树的最小值和最大值
          if(root == NULL) return true;       //空树必是BST
          T lmax, rmin;                             //lmax为左子树的最大值，rmin为右子树最小值
           rmin = lmax = root->value();       //以root为根的子树的最小最大值初始化为树根的值
           bool lb = IsBST(root->LeftChild, min, lmax);       //递归计算左子树
           bool rb = IsBST(root->RightChild, rmin, max);    //递归计算右子树
           return lb && rb && root->value()>lmax && root->value()<rmin;
    }

    其中子树最小值的计算由其左子树完成，最大值的计算由右子树完成。



    我的看法．
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/26 12:39:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第7楼
    发贴心情 
    输的时候打字打错了
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/26 14:14:00
     
     buddha 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(每天看1小时莱昂氏)
      文章：164
      积分：1022
      门派：XML.ORG.CN
      注册：2006/5/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给buddha发送一个短消息 把buddha加入好友 查看buddha的个人资料 搜索buddha在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看buddha的博客第8楼
    发贴心情 
    以下是引用chenminyi在2007-12-26 14:14:00的发言：
    输的时候打字打错了


    :)
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/27 12:47:00
     
     zshao 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(要不要学学XML呢?)
      文章：145
      积分：684
      门派：XML.ORG.CN
      注册：2007/4/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给zshao发送一个短消息 把zshao加入好友 查看zshao的个人资料 搜索zshao在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看zshao的博客第9楼
    发贴心情 
    buddha

    习题集勘误上，哪里有下载？
    谢谢

    ----------------------------------------------
    PLEASE BLESS ME ,MY GOD.

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/27 22:49:00
     
     buddha 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(每天看1小时莱昂氏)
      文章：164
      积分：1022
      门派：XML.ORG.CN
      注册：2006/5/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给buddha发送一个短消息 把buddha加入好友 查看buddha的个人资料 搜索buddha在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看buddha的博客第10楼
    发贴心情 
    以下是引用zshao在2007-12-27 22:49:00的发言：
    buddha

    习题集勘误上，哪里有下载？
    谢谢



    好象是DS的课程网站上应该有的.就是书的序言中带的哪个网站.
    我现在登不上去.不知道为什么.
    你如果能上去的话找找看看哈.
    PS:我现在手头上也没有那东西。否则就给你传一个了。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/28 12:22:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/3 12:59:49

    本主题贴数11，分页： [1] [2]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 105.469ms