以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [分享][原创]DS第四章习题解答IsBST()函数的更正  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=57112)

--  作者：chenminyi
--  发布时间：12/23/2007 10:41:00 PM

--  [分享][原创]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;
}

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

--  作者：chenminyi
--  发布时间：12/24/2007 1:34:00 PM

--  
如觉得有错误的希望指正，免得误了他人
--  作者：hanshumin
--  发布时间：12/24/2007 5:19:00 PM

--  
我感觉习题解答没有错误。
  “这是不够的～因为其左子树可存在比根节点大的元素但仍满足习题解答的约束。”这句话好象有问题，因为只要是满足每个节点都比它的子节点小，则该节点比它的子子节点要小，依次递推，则不会出现你所说的那种情况。
--  作者：chenminyi
--  发布时间：12/24/2007 10:57:00 PM

--  
hanshumin请注意这不是堆，你说的情况是当树中的结点都是依次插入的时候才会之需要满足根与其子节点的关系，否则需要考虑根与其子树的关系

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

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

--  作者：buddha
--  发布时间：12/25/2007 12:53:00 PM

--  
这个对应的习题集勘误上有说明.
程序是不对的.
但是勘误中给出的判断是否是BST的方法是中序遍历是否有序的方法.
而不是按原思路在原来函数上的改进.
--  作者：buddha
--  发布时间：12/26/2007 12:39:00 PM

--  
以下是引用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;
}

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



我的看法．

--  作者：chenminyi
--  发布时间：12/26/2007 2:14:00 PM

--  
输的时候打字打错了
--  作者：buddha
--  发布时间：12/27/2007 12:47:00 PM

--  
以下是引用chenminyi在2007-12-26 14:14:00的发言：
输的时候打字打错了


:)
--  作者：zshao
--  发布时间：12/27/2007 10:49:00 PM

--  
buddha

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

--  作者：buddha
--  发布时间：12/28/2007 12:22:00 PM

--  
以下是引用zshao在2007-12-27 22:49:00的发言：
buddha

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



好象是DS的课程网站上应该有的.就是书的序言中带的哪个网站.
我现在登不上去.不知道为什么.
你如果能上去的话找找看看哈.
PS:我现在手头上也没有那东西。否则就给你传一个了。
--  作者：gradxixi
--  发布时间：12/28/2007 11:32:00 PM

--  
这有

http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=37311

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 85.938ms