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