二叉树三种遍历的非递归算法(背诵版) 1.先序遍历非递归算法
7 S' {& }2 w# y#define maxsize 100' l/ q U( x: p& t y% q3 ~
typedef struct
0 G; q [& ~: N; J, a8 q; Q{1 t, `! m9 H% ]: E8 ^5 {
Bitree Elem[maxsize];
0 \: X& P1 x! A int top;
' t; t! y. c+ t+ ~# O* V5 G' K}SqStack;
" o" P, I0 [3 Kvoid PreOrderUnrec(Bitree t)
* m+ Q& q5 L% @# ^2 R{/ W' M$ `) Q4 o0 O# d$ X% ^
SqStack s;7 _, X5 `& ~1 v8 c6 U
StackInit(s);
6 g! d ~3 W7 Z9 K! D p=t;
9 z3 T+ X @: V4 w/ ~/ ?; E4 t: E2 Z while (p!=null || !StackEmpty(s))
% ~ Y4 Q5 g4 H {4 j0 Y9 J% m. G, f: ]! Q6 ^
while (p!=null) //遍历左子树) D2 V Q; o8 J* i* j! F
{
/ N3 j- k6 k( _ f | visite(p->data);: h( g% n4 t8 |- ^- M" x( R7 V
push(s,p);+ d" N7 w5 l2 t% C
p=p->lchild;
T# e2 o s$ e+ L" h" P }//endwhile
- U5 O7 x5 C; W/ r4 e7 e/ n7 G
2 _0 Y: k: K* p5 R4 q+ `1 ? if (!StackEmpty(s)) //经由过程下一次轮回中的内嵌while实现右子树遍历+ v4 R( X2 h7 c% o( |, _ V( U8 s
{! b5 R, T7 |, ~
p=pop(s);6 E1 H5 L6 X2 A; Z
p=p->rchild;
0 a' S* m# t: { }//endif
5 x$ J) h5 _2 o+ {( \ }//endwhile & u( n' B: O5 G, f h
}//PreOrderUnrec |
发表于 2012-8-2 08:51:15
