3.后序遍历非递归算法 #define maxsize 100
y- B9 g1 _8 {typedef enum{L,R} tagtype;
# m' {+ u! `) B7 `8 ]; g% Ftypedef struct ' @) f9 p2 N" d3 _, f/ M$ L- d
{! h8 q) Z0 x$ i; b7 ~# l
Bitree ptr;
5 S; W d0 X0 |, u' ftagtype tag;
. R* m5 p2 x! S}stacknode; `2 k+ j4 n6 J" H% V
typedef struct2 C8 l8 H8 v& I' K* `
{
( ?7 s! S) h5 d$ A; E; }2 G) _, q; s2 D9 |stacknode Elem[maxsize];
- V5 J( f: @; K( d4 l; Wint top;
0 z) u! X* ]/ U) w}SqStack;
/ }( d9 x/ ~! Q# K: G
/ J" w9 J: F4 A//后序遍历
7 Z0 K; j& {5 D4 R, u/ Uvoid PostOrderUnrec(Bitree t)
2 w3 ?) H( F) p{
2 W5 P4 T5 `) D" ESqStack s;& \; V, Q) |$ K, n- K
stacknode x;
! H8 o3 n6 u$ ?* H+ Y YStackInit(s);
( J, u2 t" C6 Wp=t;
# p- n+ X' V* O8 r/ ]/ t
' m+ w' u& T) F" B& t udo & W, L4 h; {$ b6 W
{. o) {4 n# H; @( u/ w8 L. x
while (p!=null) //遍历左子树$ R n& u! k3 L7 Y4 H+ V& z
{
; \& D, Q+ I! x5 K6 i& wx.ptr = p;
5 [; V, |' X) ~' g" \% f% {( ?x.tag = L; //标记为左子树' ]/ N3 U' K+ p
push(s,x);
7 I* r8 F4 o" @. k) X, j% P8 wp=p->lchild; K3 q0 X5 [* e h
}
W2 o2 s- x' h* u# t2 c1 H
# ]7 A3 E( A/ L( j3 h2 Wwhile (!StackEmpty(s) &&s.Elem[s.top].tag==R) 3 ]* f( u) u, i* W6 i* d
{7 n) y3 c% [1 Z# \! l* o$ ~
x = pop(s);1 w3 e& Y! d2 f
p = x.ptr;% L: W) a7 e0 y5 o( T" ?
visite(p->data); //tag为R,表示右子树访问完毕,故访问根结点
: i2 u' t7 R2 v6 _* g# k}" m. e* i/ e# C& v1 Y
) H% }% @8 y: w) I8 Rif (!StackEmpty(s))
4 p9 r) [8 i2 \3 O8 ~' S{8 Y6 j0 ?: I+ v* h+ X' k4 f
s.Elem[s.top].tag =R; //遍历右子树7 U7 G; F, e/ x4 v9 X% W+ K8 i6 I
p=s.Elem[s.top].ptr->rchild; & ^* d# f. Z$ H, ~9 R1 l
}
* j7 j4 r6 q7 @}while (!StackEmpty(s));) W; d# ]0 ~ `* R: x6 @
}//PostOrderUnrec |