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