二叉樹前序、后序和后序遍歷（非遞歸實現(xiàn)）
（1）前序
我們知道，前序遍歷的順序是根左右，當根節(jié)點不為空時，該節(jié)點才可以被打印。目前書上常見對樹的遍歷都是采用遞歸的方法實現(xiàn)的，我們知道遞歸必然會產(chǎn)生中斷，也就是有現(xiàn)場信息的保存，如果要實現(xiàn)非遞歸，那么我們必須自己要有一個棧，用來保存現(xiàn)場信息。
我先給出實現(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就相當于遞歸中的現(xiàn)場信息，而第4行聲明到的棧則用來保存它。
第5行的循環(huán)條件暫時不用關注，我們看第7行到第12行的代碼，它主要做的是，如果當前節(jié)點不為空，則打印，同時將該結點的信息保存到用戶棧中，接著把當前節(jié)點改變成它到的左子。當左子為空時，循環(huán)結束。
接著再看第13行到第16行的代碼，它做的是取棧頂?shù)默F(xiàn)場信息（也就是最后一次保存的現(xiàn)場信息），然后改變當前結點為它的右子。
最后我們關注這個大循環(huán)結束的條件。當?shù)?6行執(zhí)行結束，cur為右結點，可能存在兩種情形:
① 右子為空，那么我們從用戶?；謴捅４娴默F(xiàn)場信息。
② 右子不為空，那么整個邏輯不變，按照之前的方法進行處理。
所以我們得出整個循環(huán)繼續(xù)得以執(zhí)行的條件是結點不為空或者用戶棧不空，滿足二者其一即可。
（2）后序
后序遍歷的順序是左右根，我們要保證根節(jié)點在左孩子和右孩子訪問之后才能訪問。
首先我們來考慮一個結點P能被訪問的條件：
① P的左孩子和右孩子都為空，則該節(jié)點可以被直接訪問；
② P有左孩子或右孩子，但左孩子和右孩子都已經(jīng)被訪問過，那么結點P也可以直接訪問。
如果不是上面兩種條件，那我們將P的右孩子和左孩子依次入棧，這樣就可以保證每次取棧頂元素的時候，左孩子在右孩子的前面被訪問，左孩子和右孩子都在根節(jié)點的前面被訪問。
實現(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!
}
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
重慶分公司
重慶分公司
