后序遍历二叉树的非递归算法

发布时间 2024-01-03 19:10:13作者: DoubleLi

算法思想:

  1. 后序非递归遍历顺序:左右根
  2. 用堆栈来存储结点时,必须分清返回根节点时 是从左子树返回还是右子树返回。
  3. 所以使用辅助指针r,指向最近访问过的结点。
  4. 也可在结点中增加一个标志域,记录是否已被访问过。

 

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结点的一条路径。

在很多算法设计中都利用了这一特性求解,如求根结点到某结点的路径、求两个结点的最近公共祖先等,都可以利用这个思路来实现。