二叉树前序、中序、后序遍历非递归写法的透彻解析
生活随笔
收集整理的這篇文章主要介紹了
二叉树前序、中序、后序遍历非递归写法的透彻解析
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
前言
在前兩篇文章二叉樹(shù)和二叉搜索樹(shù)中已經(jīng)涉及到了二叉樹(shù)的三種遍歷。遞歸寫法，只要理解思想，幾行代碼。可是非遞歸寫法卻很不容易。這里特地總結(jié)下，透徹解析它們的非遞歸寫法。其中，中序遍歷的非遞歸寫法最簡(jiǎn)單，后序遍歷最難。我們的討論基礎(chǔ)是這樣的：? ??
[cpp]?view plain?copy
首先，有一點(diǎn)是明確的：非遞歸寫法一定會(huì)用到棧，這個(gè)應(yīng)該不用太多的解釋。我們先看中序遍歷：
中序遍歷
分析
中序遍歷的遞歸定義：先左子樹(shù)，后根節(jié)點(diǎn)，再右子樹(shù)。如何寫非遞歸代碼呢？一句話：讓代碼跟著思維走。我們的思維是什么？思維就是中序遍歷的路徑。假設(shè)，你面前有一棵二叉樹(shù)，現(xiàn)要求你寫出它的中序遍歷序列。如果你對(duì)中序遍歷理解透徹的話，你肯定先找到左子樹(shù)的最下邊的節(jié)點(diǎn)。那么下面的代碼就是理所當(dāng)然的：
中序代碼段(i)? ??
[cpp]?view plain?copy保存一路走過(guò)的根節(jié)點(diǎn)的理由是：中序遍歷的需要，遍歷完左子樹(shù)后，需要借助根節(jié)點(diǎn)進(jìn)入右子樹(shù)。代碼走到這里，指針p為空，此時(shí)無(wú)非兩種情況：
說(shuō)明：
我們的思維接著走，兩圖情形不同得區(qū)別對(duì)待： 1.圖a中訪問(wèn)的是一個(gè)左孩子，按中序遍歷順序，接下來(lái)應(yīng)訪問(wèn)它的根節(jié)點(diǎn)。也就是圖a中的另一個(gè)節(jié)點(diǎn)，高興的是它已被保存在棧中。我們只需這樣的代碼和上一步一樣的代碼： [cpp]?view plain?copy
2.再看圖b，由于沒(méi)有左孩子，根節(jié)點(diǎn)就是中序序列中第一個(gè)，然后直接是進(jìn)入右子樹(shù)：p=p->rchild;在右子樹(shù)中，又會(huì)新一輪的代碼段(i)、代碼段(ii)……直到棧空且p空。 思維到這里，似乎很不清晰，真的要區(qū)分嗎？根據(jù)圖a接下來(lái)的代碼段(ii)這樣的： [cpp]?view plain?copy
根據(jù)圖b，代碼段(ii)又是這樣的： [cpp]?view plain?copy
我們可小結(jié)下：遍歷過(guò)程是個(gè)循環(huán)，并且按代碼段(i)、代碼段(ii)構(gòu)成一次循環(huán)體，循環(huán)直到棧空且p空為止。?? 不同的處理方法很讓人抓狂，可統(tǒng)一處理嗎？真的是可以的！回顧擴(kuò)充二叉樹(shù)，是不是每個(gè)節(jié)點(diǎn)都可以看成是根節(jié)點(diǎn)呢？那么，代碼只需統(tǒng)一寫成圖b的這種形式。也就是說(shuō)代碼段(ii)統(tǒng)一是這樣的：
中序代碼段(ii)? ?
[cpp]?view plain?copy口說(shuō)無(wú)憑，得經(jīng)的過(guò)理論檢驗(yàn)。 圖a的代碼段(ii)也可寫成圖b的理由是：由于是葉子節(jié)點(diǎn)，p=-=p->rchild;之后p肯定為空。為空，還需經(jīng)過(guò)新一輪的代碼段(i)嗎？顯然不需。(因?yàn)椴粷M足循環(huán)條件)那就直接進(jìn)入代碼段(ii)。看！最后還是一樣的吧。還是連續(xù)出棧兩次。看到這里，要仔細(xì)想想哦！相信你一定會(huì)明白的。
這時(shí)寫出遍歷循環(huán)體就不難了：? ?? [cpp]?view plain?copy
仔細(xì)想想，上述代碼是不是根據(jù)我們的思維走向而寫出來(lái)的呢？再加上邊界條件的檢測(cè)，中序遍歷非遞歸形式的完整代碼是這樣的：
中序遍歷代碼一 ?? ? ?? ?
[cpp]?view plain?copy恭喜你，你已經(jīng)完成了中序遍歷非遞歸形式的代碼了。回顧一下難嗎？ 接下來(lái)的這份代碼，本質(zhì)上是一樣的，相信不用我解釋，你也能看懂的。
中序遍歷代碼二? ?
[cpp]?view plain?copy前序遍歷
分析
前序遍歷的遞歸定義：先根節(jié)點(diǎn)，后左子樹(shù)，再右子樹(shù)。有了中序遍歷的基礎(chǔ)，不用我再像中序遍歷那樣引導(dǎo)了吧。 首先，我們遍歷左子樹(shù)，邊遍歷邊打印，并把根節(jié)點(diǎn)存入棧中，以后需借助這些節(jié)點(diǎn)進(jìn)入右子樹(shù)開(kāi)啟新一輪的循環(huán)。還得重復(fù)一句：所有的節(jié)點(diǎn)都可看做是根節(jié)點(diǎn)。根據(jù)思維走向，寫出代碼段(i):前序代碼段(i)
[cpp]?view plain?copy接下來(lái)就是：出棧，根據(jù)棧頂節(jié)點(diǎn)進(jìn)入右子樹(shù)。
前序代碼段(ii)???
[cpp]?view plain?copy同樣地，代碼段(i)(ii)構(gòu)成了一次完整的循環(huán)體。至此，不難寫出完整的前序遍歷的非遞歸寫法。
前序遍歷代碼一? ?
[cpp]?view plain?copy下面給出，本質(zhì)是一樣的另一段代碼：
前序遍歷代碼二? ??
[cpp]?view plain?copy在二叉樹(shù)中使用的是這樣的寫法，略有差別，本質(zhì)上也是一樣的：
前序遍歷代碼三?
[cpp]?view plain?copy
后序遍歷
分析
后序遍歷遞歸定義：先左子樹(shù)，后右子樹(shù)，再根節(jié)點(diǎn)。后序遍歷的難點(diǎn)在于：需要判斷上次訪問(wèn)的節(jié)點(diǎn)是位于左子樹(shù)，還是右子樹(shù)。若是位于左子樹(shù)，則需跳過(guò)根節(jié)點(diǎn)，先進(jìn)入右子樹(shù)，再回頭訪問(wèn)根節(jié)點(diǎn)；若是位于右子樹(shù)，則直接訪問(wèn)根節(jié)點(diǎn)。直接看代碼，代碼中有詳細(xì)的注釋。后序遍歷代碼一? ?
[cpp]?view plain?copy下面給出另一種思路下的代碼。它的想法是：給每個(gè)節(jié)點(diǎn)附加一個(gè)標(biāo)記(left,right)。如果該節(jié)點(diǎn)的左子樹(shù)已被訪問(wèn)過(guò)則置標(biāo)記為left；若右子樹(shù)被訪問(wèn)過(guò)，則置標(biāo)記為right。顯然，只有當(dāng)節(jié)點(diǎn)的標(biāo)記位是right時(shí)，才可訪問(wèn)該節(jié)點(diǎn)；否則，必須先進(jìn)入它的右子樹(shù)。詳細(xì)細(xì)節(jié)看代碼中的注釋。
后序遍歷代碼二
[cpp]?view plain?copy總結(jié)
思維和代碼之間總是有巨大的鴻溝。通常是思維正確，清楚，但卻不易寫出正確的代碼。要想越過(guò)這鴻溝，只有多嘗試、多借鑒，別無(wú)它法。 以下幾點(diǎn)是理解上述代碼的關(guān)鍵：轉(zhuǎn)載請(qǐng)注明出處，本文地址：http://blog.csdn.net/zhangxiangdavaid/article/details/37115355
總結(jié)
以上是生活随笔為你收集整理的二叉树前序、中序、后序遍历非递归写法的透彻解析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 伍德里奇计量经济学导论之计算机操作题的R
- 下一篇： ZerMQ安装与使用