編寫(xiě)的方法：根據(jù)樹(shù)中結(jié)點(diǎn)的遍歷規(guī)律及順序直接寫(xiě)出其非遞歸算法。
先序非遞歸算法
【思路】
假設(shè)：T是要遍歷樹(shù)的根指針，若T?!=?NULL
對(duì)于非遞歸算法，引入棧模擬遞歸工作棧，初始時(shí)棧為空。
問(wèn)題：如何用棧來(lái)保存信息，使得在先序遍歷過(guò)左子樹(shù)后，能利用棧頂信息獲取T的右子樹(shù)的根指針？
方法1：訪(fǎng)問(wèn)T->data后，將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén)，出棧，再先序遍歷T的右子樹(shù)。
方法2：訪(fǎng)問(wèn)T->data后，將T->rchild入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén)->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ù)后，訪(fǎng)問(wèn)根，再遍歷右子樹(shù)。
問(wèn)題：如何用棧來(lái)保存信息，使得在中序遍歷過(guò)左子樹(shù)后，能利用棧頂信息獲取T指針？
方法：先將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén)，出棧，訪(fǎng)問(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ù)后，再訪(fǎng)問(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ù)；最后訪(fǎng)問(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;
}
}