以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  关于BST的递归问题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=37692)

--  作者：msychailce
--  发布时间：9/7/2006 4:33:00 PM

--  关于BST的递归问题
题目要求"规定二叉搜索树中重复关键码插入在右子树中，写出从一棵有重复关键码的BST中删除一个关键码的递归算法"
我写了下面的算法,但是当删除之后或是无此结点时递归跳回上一级函继续遍历,直到所有结点遍历完,做了很多无用功.想删除或找不到结点时结束函数该如何实现呢?
请高手指教
template<class T>
void BinarySearchTree<T> Remove(T item,BinaryTreeNode<T> * root)
{
 if(root == NULL)
  return;
 else if(item == (root->value())
 {
  DeleteNode(root);        //书中删除算法
  if(root->rightchild())
  {
      BinaryTreeNode<T> * temp = root->rightchild();
      while((temp->leftchild())!=NULL)
       temp = temp->leftchild();
       if((temp->value()) == item)
    {
       DeleteNode(temp);
    return;
    }
       else return;
  }
  else return;
 }
 else if(item < (root->value()))
  root = root->leftchild();
 else
  root = root->rightchild();
}

--  作者：mxf3306
--  发布时间：9/7/2006 6:52:00 PM

--  
最简单的方法是用个标志位，如果一旦开始删除，就置位，如果判断位被置上并且节点值不符合的话就退出。
--  作者：mxf3306
--  发布时间：9/7/2006 6:53:00 PM

--  
还有就是找到结点后另用一个循环进行删除
--  作者：msychailce
--  发布时间：9/8/2006 8:50:00 AM

--  
嗯  加一个标志位返回时就可以一直return到根
看来我还是理解得不透啊
谢谢mxf3306兄
--  作者：Supremgoooo
--  发布时间：9/9/2006 10:37:00 PM

--  
递归？没看见呀！在哪？

以下是引用msychailce在2006-9-7 16:33:00的发言：
题目要求"规定二叉搜索树中重复关键码插入在右子树中，写出从一棵有重复关键码的BST中删除一个关键码的递归算法"
我写了下面的算法,但是当删除之后或是无此结点时递归跳回上一级函继续遍历,直到所有结点遍历完,做了很多无用功.想删除或找不到结点时结束函数该如何实现呢?
请高手指教
template<class T>
void BinarySearchTree<T> Remove(T item,BinaryTreeNode<T> * root)
{
  if(root == NULL)
   return;
  else if(item == (root->value())
  {
   DeleteNode(root);        //书中删除算法
   if(root->rightchild())
   {
       BinaryTreeNode<T> * temp = root->rightchild();
       while((temp->leftchild())!=NULL)
        temp = temp->leftchild();//这里显然少了root的右儿子      


if((temp->value()) == item)
     {
        DeleteNode(temp);
     return;
     }
        else return;
   }
   else return;
  }
  else if(item < (root->value()))
   root = root->leftchild();
  else
   root = root->rightchild();
}



--  作者：msychailce
--  发布时间：9/11/2006 9:03:00 AM

--  
sorry,笔误,最后两个else下应该是Remove(root->leftchild()) 和Remove(root->rightchild())
但是楼上加红的地方我不明白哪里错了,是删除重复结点,与root的右儿子有什么关系,不过我没考虑到有很多个重复的情况,应该加一循环
--  作者：msychailce
--  发布时间：9/11/2006 4:31:00 PM

--  
仔细想清楚了,这次应该对了.
template<class T>
void BinarySearchTree<T>::Remove(T item,Node<T> * root)
{
 if(root == NULL)
  return;
 if(item < root->value())
  Remove(root->leftchild());
 if(root->value() == item)
 {
  DeleteNode(root);
  Remove(root->rightchild());
 }
 if(item > root->value())
  Remove(root->rightchild());
}
看看自己发帖时写的程序实在很烂,真惭愧啊~~
--  作者：mxf3306
--  发布时间：9/11/2006 5:56:00 PM

--  
还有点小问题，参数不一致。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 62.500ms