2011年软考程序员考试复习笔试知识点整理2' @. q& n2 k8 M/ W! o
二叉树三种遍历的非递归算法(背诵版)( T5 \2 p% D2 f
1.先序遍历非递归算法0 c5 a5 E3 E; |1 u8 Y) W+ `
#define maxsize 100 h- a* g; _8 y
typedef struct5 a+ N& v" n# a% X# [( k6 |
{
3 y4 U8 @# {+ v Bitree Elem[maxsize];
. i* I1 s' \ Y! @* ? int top;. L3 q( o) I* Q) p! B
}SqStack;
5 R: F6 _% Z; Svoid PreOrderUnrec(Bitree t)9 q( q. ~2 p f, |6 z
{ B/ T j9 l0 l# z% B3 F4 t
SqStack s;- K6 Q1 a1 L/ \! l2 }
StackInit(s);4 L `( H" I: z* _6 n
p=t;
4 l! p# E, |$ L+ [- X [( \ while (p!=null || !StackEmpty(s))
! W g( O- a- I( P {
4 L( a" D, A8 `3 U4 O3 V# p9 e o while (p!=null) //遍历左子树
! a, ], g# y& D H0 K {
) v: o- P: P7 t3 }" O visite(p->data);* B7 D: Z0 \/ e4 D9 o( S) w
push(s,p);" O0 O5 Y1 X# _( x) i( _ u
p=p->lchild; * n) J L/ L2 ~ [( Y! B
}//endwhile( _3 H7 Y. K) c* H9 Q
7 m7 o# O2 F3 Z8 i$ C) d1 h
if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
8 U+ Z5 J8 M3 Q+ I: \$ w {# N. |3 Y4 \+ f1 O; w( i0 q
p=pop(s);( `7 r/ ?6 W$ g) M
p=p->rchild; 0 s$ `1 l0 _* ]" o& B# U8 K% ]8 Y
}//endif
6 q, x) u( a1 ]: h3 E4 w$ H }//endwhile
1 a3 A' X) o! |7 I8 C$ f}//PreOrderUnrec |
发表于 2012-8-2 08:51:15
