二叉树后序遍历线索树的问题

菜鸟飞呀飞

.................f
.............../ \
.............d....e
............/ \
...........a...c
.................\
..................b

后序遍历线索树顺序是a b c d e f，a线索b，b线索c，c如何前进到d？

converse

不明白你什么意思，后序不就是递归遍历左子树，然后递归遍历右子树，最后访问根结点吗？所以c是d的右子树的根结点，所以访问完c后就是遍历右子树结束了，然后就访问根结点了，明白？

菜鸟飞呀飞

[quote]原帖由 "converse"]不明白你什么意思，后序不就是递归遍历左子树，然后递归遍历右子树，最后访问根结点吗？所以c是d的右子树的根结点，所以访问完c后就是遍历右子树结束了，然后就访问根结点了，明白？[/quote 发表：


我的意思是二叉树使用线索后序遍历，结点成员为 lchild,ltag,data,rtag,rchild

另外下面是严蔚敏书上的中序遍历二叉线索树的类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;
}

aero

C的右指针已经被占用作为右孩子了，那么C就没有后线索了，很正常。

线索二叉树只实尽量利用左右两个指针，尽量不要NULL存在。如果指针被孩子占用，没有线索也是应该的。

菜鸟飞呀飞

C的右指针已经被占用作为右孩子了，那么C就没有后线索了，很正常。

线索二叉树只实尽量利用左右两个指针，尽量不要NULL存在。如果指针被孩子占用，没有线索也是应该的。

--------------------
我的问题正是因为c没有了后继线索如何前进到d呢，请高人指点实现类似上面的中序遍历二叉线索树的后序遍历线索树。
这不是作业题，只是小弟自学时遇到的问题。
谢谢！

aero

用栈啊，用递归方法举例，f递归到d，d递归到a，开始线索，线索到c结束，正好返回到d（这步没有线索，但是函数直接返回就到了），d返回f，f继续调用e，e线索到f结束。

树，本身就是可历遍的。线索不过是为了提高效率的一种辅助手段。比如此例中。a线索到d、d线索到c的过程中，由于线索的存在，就少了pop、push、push、pop、pop这5个步骤，效率有所提高。

菜鸟飞呀飞

明白！

resume

...............f
............../ \
.............d...e
............/ \
...........a...c
........../.....\
。。。e.......b

有个问题啊，e->;a、a->;b、b->;c，如果递归怎么控制从e返回d呢，按我思路想好像很复杂呀。哈哈，最好给段代码看看
楼主这道题做出来了吗，把代码贴出来

菜鸟飞呀飞

利用栈遍历后序遍历后继线索二叉树算法如下
status PostOrderTraverse(ThreadedTree &T)
{
Stack S;p=T;InitStack(S);
if(!p->;ltag&&!p->;rtag)
{
visit(p->;data);
return;
}//T为独顶树
while(!p->;ltag││!p->;rtag)//p非叶子节点
{
if(!p->;ltag) p=p->;lchild;else p=p->;rchild;
Push(S,p);
}//找到后序遍历的第一个节点并记录父节点信息
visit(p->;data);
while(!StackEmpty(S))
{
Pop(S,q);
if(q==T) visit(q->;data);//弹出的为树根，直接访问
if(q->;rtag==Thread)&&(p==q->;lchild)//从左树返回根节点，没有右子树，则后继为根结点
{
p=q;
visit(p->;data);
}
if(q->;rtag!=Thread)&&(p==q->;rchild)//从右树返回根结点，后继为根节点
{
p=q;
visit(p->;data);
}
if(q->;rtag!=Thread)&&(p==q->;lchild)//从左树返回根结点，根结点有右子树，则后继为右子树后序遍历的第一个节点
{
Push(S,q);
r=q->;rchildush(S,r);
while(!r->;rtag││!r->;ltag)
{
if(!r->;ltag) r=r->;lchild;else r=r->;rchild;
Push(S,r);
}
p=p->;rchild;
visite(p->;data);
}
}
}


觉得没有实际意义....

写得很仓促,有错误!