| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2832 人关注过本帖
标题:求后序遍历二叉线索树的算法
取消只看楼主 加入收藏
ffter2003
Rank: 1
来 自:HAINAN
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-11-25
收藏
 问题点数:0 回复次数:3 
求后序遍历二叉线索树的算法
参照以下的严蔚敏书上的中序遍历二叉线索树的类C程序,写一个后序遍历的算法,最好把代码贴出来,呵呵,先谢谢某位大虾了!
status inordertraverse(bithrtree T,status (*visit)(telemtype e))
{
p=T->lchild;
while(p!=T)
{
while(p->ltag==link)
p=p->lchild;
if(!visit(p->data))
return error;
while(p->rtag==thread && p->rchild !=T)
{
p=p->rchild;
visit(p->data);
}
p=p->rchild;
}
return ok;
}
搜索更多相关主题的帖子: 遍历 算法 线索 
2007-11-25 18:35
ffter2003
Rank: 1
来 自:HAINAN
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-11-25
收藏
得分:0 
先谢谢两位了,不过不符合我的题意,呵呵,missyou你写的是后续线索化的过程,chudl写的是遍历普通的二叉树,我要的是后序遍历后序线索二叉树,我在说明一下这里要用到栈,不过和遍历普通的二叉树的思路确不一样,请教高手指点。。。。。。
2007-12-07 18:45
ffter2003
Rank: 1
来 自:HAINAN
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-11-25
收藏
得分:0 
呵呵,感觉好像有点不对也,若从根出发访问到一个结点,其左孩子为thread(即空),而右孩子不空的话不因该先访问该结点,而还要去访问它的右子树
不过我想了下递归的算法你看看,储存结构改为三叉链表,其他不变
void postordertraverse(bithrtree &T,status (*visit)(telemtype e)) {
p=T->lchild;
while(p!=T)
{
  while(p->ltag==link) p=p->lchild;
  if(p->rtag==thread) visit(p->data);p=p->rchild;
  else
  {
     postordertraverse(p->rchild,visit);
     if(p->parent->rchild==p||p->parent->lchild==p&&p->parent->rtag==thread)
        {
           visit(p->parent->data);
           p=p->parent;
        }
      else if(p->parent->lchild==p&&p->parent->rtag==link)
           postordertraverse(p->parent->rchild,visit);
   }
}
}

[[italic] 本帖最后由 ffter2003 于 2007-12-8 01:25 编辑 [/italic]]
2007-12-08 01:18
ffter2003
Rank: 1
来 自:HAINAN
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-11-25
收藏
得分:0 
原帖由 [bold][underline]missiyou[/underline][/bold] 于 2007-12-10 20:49 发表 [url=http://bbs.][/url]
只要把p=stack[top];
              if(!visit(p->data))
return error;
放到,top--上面就可以了

还要改一处
就是在其后的else p->rchild; 加上stack[top]=p;top++;
好了,这个问题已基本解决,谢谢你!
2007-12-11 19:23
快速回复:求后序遍历二叉线索树的算法
数据加载中...
 
   



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

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