遍歷二叉樹(shù)的非遞歸算法
編寫(xiě)的方法：根據(jù)樹(shù)中結(jié)點(diǎn)的遍歷規(guī)律及順序直接寫(xiě)出其非遞歸算法。
先序非遞歸算法
【思路】
假設(shè)：T是要遍歷樹(shù)的根指針，若T != NULL
對(duì)于非遞歸算法，引入棧模擬遞歸工作棧，初始時(shí)棧為空。
問(wèn)題：如何用棧來(lái)保存信息，使得在先序遍歷過(guò)左子樹(shù)后，能利用棧頂信息獲取T的右子樹(shù)的根指針？
方法1：訪問(wèn)T->data后，將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T，出棧，再先序遍歷T的右子樹(shù)。
方法2：訪問(wèn)T->data后，將T->rchild入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T->rchild，出棧，遍歷以該指針為根的子樹(shù)。
【算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法一，流程圖如右，當(dāng)型循環(huán)
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法二，流程圖如右，當(dāng)型循環(huán)
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
進(jìn)一步考慮：對(duì)于處理流程中的循環(huán)體的直到型、當(dāng)型+直到型的實(shí)現(xiàn)。
中序非遞歸算法
【思路】
T是要遍歷樹(shù)的根指針，中序遍歷要求在遍歷完左子樹(shù)后，訪問(wèn)根，再遍歷右子樹(shù)。
問(wèn)題：如何用棧來(lái)保存信息，使得在中序遍歷過(guò)左子樹(shù)后，能利用棧頂信息獲取T指針？
方法：先將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T，出棧，訪問(wèn)T->data，再中序遍歷T的右子樹(shù)。
【算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程圖如右，當(dāng)型循環(huán)
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
進(jìn)一步考慮：對(duì)于處理流程中的循環(huán)體的直到型、當(dāng)型+直到型的實(shí)現(xiàn)。
后序非遞歸算法
【思路】
T是要遍歷樹(shù)的根指針，后序遍歷要求在遍歷完左右子樹(shù)后，再訪問(wèn)根。需要判斷根結(jié)點(diǎn)的左右子樹(shù)是否均遍歷過(guò)。
可采用標(biāo)記法，結(jié)點(diǎn)入棧時(shí)，配一個(gè)標(biāo)志tag一同入棧(0：遍歷左子樹(shù)前的現(xiàn)場(chǎng)保護(hù)，1：遍歷右子樹(shù)前的現(xiàn)場(chǎng)保護(hù))。
首先將T和tag(為0)入棧，遍歷左子樹(shù)；返回后，修改棧頂tag為1，遍歷右子樹(shù)；最后訪問(wèn)根結(jié)點(diǎn)。
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程圖如右，當(dāng)型循環(huán)
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 設(shè)置棧頂標(biāo)記
T = GetTopPointer(S); // 取棧頂保存的指針
T = T->rchild;
}else break;
}
}