后序遍历二叉树的非递归算法
模拟栈的操作过程
C
B
A
1.PUSH A
2.PUSH B
3.PUSH C
B
A
4.C’lchild is NULL
and C’rchild is NULL,
VISIT C ,
POP C ;
A
5. B’rchild is NULL,
VISIT B ,
POP B;
E
D
A
6. A’rchild is not NULL,
7.PUSH D;
8.PUSH E;
F
E
D
A
9.E’lchild is NULL;
but E’rchild is not NULL;
PUSH F;
G
F
E
D
A
10. F’lchild is NULL;
but F’rchild is not NULL;
PUSH G;
F
E
D
A
11.G’lchild is NULL
and G’rchild is NULL,
VISIT G ,
POP G ;
E
D
A
12. F’rchild is not NULL;
but G is just visited;
VISIT F;
POP F;
D
A
13. E’rchild is not NULL;
but F is just visited;
VISIT E;
POP E;
H
D
A
14. D’rchild is not NULL;
PUSH H;
D
A
15. H’lchild is NULL
and H’rchild is NULL,
VISIT H ,
POP H ;
A
16. D’rchild is not NULL;
but H is just visited;
VISIT D;
POP D;
17. A’rchild is not NULL;
but D is just visited;
VISIT A;
POP A;
18.STACK is empty,end.
算法的形成过程
（一）基本思路
1.从根开始，不断将左子树指针压栈，直到指针为空为止；
2.这时的栈顶元素所指的树结点肯定没有左孩子，
如果它也没有右孩子，该结点就是要访问的结点，
于是访问它，从栈中弹出指向该结点的指针；
否则，它有右孩子则必须将它的右孩子继续压栈；转到 1.
但如果它的右孩子是被访问过的（对后序遍历来说，就是刚刚被访问过），
则又必须访问该结点。
（二）重新整理一下思路
1.从根开始，不断将左子树指针压栈，直到指针为空为止；
2.看栈顶元素
如果：它没有右孩子，或者它的右孩子刚被访问过，访问该结点，弹栈；转到 2；
否则：它的右孩子不空且未被访问过，则必须将它的右孩子继续压栈；转到 1；
3.栈空，则结束。
（三）写算法
void post_order(BiTree T)
{
p=T;
do{
1: while(p){push(S,p)；p=p->lchild; }
2: get(S,p);
if (p->rchild==NULL)||(p->rchild==q)//q 表示刚访问过的结点
{visit(p);
pop(S); goto 2;
}
else{
p=p->rchild;goto 1;
}
}while (!stackempty(S))
}//end of post_order
（四）写结构较好的算法
void post_order(BiTree T)
{
p=T;
do{
1: while(p){push(S,p)；p=p->lchild; }
2: q=NULL;//为了给 q 赋初值，也可以理解为是栈顶元素的左子
while(!stackempty(S))
{
get(S,p);
if (p->rchild==NULL)||(p->rchild==q)//q 表示刚访问过的结点
{visit(p); q=p; //记录访问过的结点
pop(S); goto 2;
}
else{
p=p->rchild; goto 1; break;
}
}while (!stackempty(S))
}//end of post_order
（四）写相应的 c 程序
#include
#include
#include
#define MaxSize 100
typedef char elemtype;
typedef struct BiTNode{
elemtype data;
struct BiTNode *lchild,*rchild;
} BiTNode,* BiTree;//p127
void post_order(BiTree T)
{
BiTree stack[MaxSize], p,q;int top=-1;
p=T;
do{
1: while(p)
{ push(S,p)； top++; stack[top]=p;
p=p->lchild;
}
2: q=NULL;
while(!stackempty(S) top>=0)
{
get(S,p); p=stack[top];
if (p->rchild==NULL)||(p->rchild==q)
{ visit(p); cout<data<<” “;
q=p;
pop(S); top- - ;
}
else{
p=p->rchild; break;
}
}
}while (!stackempty(S) top>=0 ) ;
}//end of post_order
整理 C 程序
#include
#include
#include
#define MaxSize 100
typedef char elemtype;
typedef struct BiTNode{
elemtype data;
struct BiTNode *lchild,*rchild;
} BiTNode,* BiTree;
void post_order(BiTree T)
{
BiTree stack[MaxSize], p,q;int top=-1;
p=T;
do{
while(p)
{ top++; stack[top]=p;
p=p->lchild;
}
q=NULL;
while( top>=0)
{
p=stack[top];
if (p->rchild==NULL)||(p->rchild==q)
{ cout<data<<” “;
q=p;
top- - ;
}
else{
p=p->rchild; break;
}
}
}while ( top>=0 ) ;
}//end of post_order
另一种 C 程序
void post_order2(BiTree T)
{
BiTree stack[MaxSize],p=T,q;
int top=-1,flag;
do
{
while(p)
{ top++; stack[top]=p; p=p->lchild;}
q=NULL;
flag=1;
while(top>=0 && flag)
{
p= stack[top];
if (p->rchild==q)
{
cout<data<<” ”;
top--;
q=p;
}
else
{
p=p->rchild;
flag=0;
}
}
}while(top>=0);
}//end of post_order2
浙公网安备 33021202002483