我們提供的服務(wù)有：做網(wǎng)站、網(wǎng)站制作、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、忻州ssl等。為近1000家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的忻州網(wǎng)站制作公司
二叉樹前序、后序和后序遍歷（非遞歸實(shí)現(xiàn)）
（1）前序
我們知道，前序遍歷的順序是根左右，當(dāng)根節(jié)點(diǎn)不為空時(shí)，該節(jié)點(diǎn)才可以被打印。目前書上常見對樹的遍歷都是采用遞歸的方法實(shí)現(xiàn)的，我們知道遞歸必然會產(chǎn)生中斷，也就是有現(xiàn)場信息的保存，如果要實(shí)現(xiàn)非遞歸，那么我們必須自己要有一個(gè)棧，用來保存現(xiàn)場信息。
我先給出實(shí)現(xiàn)的偽代碼，稍后我將解釋為什么需要這么做，為何要用到這些條件。
偽代碼如下：
1 void PreOrderTraverse(BinaryTree root)
2 {
3 BinaryTree cur = root;
4 stack
5 while(null != cur || !s.empty())
6 {
7 while(null != cur)
8 {
9 print cur.data;
10 s.push(cur);
11 cur = cur.left;
12 }
13 if(!s.empty()) {
14 cur = s.top();
15 s.pop();
16 cur = cur.right;
17 }
18 } //loop end!
19}
第3行的cur就相當(dāng)于遞歸中的現(xiàn)場信息，而第4行聲明到的棧則用來保存它。
第5行的循環(huán)條件暫時(shí)不用關(guān)注，我們看第7行到第12行的代碼，它主要做的是，如果當(dāng)前節(jié)點(diǎn)不為空，則打印，同時(shí)將該結(jié)點(diǎn)的信息保存到用戶棧中，接著把當(dāng)前節(jié)點(diǎn)改變成它到的左子。當(dāng)左子為空時(shí)，循環(huán)結(jié)束。
接著再看第13行到第16行的代碼，它做的是取棧頂?shù)默F(xiàn)場信息（也就是最后一次保存的現(xiàn)場信息），然后改變當(dāng)前結(jié)點(diǎn)為它的右子。
最后我們關(guān)注這個(gè)大循環(huán)結(jié)束的條件。當(dāng)?shù)?6行執(zhí)行結(jié)束，cur為右結(jié)點(diǎn)，可能存在兩種情形:
① 右子為空，那么我們從用戶?；謴?fù)保存的現(xiàn)場信息。
② 右子不為空，那么整個(gè)邏輯不變，按照之前的方法進(jìn)行處理。
所以我們得出整個(gè)循環(huán)繼續(xù)得以執(zhí)行的條件是結(jié)點(diǎn)不為空或者用戶棧不空，滿足二者其一即可。
（2）后序
后序遍歷的順序是左右根，我們要保證根節(jié)點(diǎn)在左孩子和右孩子訪問之后才能訪問。
首先我們來考慮一個(gè)結(jié)點(diǎn)P能被訪問的條件：
① P的左孩子和右孩子都為空，則該節(jié)點(diǎn)可以被直接訪問；
② P有左孩子或右孩子，但左孩子和右孩子都已經(jīng)被訪問過，那么結(jié)點(diǎn)P也可以直接訪問。
如果不是上面兩種條件，那我們將P的右孩子和左孩子依次入棧，這樣就可以保證每次取棧頂元素的時(shí)候，左孩子在右孩子的前面被訪問，左孩子和右孩子都在根節(jié)點(diǎn)的前面被訪問。
實(shí)現(xiàn)的偽代碼如下:
void PostOrderTraverse(BinaryTree root)
{
if(null == root)
return;
stack
s.push(root);
BinaryTree pre = null;
BinaryTree cur;
while(!s.empty())
{
cur = s.top();
if(null == cur.lchild) && null == cur.rchild
|| (null != pre) && (pre == cur.lchild || pre == cur.rchild)) {
print cur.data;
s.pop();
pre = cur;
}
else {
if(null != cur.rchild) {
s.push(cur.rchild);
}
if(null != cur.lchild) {
s.push(cur.lchild);
}
}
} //loop end!
}
