創(chuàng)新互聯(lián)網(wǎng)絡(luò)公司擁有10年的成都網(wǎng)站開發(fā)建設(shè)經(jīng)驗(yàn)，上千余家客戶的共同信賴。提供網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、網(wǎng)站開發(fā)、網(wǎng)站定制、賣友情鏈接、建網(wǎng)站、網(wǎng)站搭建、成都響應(yīng)式網(wǎng)站建設(shè)公司、網(wǎng)頁設(shè)計(jì)師打造企業(yè)風(fēng)格，提供周到的售前咨詢和貼心的售后服務(wù)

二叉樹前序、后序和后序遍歷（非遞歸實(shí)現(xiàn)）

（1）前序

我們知道，前序遍歷的順序是根左右，當(dāng)根節(jié)點(diǎn)不為空時，該節(jié)點(diǎn)才可以被打印。目前書上常見對樹的遍歷都是采用遞歸的方法實(shí)現(xiàn)的，我們知道遞歸必然會產(chǎn)生中斷，也就是有現(xiàn)場信息的保存，如果要實(shí)現(xiàn)非遞歸，那么我們必須自己要有一個棧，用來保存現(xiàn)場信息。

  我先給出實(shí)現(xiàn)的偽代碼，稍后我將解釋為什么需要這么做，為何要用到這些條件。

  偽代碼如下：

1 void PreOrderTraverse(BinaryTree root)

2 {

3   BinaryTree cur = root;

4   stack<BinaryTree> s;

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)條件暫時不用關(guān)注，我們看第7行到第12行的代碼，它主要做的是，如果當(dāng)前節(jié)點(diǎn)不為空，則打印，同時將該結(jié)點(diǎn)的信息保存到用戶棧中，接著把當(dāng)前節(jié)點(diǎn)改變成它到的左子。當(dāng)左子為空時，循環(huán)結(jié)束。

  接著再看第13行到第16行的代碼，它做的是取棧頂?shù)默F(xiàn)場信息（也就是最后一次保存的現(xiàn)場信息），然后改變當(dāng)前結(jié)點(diǎn)為它的右子。

  最后我們關(guān)注這個大循環(huán)結(jié)束的條件。當(dāng)?shù)?6行執(zhí)行結(jié)束，cur為右結(jié)點(diǎn)，可能存在兩種情形:

     ① 右子為空，那么我們從用戶棧恢復(fù)保存的現(xiàn)場信息。

     ② 右子不為空，那么整個邏輯不變，按照之前的方法進(jìn)行處理。

  所以我們得出整個循環(huán)繼續(xù)得以執(zhí)行的條件是結(jié)點(diǎn)不為空或者用戶棧不空，滿足二者其一即可。

（2）后序

后序遍歷的順序是左右根，我們要保證根節(jié)點(diǎn)在左孩子和右孩子訪問之后才能訪問。

  首先我們來考慮一個結(jié)點(diǎn)P能被訪問的條件：

    ① P的左孩子和右孩子都為空，則該節(jié)點(diǎn)可以被直接訪問；

    ② P有左孩子或右孩子，但左孩子和右孩子都已經(jīng)被訪問過，那么結(jié)點(diǎn)P也可以直接訪問。

  如果不是上面兩種條件，那我們將P的右孩子和左孩子依次入棧，這樣就可以保證每次取棧頂元素的時候，左孩子在右孩子的前面被訪問，左孩子和右孩子都在根節(jié)點(diǎn)的前面被訪問。

  實(shí)現(xiàn)的偽代碼如下:

void PostOrderTraverse(BinaryTree root)

{

  if(null == root)

    return;

  stack<BinaryTree> s;

  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!

}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章標(biāo)題：二叉樹前序、后序和后序遍歷（非遞歸實(shí)現(xiàn)）-創(chuàng)新互聯(lián)
網(wǎng)站URL：http://www.chinadenli.net/article4/djosoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計(jì)公司、服務(wù)器托管、網(wǎng)站策劃、全網(wǎng)營銷推廣、營銷型網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)