中序周遊的通路過程:
1.沿着根的左孩子,依次入棧,直到左孩子為空,說明已經找到可以輸出的節點。
2.棧頂元素出棧并通路,若其右孩子為空,繼續執行2。
3.若右孩子不空,将右子樹轉執行1。
void InOrder(BiTree T){
InitStack(S); BiTree p=T;
while(p||!IsEmpty(S)){
if(p){
Push(S,p);
p=p->lchild;
}
else{
Pop(S,p);
visit(p);
p=p->rchild;
}
}
}
先序周遊:
void PreOrder(BiTree T){
InitStack(S); BiTree p=T;
while(p||!IsEmpty(S)){
if(p){
visit(p);
Push(S,p);
p=p->lchild;
}
else{
Pop(S,p);
p=p->rchild;
}
}
}
後序周遊:
1.沿着根的左孩子依次入棧,直到左孩子為空。
2.讀棧頂元素(不彈出),若其右孩子不空且未被通路過,将右子樹轉執行1;否則棧頂元素出棧并通路。
在2中必須厘清傳回時是從左子樹傳回還是從右子樹傳回的,是以設定一個輔助指針r,指向最近通路過的節點。
void PostOrder(BiTree T){
InitStack(S);
p=T;
r=NULL;
while(p||!IsEmpty(s)){
if(p){ //走到最左邊
push(S,p);
p=p->lchild;
}
else{
GetTop(S,p); //讀棧頂節點(非出棧)
if(p->rchild&&p->rchild!=r){ //若右子樹存在,且未被通路過
p=p->rchild; //轉向右
push(S,p); //壓入棧
p=p->lchild; //在走到最左
}
else{ //否則彈出節點并通路
pop(S,p);
visit(p->data);
r=p; //記錄最近通路的結點
p=NULL; //每次出棧通路完一個節點就相當于周遊完以該節點為根的子樹,需将p置為NULL。
}
}
}
}