二叉樹遍歷演算法的改進
二叉樹的深度優先遍歷演算法都是用遞回函式實作的，這是很低效的，原因在于系統幫你呼叫了一個堆疊并做了諸如保護現場和恢復現場等復雜的操作，才使得遍歷可以用非常簡潔的代碼實作，二叉樹深度優先遍歷演算法的非遞回實作用用戶定義的堆疊來代替系統堆疊，也就是用非遞回的方式來實作遍歷演算法，可以得到不小的效率提升，
二叉樹深度優先遍歷演算法的非遞回實作
（1）先序遍歷非遞回演算法
要寫出其遍歷的非遞回演算法，其主要任務是用自己定義的堆疊來代替系統堆疊的功能，
以圖1所示的二叉樹為例，程序為圖二所示
初態堆疊空
- 結點1入堆疊，
- 出堆疊，輸出堆疊頂結點1，并將1的左、右孩子結點（2和4）入堆疊；右孩子先入堆疊，左孩子后入堆疊，因為對左孩子的訪問要先于右孩子，后入堆疊的會先出堆疊訪問，
- 出堆疊，輸出堆疊頂結點2，并將2的左、右孩子結點（3和5）入堆疊，
- 出堆疊，輸出堆疊頂結點3，3為葉子結點，無孩子，本步無結點入堆疊，
- 出堆疊，輸出堆疊頂結點5，
出堆疊，輸出堆疊頂結點4，此時堆疊空，進入終態，
遍歷序列為1，2，3，5，4，
代碼如下
void preorderNonrecursion(BTNode *bt)
{
if(bt != NULL)
{
BTNode *Stack[maxSize]; //定義一個堆疊
int top = -1; //初始化堆疊
BTNode *p;
Stack[++top] = bt; //根結點入堆疊
while(top != -1) //堆疊慷訓圈結束
{
p = Stack[top--]; //出堆疊并輸出堆疊頂結點
Visit(p); //Visit()為訪問p的函式
if(p->rchild != NULL) //堆疊頂結點的右孩子存在，則右孩子入堆疊
Stack[++top] = p->rchild;
if(p->lchild != NULL) //堆疊頂結點的左孩子存在，則左孩子入堆疊
Stack[++top] = p->lchild;
}
}
}
（2）中序遍歷非遞回演算法
類似于先序遍歷，對圖1中的二叉樹進行中序遍歷，各個結點進堆疊、出堆疊程序如圖3所示，
初態堆疊空，
- 結點1入堆疊，1左孩子存在，
- 結點2入堆疊，2左孩子存在，
- 結點3入堆疊，3左孩子不存在，
- 出堆疊，輸出堆疊頂結點3，3右孩子不存在，
- 出堆疊，輸出堆疊頂結點2，2右孩子存在，右孩子5入堆疊，5左孩子不存在，
- 出堆疊，輸出堆疊頂結點5，5右孩子不存在，
- 出堆疊，輸出堆疊頂結點1，1右孩子存在，右孩子4入堆疊，4左孩子不存在，
出堆疊，輸出堆疊頂結點4，此時堆疊空，進入終態，
遍歷序列為3，2，5，1，4，
由以上步驟可以看出，中序非遞回遍歷程序如下：
- 開始根結點入堆疊
- 回圈執行如下操作：如果堆疊頂結點左孩子存在，則左孩子進堆疊；如果堆疊頂結點左孩子不存在，則出堆疊并輸出堆疊頂結點，然后檢查其右孩子是否存在，如果存在，則右孩子入堆疊，
- 當堆疊空時演算法結束，
代碼如下
void inorderNonrecursion(BTNode *bt)
{
if(bt != NULL)
{
BTNode *Stack[maxSize];
int top = -1;
BTNode *p;
p = bt;
/*下邊回圈完成中序遍歷，注意：圖3進堆疊、出堆疊程序在7中會出現堆疊空狀態，但是這時遍歷還沒有結束，因根結點的右子樹還沒有遍歷，此時p非空，根據這一點來維持回圈的進行*/
while(top != -1 || p != NULL)
{
while(p != NULL) //左孩子存在，則左孩子入堆疊
{
Stack[++top] = p;
p = p->lchild;
}
if(top != -1) //在堆疊不空的情況下出堆疊并輸出出堆疊結點
{
p = Stack[top--];
Visit(p);
p = p->rchild;
}
}
}
}
（3）后序遍歷非遞回演算法
首先寫出圖1中二叉樹進行先序遍歷和后序遍歷的序列，
先序遍歷序列：1、2、3、5、4
后序遍歷序列：3、5、2、4、1
把后序遍歷序列逆序得：
逆后序遍歷序列：1、4、2、5、3
發現，逆后序遍歷序列和先序遍歷序列有一點的聯系，逆后序遍歷序列只不過是先序遍歷程序中對左右子樹遍歷順序交換所得到的結果，如圖4所示，
因此，只需要將前面的非遞回先序遍歷演算法中對左右子樹的遍歷順序交換就可以得到逆后序遍歷序列，然后將逆后序遍歷序列逆序就得到了后序遍歷序列，因此需要兩個堆疊，一個堆疊stack1用來輔助做逆后序遍歷（將先序遍歷的左、右子樹遍歷順序交換的遍歷方式稱為逆后序遍歷）并將遍歷結果序列壓入另一個堆疊stack2，然后將stack2中的元素全部出堆疊，所得到的序列即為后序遍歷序列，具體程序如圖5所示，
初態堆疊空，
- 結點1如stack1，
- stack1元素出堆疊，并將出堆疊結點1入stack2，結點1的左、右孩子存在，左孩子結點2入stack1，右孩子結點4入stack1，這里注意和先序遍歷進出堆疊程序對比，恰好是將其左、右孩子入堆疊順序調換，以實作訪問順序的調換，
- stack1元素出堆疊，并將出堆疊結點4入stack2，結點4的左、右孩子不存在，
- stack1元素出堆疊，并將出堆疊結點2入stack2，結點2的左、右孩子存在，左孩子結點3入stack1，右孩子結點5入stack1，
- stack1元素出堆疊，并將出堆疊結點5入stack2，
- stack1元素出堆疊，并將出堆疊結點3入stack2，
此時stack1空，stack2中元素自頂向下依次為：3、5、2、4、1，正好為后序遍歷序列，
代碼如下：
void postorderNonrecursion(BTNode *bt)
{
if(bt != NULL)
{
/*定義兩個堆疊*/
BTNode *Stack1[maxSize];int top1 = -1;
BTNode *Stack2[maxSize];int top2 = -1;
BTNode *p = NULL;
Stack1[++top1] = bt;
while(top1 != -1)
{
p = Stack1[top1--]；
Stack2[++top2] = p;//注意這里和先序遍歷的區別，輸出改為入Stack2
/*注意下邊這兩個if陳述句和先序遍歷的區別，左、右孩子的入堆疊順序相反*/
if(p->lchild != NULL)
Stack1[++top1] = p->lchild;
if(p->rchild != NULL)
Stack1[++top1] = p->rchild;
}
while(top2 != -1)
{
/*出堆疊序列即為后序遍歷序列*/
p = Stack2[top2--];
Visit(p);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/145106.html
標籤：其他
下一篇：單調佇列