2011年软考程序员考试复习笔试知识点整理4 n. T+ i" t% S9 P- n1 F
二叉树三种遍历的非递归算法(背诵版)7 l5 i" p) }4 Z4 e6 y
3.后序遍历非递归算法
Z# R4 l+ W# t5 E) x% l#define maxsize 100$ [! R- P+ i6 ~2 E( X
typedef enum{L,R} tagtype;
! E/ z! V, @5 V! Ztypedef struct
7 O3 T5 B" I4 i D( D0 Z+ |{
$ M+ r7 }6 N" `+ @8 w Bitree ptr;
6 R0 s+ k4 i7 t2 ^8 x \4 m& x ] X tagtype tag;
) z& {9 ?6 h2 r* R/ {}stacknode;5 M) W' m5 i0 ~. p- ` V
typedef struct# L% ]% S# z4 r% z9 q) n
{# ^$ S. a8 F) N7 Z: R" C9 @5 O
stacknode Elem[maxsize];9 a5 ?5 w+ T3 Z3 |# g1 s( I' m4 W
int top;; u ]5 U, h, c+ _/ B4 u2 n
}SqStack;
7 x3 z5 d* K/ u3 N! [2 o7 Z
) m$ I; S6 e- U; u: t//后序遍历- m0 k; `2 P* E
void PostOrderUnrec(Bitree t)8 f9 O9 S- F7 l' I V
{
y4 ? R, b I( k- Q SqStack s;; `. ^& L6 M; [& m" h$ \. L
stacknode x;9 v \- P Q3 a0 [) D+ D- s
StackInit(s); T5 b: H, |8 o+ h! ?7 m
p=t;
/ S: I3 }7 R2 g% A9 A $ T/ f4 ~+ ], l) h
do 0 P1 _: c/ @( S( k- f# e) Q$ K9 ~
{& { S/ U4 P' B; `- ~8 k) ^
while (p!=null) //遍历左子树1 I& V4 y0 H3 P" z! y' E
{9 p5 S/ l8 [" a* {: e
x.ptr = p; . l5 e* B0 L- _2 u
x.tag = L; //标记为左子树
' F0 O1 c+ w; [3 _7 C# K push(s,x);
2 Z+ w( v* T1 \; W7 ] p=p->lchild;
: t" G: Z' n0 w0 L7 Z% R( c. ~ }
& E. O6 V. s- F0 S2 V+ P% s" }, T' M
7 h9 Q& n J7 N9 @' R% E' M while (!StackEmpty(s) &&s.Elem[s.top].tag==R) 1 Z, |. T4 ~+ E& M
{# G, B1 Q+ r) S" `
x = pop(s);1 Z5 X) V) P/ A4 a
p = x.ptr;8 J" W. j' `+ R& v
visite(p->data); //tag为R,表示右子树访问完毕,故访问根结点
* v9 o9 p/ m% g2 h }
) _) u4 M, j( i* z+ y( a* F: U
- @- ~) @ _, s/ } if (!StackEmpty(s))
8 b1 Z0 q$ R! W1 N: d {
" g7 D- Y! U+ ~8 F! O9 n) F s.Elem[s.top].tag =R; //遍历右子树0 g( n% ]/ y8 v/ U8 B4 [0 U' f
p=s.Elem[s.top].ptr->rchild;
* s7 i% D2 U$ K! W) g }
U; H8 {& p4 s1 Q* q) g }while (!StackEmpty(s));4 c* T0 S3 _# {
}//PostOrderUnrec |