回覆列表
-
1 # 梁範志
-
2 # 使用者3845252462615
中序遍歷
中序遍歷比較重要，規則為：左子樹，根節點，右子樹。
一切都是從根節點開始的。
從A開始，因為A有B左子樹，所以A不是第一個點。
B子樹沒有左子樹，所以B為根節點，結果為B。我們知道其實一切都是從根節點開始，在這裡是A。
在這種排序遍歷中，和一個佇列有關。
先將A進入佇列，佇列中為:A;
然後A出佇列，輸出A，左右子樹的B，E進入佇列,佇列中為：BE。
然後B出佇列，輸出AB，C進入佇列,佇列中為:EC。
然後E出佇列，輸出為ABE,F進入佇列，佇列中為:CF。
然後c出佇列，輸入為ABEC,D進入佇列，佇列中為:FD。
然後F出佇列，輸入為ABECF,G進入佇列，佇列為:DG.
然後D出佇列，然後輸入為ABECFD,佇列為:G
然後G出佇列，然後輸入為ABECFDG,佇列為:HK
然後HK分別出佇列，輸出為ABECFDGHK。
這裡有二叉樹先序、中序、後序三種遍歷的非遞迴演算法，此三個演算法可視為標準演算法。
1.先序遍歷非遞迴演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//透過下一次迴圈中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍歷非遞迴演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//訪問根結點
p=p->rchild;
//透過下一次迴圈實現右子樹遍歷
}//endif
}//endwhile
}//InOrderUnrec
3.後序遍歷非遞迴演算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍歷左子樹
{
x.ptr
=
p;
x.tag
=
L;
//標記為左子樹
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag為R，表示右子樹訪問完畢，故訪問根結點
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec