2011年软考程序员考试复习笔试知识点整理4
3 q# y; P+ w' E9 H z' K二叉树三种遍历的非递归算法(背诵版)
* G( N2 x1 V! H6 l% f5 }, O3.后序遍历非递归算法
P* V) [' |7 f, g5 b#define maxsize 100
% m/ n. B3 t; @8 b7 i8 [* ztypedef enum{L,R} tagtype;
5 q6 D: \: V8 itypedef struct
! b6 |% G, k9 M' z3 Z$ |{" [' X1 \5 _( C) t5 Z2 y$ x
Bitree ptr;: f& y! l( F( V8 q9 u9 }9 p
tagtype tag;
- T/ ^1 Q J7 b) L9 j7 w* f}stacknode;' E; `" B: v# E, Y2 u4 ~
typedef struct7 I0 [/ S2 H3 _3 E
{" j+ X! p" G* y
stacknode Elem[maxsize];% l% A; f" X# ^' ~8 u
int top;) l2 d. _8 f5 ?/ V0 ^. d$ r
}SqStack;
W# ~6 d3 {0 B2 T8 [0 u
+ p y+ j' Q9 g" {: `9 ~//后序遍历0 r% w2 D5 W5 f* E( i% D$ ^% ], s
void PostOrderUnrec(Bitree t)
5 R* R @8 D E# m* Y( h% B{8 b2 l& c4 D5 d/ U* d
SqStack s;& Y, G7 y: n/ [7 T: m
stacknode x;3 i" N. N) }* {
StackInit(s);
' I0 }: Z. h4 {9 t5 _: [ p=t;) y- M- v# N: i! B% G
2 R2 T u9 h3 \# q8 _ do
& G" K+ X% o& E {
/ Q6 [/ [$ K1 a0 \5 O) ^- F while (p!=null) //遍历左子树" }: y" I9 y" s* G4 s
{
. g2 f: Q7 M+ t$ u; ?% c x.ptr = p;
6 v; A- c* W6 v# T% C x.tag = L; //标记为左子树
( `4 g0 _7 {3 ~# f push(s,x);( {) E5 h6 e2 g' j5 k
p=p->lchild;% N1 x% L, z: g& \+ q' u& D
}6 \' R) e7 N2 J' c8 n3 ?- V
0 u- W% B4 [ N* S( f
while (!StackEmpty(s) &&s.Elem[s.top].tag==R) : w& u- c! r. b% |! x5 x
{
1 v1 x- D$ E. r: s1 A3 ] x = pop(s);5 I* \4 Y* \. a/ k
p = x.ptr;
) ^% Z- x% @+ l% {. I3 @7 O visite(p->data); //tag为R,表示右子树访问完毕,故访问根结点
) L% J/ r1 l. U8 V p$ y) I- c# u }
( D/ _; P( U2 E* K3 v6 } % C. g1 y, M. ?
if (!StackEmpty(s))' j7 I1 T) X1 S9 r
{- t+ T q( R# t3 O2 M, }
s.Elem[s.top].tag =R; //遍历右子树; I/ C+ K1 a# W8 j* w# t
p=s.Elem[s.top].ptr->rchild; 7 C7 P8 G; H6 u5 G! Y4 e7 P
} 8 B0 f5 g3 s: w. Q0 u/ u
}while (!StackEmpty(s));
; v9 Y) v( L& _9 J}//PostOrderUnrec |