|
发表于 2017-8-6 20:19:51
|
显示全部楼层
算法步骤如下:
①若二叉树T=∧(空树),返回,算法终止;
②初始化:置栈S空,根指针T=>p;
③反复以下过程,直到p=∧且栈S=∧时算法终止:
若p≠∧,(p,o)进栈,p=p–>Lchild (遍历左子树) ,……,直到 p=∧;出栈, 栈顶=>(p,
tag);若tag=0,(p,1)进栈,p=p–>Rchild(遍历右子树),否则,访问p结点,并置p=∧。
算法描述:void postorder-1(BTptr T) //后序非递归遍历二叉树T//
{
int tag; BTptr p; stype sdata;
Clearstack (s); // 置栈空 //
p=T;
do {
while (p)
{
sdata.q=p; sdata.tag=0;
push (s, sdata); // (p,0)进栈//
p=p–>Lchild; //遍历p之左子树//
}
sdata=pop(s); //退栈
p=sdata.q; //取指针
tag=sdata.tag;//状态位//
if (tag= =0)//从左子树返回时,根的tag=0
{
sdata. q=p;
sdata.tag=1; //这时要进入根的右子树了,所以将根的tag=1,
//下次碰到根时就可以访问了
push(s,sdata); // (p,1) 进栈,根还得进一次栈
p=p–>Rchild; //遍历右子树//
}
else //tag=1,这时说明右子树访问完了后返回,所以这次要对根访问了
{
visit(p); //访问p结点//
p=NULL;//要再退到上层,因为该棵树已经彻底访问完了
} //之所以把p=null是不让他进入while
}while ( p|| !Emptystack(s));
}
|
|