算法思想:
- 后序非递归遍历顺序:左右根
- 用堆栈来存储结点时,必须分清返回根节点时 是从左子树返回还是右子树返回。
- 所以使用辅助指针r,指向最近访问过的结点。
- 也可在结点中增加一个标志域,记录是否已被访问过。
void PostOrder( BiTree T)
{
InitStack(S);
p=T;
r=NULL;
while(p || !IsEmpty(S))
{
if (p){ //走到最左边
push(S,p);
p=p->lchild;
}
else
{
GetTop(S,p); //向右,取栈顶结点。
if (p->rchild && p->rchild!=r) //若右子树存在,且未被访问过
{
p = p->rchild; //转向右
push(S,p); //压栈
p = p->lchild; //再走到最左
}
else
{ //否则,弹出结点并访问
pop(S,p); //将结点弹出
visit(p->data); //访问该结点
r = p; //记录最近访问过的结点
p = NULL; //结点访问完后,重置p指针
}
}
}
}
访问一个结点*p 时,栈中结点恰好是*p结点的所有祖先。从栈底到栈顶结点再加上*p结点,刚好构成从根结点到*p结点的一条路径。
在很多算法设计中都利用了这一特性求解,如求根结点到某结点的路径、求两个结点的最近公共祖先等,都可以利用这个思路来实现。