2.中序遍历非递归算法 #define maxsize 100
$ i" M! C- b# T) X* x) ~" P6 ztypedef struct
* Y+ W! j A j2 Z/ j! _* i, F{
. v; j3 S, K: `1 MBitree Elem[maxsize];& m* ^8 h7 r+ T2 f
int top;
* Z, p& n5 i: U! b" ]}SqStack;) ^7 N0 Y2 E5 X: v; ]( S7 c4 n
void InOrderUnrec(Bitree t)
0 h: w* n. b; o2 K3 }{, X. \' s8 Q/ H5 C) n* c/ A
SqStack s;$ k% z# M5 P+ e
StackInit(s);+ a% V% x r* W& q9 q' K% i6 u+ t3 W' ^! b
p=t;
! j- b9 s. a& ^. K! w" s3 awhile (p!=null || !StackEmpty(s))
7 `8 }, T2 G4 ~- ^9 g{) ~. J. J0 b+ n* b E1 H
while (p!=null) //遍历左子树, p! H, Q& O0 A# ~6 n: a. s. Y
{
9 [$ G: R3 I( V5 p" S7 Ppush(s,p);- b, O. {3 W& v. X3 S8 {9 g* n
p=p->lchild;
, S, K9 r0 ?* t" [& k) r}//endwhile" i6 M6 M! ^1 u9 d
7 r5 n' m7 L* Aif (!StackEmpty(s))2 C+ m! P! G Y! H
{
2 h3 H9 a2 C3 y7 X8 c4 j6 M: o, E$ [p=pop(s);
6 S5 m& @; s4 [* R" z* t, y/ P$ Xvisite(p->data); //访问根结点 V) }; W2 q5 j# @/ X5 Z, P. Q8 L
p=p->rchild; //通过下一次循环实现右子树遍历
9 Y& K: s; U4 A% e @}//endif
3 k0 R& u3 a/ I7 q+ V! O}//endwhile, M5 G! p) B& b& g
}//InOrderUnrec |