读书人

后序遍历非递归算法大家看看哪错了解

发布时间: 2012-04-25 19:32:32 作者: rapoo

后序遍历非递归算法,大家看看哪错了
void PostOrderTraverse(BiTree T)//后序遍历非递归算法
{
SqStack S;
InitStack(S);
BiTree p;
BiTree lastvist = NULL;
p=T;
while (p||!StackEmpty(S))
{

while (p)
{
Push(S,p);
p= p->lchild;
}
GetTop(S,p);
if (p->rchild==NULL||p->rchild==lastvist)

{
printf("%c",p->data);
Pop(S,lastvist);
}
else

p = p->rchild;

}
}

[解决办法]
思路上就不对吧。。。
http://www.cnblogs.com/hicjiajia/archive/2010/08/27/1810055.html
看看这个
[解决办法]
程序的大体思路是由lastview 保存至今输出的节点,有不断压入left节点保证left节点访问过,在输出时,仅检查right节点是否满足条件。
程序的right节点控制很好,单但程序无法确认left节点是否已经访问过。目测,此程序会一直输出最left下的节点。
while中改变p的地方GetTop(S,p); else部分永远不会被执行{自己可以尝试访问一些简单的树试试}
建议:加个leftlastview,检测left段最后访问的节点。

读书人网 >C语言

热点推荐