后序遍历非递归算法,大家看看哪错了
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段最后访问的节点。