中文XML论坛--关于BST的递归问题

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> 研友的交流园地，讨论关于计算机考研的方方面面。

[返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『计算机考研交流』 → 关于BST的递归问题

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 3008 个阅读者　　

*	贴子主题：关于BST的递归问题	举报打印推荐 IE收藏夹
	本主题类别:

msychailce

  等级：大一(高数修炼中)
  文章：15
  积分：166
  门派：XML.ORG.CN
  注册：2006/8/13

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	楼主

关于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();
}

   收藏   分享
顶(0)

2006/9/7 16:33:00

mxf3306

  等级：大三(研究MFC有点眉目了!)
  文章：112
  积分：823
  门派：XML.ORG.CN
  注册：2006/7/6

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第2楼

最简单的方法是用个标志位，如果一旦开始删除，就置位，如果判断位被置上并且节点值不符合的话就退出。

2006/9/7 18:52:00

mxf3306

  等级：大三(研究MFC有点眉目了!)
  文章：112
  积分：823
  门派：XML.ORG.CN
  注册：2006/7/6

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第3楼

还有就是找到结点后另用一个循环进行删除

2006/9/7 18:53:00

msychailce

  等级：大一(高数修炼中)
  文章：15
  积分：166
  门派：XML.ORG.CN
  注册：2006/8/13

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第4楼

嗯加一个标志位返回时就可以一直return到根
看来我还是理解得不透啊
谢谢mxf3306兄

2006/9/8 8:50:00

Supremgoooo

  等级：大四下学期(考上研究生啦!)
  文章：201
  积分：1872
  门派：XML.ORG.CN
  注册：2006/4/9

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第5楼

递归？没看见呀！在哪？

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

2006/9/9 22:37:00

msychailce

  等级：大一(高数修炼中)
  文章：15
  积分：166
  门派：XML.ORG.CN
  注册：2006/8/13

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第6楼

sorry,笔误,最后两个else下应该是Remove(root->leftchild()) 和Remove(root->rightchild())
但是楼上加红的地方我不明白哪里错了,是删除重复结点,与root的右儿子有什么关系,不过我没考虑到有很多个重复的情况,应该加一循环

2006/9/11 9:03:00

msychailce

  等级：大一(高数修炼中)
  文章：15
  积分：166
  门派：XML.ORG.CN
  注册：2006/8/13

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第7楼

仔细想清楚了,这次应该对了.
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());
}
看看自己发帖时写的程序实在很烂,真惭愧啊~~

2006/9/11 16:31:00

mxf3306

  等级：大三(研究MFC有点眉目了!)
  文章：112
  积分：823
  门派：XML.ORG.CN
  注册：2006/7/6

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第8楼

还有点小问题，参数不一致。

2006/9/11 17:56:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2025/10/4 4:07:02

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

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


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