| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2832 人关注过本帖
标题:求后序遍历二叉线索树的算法
只看楼主 加入收藏
ffter2003
Rank: 1
来 自:HAINAN
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-11-25
收藏
 问题点数:0 回复次数:11 
求后序遍历二叉线索树的算法
参照以下的严蔚敏书上的中序遍历二叉线索树的类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
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
void postbitree(Bitree T)
{
   if(T)
{ postbitree(T->lchild);
  postbitree(T->rchild);
 if(!T->lchild)
 {T->lchild=Thread; T->lchild=pre;}
if(!T->rchild)
{T->rchild=Thread; pre->rchild=T;}
pre=T;
}
}
也不知道对不对,
   
}
2007-11-27 21:49
chudl
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2007-10-28
收藏
得分:0 
template <class T>
void BinaryTree<T>::PreOrder(void(*Visit)(BinaryTreeNode<T> *u),BinaryTreeNode<T> *t){
    if (t)
    {Visit(t);
    PreOrder(Visit,t->LeftChild);
    PreOrder(Visit,t->RightChild);
    }
}
template<class T>
void visit(BinaryTree<T> *a){
cout<<a.data<<"  ";
}
2007-11-30 21:11
ffter2003
Rank: 1
来 自:HAINAN
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-11-25
收藏
得分:0 
先谢谢两位了,不过不符合我的题意,呵呵,missyou你写的是后续线索化的过程,chudl写的是遍历普通的二叉树,我要的是后序遍历后序线索二叉树,我在说明一下这里要用到栈,不过和遍历普通的二叉树的思路确不一样,请教高手指点。。。。。。
2007-12-07 18:45
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
哦这样呀,感觉,不是有二个标志呀,LINK,Thead 条件,从头开始,如果是Thead,输出,
status inordertraverse(bithrtree T,status (*visit)(telemtype e))
{
p=T->lchild; ///////////bitree stack[];int top=0; stack[top]=T;top++
while(p!=T)
{
while(p->ltag!=thread;)
{stack[top]=p;top++;

p=p->lchild;}

p=stack[top];
              if(!visit(p->data))
return error;

if(p->rtag==thread && p->rchild !=T)
{
  top--;
}
else
{ p=p->rchild;
}
}
return ok;
}
好了,感觉是这样吧,呵呵,你在看看吧

[[italic] 本帖最后由 missiyou 于 2007-12-7 22:10 编辑 [/italic]]
2007-12-07 22:08
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
觉得还普通遍历也差不多呀,
2007-12-07 22:13
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
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
只要把p=stack[top];
              if(!visit(p->data))
return error;
放到,top--上面就可以了
2007-12-10 20:49
zxc1998
Rank: 1
等 级:新手上路
威 望:1
帖 子:133
专家分:0
注 册:2007-3-21
收藏
得分:0 
这个算法好像用的不多,走过看一下。
2007-12-10 21:30
deepseep
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2007-12-3
收藏
得分:0 
void PostOrder(Tree T)
{
    if(T==NULL)
        return;
    else
    {
        PostOrder(T->left);
        PostOrder(T->right);
        printf("%d\t",T->date);   
    }     
}

坚持自己的原则,充满希望和乐观。
2007-12-11 09:23
快速回复:求后序遍历二叉线索树的算法
数据加载中...
 
   



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

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