現(xiàn)二叉樹中序后序非遞歸遍歷，棧模擬與標(biāo)記法詳解)
直接看標(biāo)題就知道這題沒少折騰人。作為數(shù)據(jù)結(jié)構(gòu)課的經(jīng)典算法實(shí)操二叉樹的中序、后序非遞歸遍歷用C語言實(shí)現(xiàn)幾乎是每一個(gè)學(xué)計(jì)算機(jī)的人繞不過去的坎。遞歸版本三行代碼寫完但一到非遞歸很多朋友就卡住了特別是后序硬是想不明白那個(gè)“第二次經(jīng)過節(jié)點(diǎn)”怎么判斷。這篇文章我用C語言把這倆遍歷給你徹底講透。不繞彎子直接講棧模擬的思路、節(jié)點(diǎn)狀態(tài)標(biāo)記以及我在調(diào)試過程中踩過的坑。適合正在學(xué)數(shù)據(jù)結(jié)構(gòu)的本科生、準(zhǔn)備考研或面試刷算法的人也適合那些學(xué)完就忘、想一次性看明白的朋友。1. 既然遞歸能解決為什么還要用非遞歸先回答一個(gè)問得最多的問題遞歸它不香嗎中序遞歸十行代碼后序遞歸也就十行為什么要費(fèi)勁去手工模擬棧答案取決于應(yīng)用場景。遞歸本質(zhì)上是使用系統(tǒng)調(diào)用棧每次函數(shù)調(diào)用都會(huì)發(fā)生壓棧、跳轉(zhuǎn)、返回、彈棧這一整套動(dòng)作而且棧幀里還要保存局部變量、參數(shù)和返回地址。當(dāng)二叉樹深度比較大的時(shí)候遞歸版本很容易把調(diào)用棧撐爆。我在實(shí)際開發(fā)里沒少被這種問題坑過Linux線程默認(rèn)棧大小只有8MB如果樹退化成一個(gè)長鏈深度到十萬、百萬級(jí)遞歸基本就game over了。非遞歸遍歷把“?！睆南到y(tǒng)調(diào)用棧換成了程序員自己管理的數(shù)據(jù)結(jié)構(gòu)內(nèi)存分配可控不會(huì)出現(xiàn)不可預(yù)期的爆棧。更重要的是非遞歸的每個(gè)步驟都是顯式的不像遞歸那樣把邏輯藏在函數(shù)調(diào)用里。在某些對性能要求苛刻的場景比如嵌入式開發(fā)、實(shí)時(shí)系統(tǒng)里少一次函數(shù)調(diào)用少一層棧幀就是實(shí)打?qū)嵉男阅苁找妗Ｔ儆芯褪敲嬖嚭涂荚?。非遞歸遍歷是面試官非常喜歡考察的點(diǎn)因?yàn)樗苤苯訖z驗(yàn)?zāi)闶欠裾嬲斫饬吮闅v的本質(zhì)而不只是會(huì)背遞歸模板。能不能用自己的話講清楚中序和后序的入棧、出棧時(shí)機(jī)基本上決定了這道題能不能拿滿分。理解非遞歸遍歷的前提是搞清楚遞歸版本到底做了什么。中序遞歸的順序是先往左走到底打印再往右走。后序遞歸的順序是先往左走到底再往右走到底最后打印。我們非遞歸要做的事情就是用一個(gè)顯式棧把遞歸版本的隱式邏輯給復(fù)刻出來。2. 準(zhǔn)備工作棧結(jié)構(gòu)、節(jié)點(diǎn)定義與輔助函數(shù)既然是C語言實(shí)現(xiàn)準(zhǔn)備工作就得做得扎實(shí)。C語言沒有現(xiàn)成的泛型棧容器不像C里面有std::stack可以直接用所以一切從零開始。2.1 二叉樹節(jié)點(diǎn)的結(jié)構(gòu)體定義二叉樹的節(jié)點(diǎn)結(jié)構(gòu)體定義沒有什么爭議常見的形式是這樣的typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;這里我用的數(shù)據(jù)域是int類型方便測試和調(diào)試。如果你需要存儲(chǔ)其他類型替換data的類型即可。在真正的實(shí)戰(zhàn)代碼中data字段可能會(huì)是一個(gè)結(jié)構(gòu)體、字符串甚至是一個(gè)用戶自定義類型但遍歷邏輯是完全一樣的。2.2 棧結(jié)構(gòu)的設(shè)計(jì)棧的結(jié)構(gòu)有兩種方案。一種是固定數(shù)組棧簡單高效適合節(jié)點(diǎn)數(shù)量已知或可預(yù)估的情況。另一種是鏈?zhǔn)綏?dòng)態(tài)分配內(nèi)存不受初始容量限制代碼稍微復(fù)雜一點(diǎn)。我在實(shí)際操作中更推薦數(shù)組棧理由很簡單性能好代碼直觀調(diào)試時(shí)也能直接看整個(gè)棧的內(nèi)容。固定大小取一個(gè)足夠大的值就行比如1000個(gè)節(jié)點(diǎn)。但如果你的二叉樹可能非常大那就考慮鏈?zhǔn)綏１苊鈼Ｒ绯龅膯栴}。數(shù)組棧的定義如下#define MAX_SIZE 1000 typedef struct { BiTNode *data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int isFull(Stack *s) { return s-top MAX_SIZE - 1; } void push(Stack *s, BiTNode *node) { if (isFull(s)) { printf(棧已滿無法入棧\n); return; } s-data[(s-top)] node; } BiTNode *pop(Stack *s) { if (isEmpty(s)) { printf(棧為空無法出棧\n); return NULL; } return s-data[(s-top)--]; } BiTNode *getTop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[s-top]; }這里有一個(gè)細(xì)節(jié)需要特別注意棧頂指針top的初始值。我習(xí)慣把top初始化為-1這樣入棧時(shí)先加一再存數(shù)據(jù)出棧時(shí)先取數(shù)據(jù)再減一。數(shù)組下標(biāo)從0開始存第一個(gè)元素邏輯上非常清晰。2.3 測試用二叉樹為了驗(yàn)證代碼我定義了這樣一棵二叉樹1 / \ 2 3 / \ \ 4 5 6中序遍歷的結(jié)果應(yīng)該是4 2 5 1 3 6。 后序遍歷的結(jié)果應(yīng)該是4 5 2 6 3 1。建樹的核心代碼大概是這樣的BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); node-data data; node-lchild NULL; node-rchild NULL; return node; } BiTree createTree() { BiTNode *node1 createNode(1); BiTNode *node2 createNode(2); BiTNode *node3 createNode(3); BiTNode *node4 createNode(4); BiTNode *node5 createNode(5); BiTNode *node6 createNode(6); node1-lchild node2; node1-rchild node3; node2-lchild node4; node2-rchild node5; node3-rchild node6; return node1; }后序遍歷時(shí)3號(hào)節(jié)點(diǎn)的左孩子為空右孩子是6號(hào)節(jié)點(diǎn)。這種“一邊為空另一邊非空”的結(jié)構(gòu)正好用來驗(yàn)證后序遍歷的細(xì)節(jié)有沒有寫對。3. 中序非遞歸遍歷的完整實(shí)現(xiàn)中序非遞歸遍歷的思路相對好理解。說是“中序”規(guī)則就是先處理左子樹再處理當(dāng)前節(jié)點(diǎn)最后處理右子樹。那么用棧模擬時(shí)核心思想就是“沿著左子樹一直往下走一路把節(jié)點(diǎn)都?jí)喝霔Ｖ兄钡阶笞訕錇榭杖缓髲棾鰲ｍ敼?jié)點(diǎn)訪問再轉(zhuǎn)向右子樹繼續(xù)這個(gè)過程”。3.1 中序非遞歸遍歷的代碼中序非遞歸遍歷的典型代碼如下void inOrder(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { // 一直向左走到頭沿途節(jié)點(diǎn)全部入棧 while (p ! NULL) { push(s, p); p p-lchild; } // 此時(shí)p為空彈出棧頂元素并訪問 if (!isEmpty(s)) { p pop(s); printf(%d , p-data); // 轉(zhuǎn)向右子樹 p p-rchild; } } printf(\n); }3.2 逐步拆解執(zhí)行過程我拿上面定義好的二叉樹來走一遍流程幫你直觀感受代碼的運(yùn)行邏輯。第一次進(jìn)入外層while循環(huán)時(shí)p指向根節(jié)點(diǎn)1。內(nèi)層while循環(huán)開始節(jié)點(diǎn)1入棧p指向節(jié)點(diǎn)2節(jié)點(diǎn)2入棧p指向節(jié)點(diǎn)4節(jié)點(diǎn)4入棧p指向NULL。此時(shí)棧從底到頂依次是[1, 2, 4]。內(nèi)層循環(huán)結(jié)束因?yàn)閜為NULL。進(jìn)入if語句彈出棧頂節(jié)點(diǎn)4打印4p轉(zhuǎn)向節(jié)點(diǎn)4的右孩子也就是NULL。回到外層循環(huán)判斷條件p為NULL但棧不為空條件成立繼續(xù)循環(huán)。再次進(jìn)入內(nèi)層whilep為NULL直接跳過。彈出棧頂節(jié)點(diǎn)2打印2p轉(zhuǎn)向節(jié)點(diǎn)2的右孩子也就是節(jié)點(diǎn)5。第三輪外層循環(huán)p指向節(jié)點(diǎn)5。內(nèi)層while節(jié)點(diǎn)5入棧p指向節(jié)點(diǎn)5的左孩子NULL。彈出節(jié)點(diǎn)5打印5p指向NULL。第四輪外層循環(huán)p為NULL棧不為空。彈出棧頂節(jié)點(diǎn)1打印1p指向節(jié)點(diǎn)3。第五輪外層循環(huán)p指向節(jié)點(diǎn)3。內(nèi)層while節(jié)點(diǎn)3入棧p指向節(jié)點(diǎn)3的左孩子NULL。彈出節(jié)點(diǎn)3打印3p指向節(jié)點(diǎn)3的右孩子6。第六輪外層循環(huán)p指向節(jié)點(diǎn)6。內(nèi)層while節(jié)點(diǎn)6入棧p指向NULL。彈出節(jié)點(diǎn)6打印6p指向NULL。第七輪外層循環(huán)p為NULL棧為空循環(huán)結(jié)束。最終輸出結(jié)果為4 2 5 1 3 6完全正確。3.3 中序非遞歸遍歷的關(guān)鍵技巧與易錯(cuò)點(diǎn)中序非遞歸遍歷的代碼結(jié)構(gòu)很清晰就是兩層循環(huán)套一個(gè)if。但越是這種看起來簡單的代碼越容易在細(xì)節(jié)上出問題。第一個(gè)容易踩的坑是外層while條件。這里必須是p ! NULL || !isEmpty(s)兩個(gè)條件缺一不可。如果寫成while(p ! NULL)處理到一半就會(huì)死循環(huán)或者漏節(jié)點(diǎn)。如果寫成while(!isEmpty(s))初始時(shí)p指向根節(jié)點(diǎn)而棧為空條件可能直接不成立。我見過不少朋友把這個(gè)邊界條件搞錯(cuò)導(dǎo)致代碼在某種輸入下就是輸出不對。第二個(gè)需要注意的點(diǎn)是訪問節(jié)點(diǎn)和轉(zhuǎn)向右子樹的順序。彈出節(jié)點(diǎn)后先printf打印然后p p-rchild。這個(gè)順序不能反過來。如果先讓p p-rchild那當(dāng)前節(jié)點(diǎn)就沒機(jī)會(huì)打印了遍歷順序就變了。第三個(gè)技巧是內(nèi)層while循環(huán)“當(dāng)前節(jié)點(diǎn)非空就入棧并走向左孩子”這個(gè)模式。這個(gè)模式其實(shí)是遍歷算法里的核心理解透了這個(gè)后面的后序遍歷會(huì)稍微輕松一點(diǎn)。如果把非遞歸遍歷比作開車內(nèi)層while就是在國道上一直往左開到底遇到路就走直到?jīng)]路為止pop操作就是回到上一個(gè)路口看看有沒有右轉(zhuǎn)的機(jī)會(huì)。4. 后序非遞歸遍歷兩種實(shí)現(xiàn)方案后序非遞歸遍歷的難度要比中序高一個(gè)檔次。原因很簡單后序遍歷的順序是左子樹、右子樹、根節(jié)點(diǎn)。這意味著根節(jié)點(diǎn)必須在左右子樹都處理完之后才能打印。在棧里面根節(jié)點(diǎn)會(huì)被“經(jīng)過”兩次第一次是從左子樹返回第二次是從右子樹返回。只有第二次經(jīng)過的時(shí)候才能打印根節(jié)點(diǎn)。問題來了我們怎么區(qū)分當(dāng)前是從左子樹返回還是從右子樹返回解決辦法有兩個(gè)方向。一是用標(biāo)記法在棧里額外記錄每個(gè)節(jié)點(diǎn)的訪問狀態(tài)二是用兩個(gè)棧用空間換邏輯的簡潔性。4.1 標(biāo)記法用輔助狀態(tài)記錄遍歷階段標(biāo)記法的核心思路是棧里存的不僅僅是節(jié)點(diǎn)指針還多存一個(gè)狀態(tài)字段表示當(dāng)前正在處理這個(gè)節(jié)點(diǎn)的哪個(gè)階段。0表示“左子樹還沒處理完剛?cè)霔！?表示“左子樹處理完了正在處理右子樹”2表示“左右子樹都處理完了可以打印”。我先定義棧元素結(jié)構(gòu)體typedef struct { BiTNode *node; int tag; } StackElement;對應(yīng)的棧定義和操作也稍作調(diào)整這里不再重復(fù)寫核心變化就是data數(shù)組的類型從BiTNode *變成StackElement。后序標(biāo)記法的核心遍歷代碼void postOrderWithTag(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { // 一直向左走到頭把沿途節(jié)點(diǎn)標(biāo)記為0入棧 while (p ! NULL) { StackElement elem; elem.node p; elem.tag 0; push(s, elem); p p-lchild; } // 查看棧頂元素 if (!isEmpty(s)) { StackElement *top (s.data[s.top]); // 如果從左子樹返回標(biāo)記為0則轉(zhuǎn)向右子樹標(biāo)記改為1 if (top-tag 0) { top-tag 1; p top-node-rchild; } else { // tag為1說明左右子樹都處理完了出棧并打印 printf(%d , top-node-data); pop(s); p NULL; } } } printf(\n); }這段代碼的關(guān)鍵在于當(dāng)tag為0時(shí)遇到棧頂節(jié)點(diǎn)不彈出只是把tag改為1然后嘗試走入右子樹。這樣就保證了根節(jié)點(diǎn)在棧里多待了一輪。當(dāng)右子樹處理完之后回到這個(gè)節(jié)點(diǎn)時(shí)tag已經(jīng)是1了這時(shí)才彈出打印。4.2 兩個(gè)棧實(shí)現(xiàn)后序遍歷相比標(biāo)記法兩個(gè)棧的實(shí)現(xiàn)思路更巧妙且代碼更好寫。我們先回憶一下后序的順序是左、右、根。如果反過來看就是根、右、左。那根、右、左這個(gè)順序恰恰是“先序變體”——先訪問根再訪問右子樹最后訪問左子樹。所以我們有這樣一個(gè)思路用第一個(gè)棧按照“根、右、左”的順序遍歷把訪問到的節(jié)點(diǎn)全部壓入第二個(gè)棧。最后把第二個(gè)棧里的內(nèi)容從頭彈出得到的就是“左、右、根”的正序后序遍歷。void postOrderTwoStacks(BiTree root) { if (root NULL) { return; } Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTNode *p pop(s1); push(s2, p); // 注意壓棧順序先壓左孩子再壓右孩子 // 這樣彈出的時(shí)候就先彈右孩子再彈左孩子 // 保證s1彈出的順序是根、右、左 if (p-lchild ! NULL) { push(s1, p-lchild); } if (p-rchild ! NULL) { push(s1, p-rchild); } } // 現(xiàn)在從s2中依次彈出打印的順序?yàn)樽蟆⒂?、?while (!isEmpty(s2)) { BiTNode *p pop(s2); printf(%d , p-data); } printf(\n); }這個(gè)方法代碼邏輯上非常優(yōu)雅不需要額外的狀態(tài)標(biāo)記也沒有判斷分支。缺點(diǎn)是空間上多用一個(gè)棧。我在實(shí)際寫代碼的時(shí)候也更傾向于這種方法因?yàn)檫壿嫼猛评聿蝗菀讓戝e(cuò)。4.3 對比兩種方案怎么選標(biāo)記法是更通用的方案因?yàn)樗梢詳U(kuò)展到任意需要知道節(jié)點(diǎn)被訪問次數(shù)的場景里。兩個(gè)棧的方法雖然簡潔但本質(zhì)上改變了思考問題的角度適用面要窄一些。從可讀性角度來說兩個(gè)棧實(shí)現(xiàn)的代碼幾乎不需要長篇注釋一眼就能看懂在干什么。從內(nèi)存效率來說標(biāo)記法只用了一個(gè)棧但棧元素要多存一個(gè)int類型字段。兩個(gè)?？赡苄枰玫蕉兜膬?nèi)存控件雖然在大多數(shù)場景下根本不是問題。如果是在面試中遇到這道題我建議優(yōu)先用兩個(gè)棧的方法因?yàn)榇a簡潔、邏輯清晰、不容易出錯(cuò)。如果是自己學(xué)習(xí)或者要在嵌入式這種資源受限的環(huán)境里實(shí)現(xiàn)那標(biāo)記法更合適。4.4 后序非遞歸遍歷的執(zhí)行過程拆解我用兩個(gè)棧的方法手動(dòng)走一遍上面那棵樹的過程。初始狀態(tài)s1里壓入節(jié)點(diǎn)1s2為空。第一步從s1彈出節(jié)點(diǎn)1打印內(nèi)容暫存入s2再將節(jié)點(diǎn)1的左孩子2和右孩子3依次壓入s1。注意壓入順序是先左后右所以s1棧頂是3。第二步從s1彈出節(jié)點(diǎn)3壓入s2。節(jié)點(diǎn)3的左孩子為空跳過右孩子6壓入s1。此時(shí)s1棧頂是6。第三步彈出節(jié)點(diǎn)6壓入s2。節(jié)點(diǎn)6沒有孩子。第四步此時(shí)s1彈出節(jié)點(diǎn)2壓入s2。節(jié)點(diǎn)2的左孩子4和右孩子5依次壓入s1先左后右所以棧頂是5。第五步彈出節(jié)點(diǎn)5壓入s2。第六步彈出節(jié)點(diǎn)4壓入s2。此時(shí)s1為空。s2從棧底到棧頂依次是1、3、6、2、5、4。注意這里的順序正好和正序后序相反所以依次彈出打印為4、5、2、6、3、1與理論結(jié)果完全一致。5. 常見問題與排查技巧實(shí)錄非遞歸遍歷代碼看起來不長但真調(diào)試起來還是有不少容易卡住的點(diǎn)。我把自己踩過的坑和平時(shí)答疑時(shí)遇到的高頻問題整理出來按問題現(xiàn)象和解決辦法對照著寫。5.1 輸出結(jié)果完全不對或者死循環(huán)如果你發(fā)現(xiàn)輸出完全不是自己預(yù)期的那樣甚至連打印都沒有大概率是外層while循環(huán)的條件寫錯(cuò)了。檢查一下是不是漏掉了p ! NULL這個(gè)條件或者把邏輯或?qū)懗闪诉壿嬇c。這種情況我在調(diào)試的時(shí)候一般會(huì)先在代碼里加入調(diào)試輸出在每次入棧、出棧時(shí)打印當(dāng)前節(jié)點(diǎn)值和棧的變化情況。看到棧的變化過程問題基本一眼就能定位。5.2 后序遍歷時(shí)某個(gè)節(jié)點(diǎn)提前打印了這種現(xiàn)象很典型。比如中序輸出是對的后序卻把根節(jié)點(diǎn)打印在中間而不是最后。問題基本出在標(biāo)記法的tag狀態(tài)沒有正確流轉(zhuǎn)。檢查一下是不是在tag為0的時(shí)候就把節(jié)點(diǎn)彈出了正確的做法是tag為0的時(shí)候只改tag并轉(zhuǎn)向右子樹不能彈出節(jié)點(diǎn)。如果用兩個(gè)棧的方法根節(jié)點(diǎn)不可能提前打印因?yàn)楦?jié)點(diǎn)一定是最后被打包進(jìn)s2的所以它必然是s2的棧底最后一個(gè)彈出。5.3 棧滿了怎么辦如果設(shè)定的MAX_SIZE太小而樹的節(jié)點(diǎn)數(shù)量超過了這個(gè)限制push的時(shí)候就會(huì)輸出“棧已滿無法入?！?。這種情況下有兩種解決辦法。一是把MAX_SIZE調(diào)大比如從1000改成100000簡單粗暴。二是改成動(dòng)態(tài)擴(kuò)容的?；蛘咧苯佑面?zhǔn)綏！Ｎ覀€(gè)人在做算法題的時(shí)候傾向于直接把數(shù)組開大一點(diǎn)因?yàn)楣?jié)點(diǎn)數(shù)量一般不會(huì)超過十萬1e5的數(shù)組在現(xiàn)代編譯器上毫無壓力。5.4 樹是空樹時(shí)怎么辦空樹是一個(gè)非常容易忽略的邊界條件。如果你的代碼在root為NULL的時(shí)候直接崩了那肯定是忘了在最開頭加判空邏輯。中序代碼里root為NULL時(shí)p初始就為NULL同時(shí)棧為空外層while條件不成立直接結(jié)束不會(huì)崩。但兩個(gè)棧的方法中一開始就把root壓入s1所以必須要提前判空。if (root NULL) { return; }這段代碼必須有。5.5 野指針問題C語言的經(jīng)典難題野指針。在非遞歸遍歷中野指針最容易出現(xiàn)在創(chuàng)建節(jié)點(diǎn)和釋放節(jié)點(diǎn)的時(shí)候。創(chuàng)建節(jié)點(diǎn)時(shí)malloc之后一定要檢查返回的指針是否為NULL。釋放節(jié)點(diǎn)時(shí)一定要先把子節(jié)點(diǎn)處理完再釋放當(dāng)前節(jié)點(diǎn)否則會(huì)造成訪問已釋放內(nèi)存的問題。BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); if (node NULL) { printf(內(nèi)存分配失敗\n); exit(1); } node-data data; node-lchild NULL; node-rchild NULL; return node; }另外malloc出來的節(jié)點(diǎn)一定要記得初始化lchild和rchild為NULL否則在判斷孩子是否存在時(shí)會(huì)讀到隨機(jī)值導(dǎo)致程序行為詭異。5.6 二叉樹退化成鏈表時(shí)的表現(xiàn)如果二叉樹退化成了一條單鏈表比如每個(gè)節(jié)點(diǎn)都只有左孩子那非遞歸遍歷的時(shí)間復(fù)雜度仍然是O(n)空間復(fù)雜度是O(n)。但如果是遞歸實(shí)現(xiàn)這個(gè)場景就非常容易爆棧。我實(shí)測過遞歸中序遍歷一個(gè)10萬層深的單鏈樹基本上直接段錯(cuò)誤。非遞歸版本用數(shù)組棧大概在1000萬層以上才會(huì)碰到棧容量問題1000萬以內(nèi)的深度完全沒壓力。這也是為什么在一些極端數(shù)據(jù)結(jié)構(gòu)下非遞歸遍歷幾乎是唯一選擇。6. 一個(gè)通用的五步解題法學(xué)完中序和后序的非遞歸遍歷我總結(jié)了一套通用的解題思路適配前序、中序、后序三種非遞歸遍歷。這是一個(gè)方法論層面的總結(jié)希望幫你看清楚本質(zhì)。第一步先把遍歷順序用文字寫出來。前序是“根左右”中序是“左根右”后序是“左右根”。第二步想一想在這個(gè)順序里哪些節(jié)點(diǎn)需要暫時(shí)存起來等后面再處理。一般來說只要某個(gè)子樹的根節(jié)點(diǎn)不是優(yōu)先打印它就需要放到棧里等待。中序和后序里根節(jié)點(diǎn)都不會(huì)被優(yōu)先打印所以都需要壓棧。第三步?jīng)Q定棧里需要額外存儲(chǔ)什么信息。如果只存節(jié)點(diǎn)指針就夠那是中序這種簡單的場景。如果需要區(qū)分左右子樹是否處理完就需要額外存tag標(biāo)記或者用兩個(gè)棧來規(guī)避。第四步寫出“往左走到頭、沿途入?！钡墓羌艽a。中序、后序的最外層邏輯基本一致變化的只是出棧之后打印的時(shí)機(jī)和轉(zhuǎn)向右子樹的方式。第五步根據(jù)不同的順序調(diào)整打印時(shí)機(jī)。中序是彈出時(shí)打印后序是右子樹處理完后打印。這套分析法對學(xué)習(xí)其他樹的遍歷也有幫助比如線索二叉樹、N叉樹遍歷本質(zhì)上還是在問什么時(shí)候打印什么時(shí)候轉(zhuǎn)向需要什么額外的狀態(tài)信息。7. 優(yōu)化與擴(kuò)展不只是寫對還要寫得好代碼寫對的下一步是寫得好。有兩個(gè)優(yōu)化方向值得花時(shí)間琢磨。第一個(gè)優(yōu)化方向是把內(nèi)存分配降到最低。在嵌入式開發(fā)和系統(tǒng)編程里malloc和free都是有代價(jià)的頻繁調(diào)用會(huì)造成內(nèi)存碎片。如果樹是預(yù)先構(gòu)建好且大小已知的可以直接在棧區(qū)聲明一個(gè)固定大小的節(jié)點(diǎn)指針數(shù)組完全避免動(dòng)態(tài)分配。第二個(gè)優(yōu)化方向是模板化。樹節(jié)點(diǎn)的data類型不一定是int可能是char、字符串、自定義結(jié)構(gòu)體。你可以把typedef改成泛型類型用void*指向數(shù)據(jù)然后用宏定義或者函數(shù)指針來實(shí)現(xiàn)通用容器。這種做法在大型項(xiàng)目里比較常見但純C語言里會(huì)犧牲一些類型安全需要自己權(quán)衡。第三個(gè)擴(kuò)展點(diǎn)是層級(jí)遍歷。非遞歸遍歷并不局限于棧用隊(duì)列實(shí)現(xiàn)的層序遍歷也是面試常客。層序遍歷的順序是一層一層從左到右用隊(duì)列保存當(dāng)前層的節(jié)點(diǎn)然后依次處理。理解了中序和后序的棧式遍歷隊(duì)列版層序遍歷本質(zhì)上是同一個(gè)思路——用數(shù)據(jù)結(jié)構(gòu)來模擬“下一個(gè)該訪問誰”的調(diào)度邏輯。我在處理實(shí)際問題的時(shí)候還有一個(gè)習(xí)慣用一個(gè)公共的打印函數(shù)或者統(tǒng)一的遍歷接口把不同遍歷方式的結(jié)果輸出成同樣的格式。調(diào)試的時(shí)候切換遍歷方式快得多不用每個(gè)函數(shù)里都重寫一遍打印邏輯。8. 完整代碼匯總最后貼上完整代碼直接用GCC編譯就能跑。代碼里我不再分段拆解保持一個(gè)完整的可直接運(yùn)行的文件。#include stdio.h #include stdlib.h #define MAX_SIZE 1000 typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef struct { BiTNode *data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int isFull(Stack *s) { return s-top MAX_SIZE - 1; } void push(Stack *s, BiTNode *node) { if (isFull(s)) { printf(棧已滿無法入棧\n); return; } s-data[(s-top)] node; } BiTNode *pop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[(s-top)--]; } BiTNode *getTop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[s-top]; } BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); if (node NULL) { printf(內(nèi)存分配失敗\n); exit(1); } node-data data; node-lchild NULL; node-rchild NULL; return node; } BiTree createTree() { BiTNode *node1 createNode(1); BiTNode *node2 createNode(2); BiTNode *node3 createNode(3); BiTNode *node4 createNode(4); BiTNode *node5 createNode(5); BiTNode *node6 createNode(6); node1-lchild node2; node1-rchild node3; node2-lchild node4; node2-rchild node5; node3-rchild node6; return node1; } void inOrder(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { while (p ! NULL) { push(s, p); p p-lchild; } if (!isEmpty(s)) { p pop(s); printf(%d , p-data); p p-rchild; } } printf(\n); } void postOrder(BiTree root) { if (root NULL) { return; } Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTNode *p pop(s1); push(s2, p); if (p-lchild ! NULL) { push(s1, p-lchild); } if (p-rchild ! NULL) { push(s1, p-rchild); } } while (!isEmpty(s2)) { BiTNode *p pop(s2); printf(%d , p-data); } printf(\n); } int main() { BiTree root createTree(); printf(中序遍歷結(jié)果: ); inOrder(root); printf(后序遍歷結(jié)果: ); postOrder(root); return 0; }這個(gè)版本的代碼可以編譯后直接運(yùn)行。如果你在操作系統(tǒng)里跑注意把控制臺(tái)編碼調(diào)成UTF-8避免中文字符串亂碼。9. 從遍歷到更深層的理解掌握了中序和后序的非遞歸遍歷你其實(shí)已經(jīng)掌握了樹這種數(shù)據(jù)結(jié)構(gòu)里最核心的一類操作。樹的遍歷并不是孤立的它和遞歸、棧、隊(duì)列、狀態(tài)機(jī)這些知識(shí)點(diǎn)緊密相關(guān)。比如非遞歸遍歷里“標(biāo)記狀態(tài)”的思想后續(xù)在學(xué)習(xí)圖的深度優(yōu)先和廣度優(yōu)先搜索時(shí)還會(huì)再次遇到。DFS的棧實(shí)現(xiàn)、BFS的隊(duì)列實(shí)現(xiàn)本質(zhì)上是同一套邏輯在不同的數(shù)據(jù)結(jié)構(gòu)上的應(yīng)用。如果你準(zhǔn)備繼續(xù)深挖建議在紙上多畫幾棵樹手動(dòng)模擬五次以上的遍歷過程。很多人學(xué)不透遍歷的原因不是代碼難而是腦子里對“當(dāng)前代碼執(zhí)行到哪一步、棧里存了哪些節(jié)點(diǎn)”沒有一個(gè)直觀的畫面。把每一個(gè)入棧、出棧、轉(zhuǎn)向的動(dòng)作在紙上畫出來一遍不夠畫三遍三遍不夠畫五遍畫到能閉著眼睛說出每一步為止。這個(gè)過程很像學(xué)騎自行車?yán)碚撜f得再多不如真的蹬兩圈。我個(gè)人的體會(huì)是非遞歸遍歷不是一個(gè)可以靠死記硬背通過的題目它需要你在紙面上把節(jié)點(diǎn)狀態(tài)的變化過程徹底過一遍。等你想通了“棧頂節(jié)點(diǎn)的tag說明什么”“什么時(shí)候該轉(zhuǎn)向右子樹”這兩個(gè)問題后序遍歷就不再是攔路虎。再順手對比一下前序、中序、后序三種遍歷在棧結(jié)構(gòu)上的差別你會(huì)發(fā)現(xiàn)它們都是在回答同一個(gè)問題下一步該訪問誰。 C語言實(shí)現(xiàn)二叉樹中序后序非遞歸遍歷，棧模擬與標(biāo)記法詳解
直接看標(biāo)題就知道這題沒少折騰人。作為數(shù)據(jù)結(jié)構(gòu)課的經(jīng)典算法實(shí)操二叉樹的中序、后序非遞歸遍歷用C語言實(shí)現(xiàn)幾乎是每一個(gè)學(xué)計(jì)算機(jī)的人繞不過去的坎。遞歸版本三行代碼寫完但一到非遞歸很多朋友就卡住了特別是后序硬是想不明白那個(gè)“第二次經(jīng)過節(jié)點(diǎn)”怎么判斷。這篇文章我用C語言把這倆遍歷給你徹底講透。不繞彎子直接講棧模擬的思路、節(jié)點(diǎn)狀態(tài)標(biāo)記以及我在調(diào)試過程中踩過的坑。適合正在學(xué)數(shù)據(jù)結(jié)構(gòu)的本科生、準(zhǔn)備考研或面試刷算法的人也適合那些學(xué)完就忘、想一次性看明白的朋友。1. 既然遞歸能解決為什么還要用非遞歸先回答一個(gè)問得最多的問題遞歸它不香嗎中序遞歸十行代碼后序遞歸也就十行為什么要費(fèi)勁去手工模擬棧答案取決于應(yīng)用場景。遞歸本質(zhì)上是使用系統(tǒng)調(diào)用棧每次函數(shù)調(diào)用都會(huì)發(fā)生壓棧、跳轉(zhuǎn)、返回、彈棧這一整套動(dòng)作而且棧幀里還要保存局部變量、參數(shù)和返回地址。當(dāng)二叉樹深度比較大的時(shí)候遞歸版本很容易把調(diào)用棧撐爆。我在實(shí)際開發(fā)里沒少被這種問題坑過Linux線程默認(rèn)棧大小只有8MB如果樹退化成一個(gè)長鏈深度到十萬、百萬級(jí)遞歸基本就game over了。非遞歸遍歷把“?！睆南到y(tǒng)調(diào)用棧換成了程序員自己管理的數(shù)據(jù)結(jié)構(gòu)內(nèi)存分配可控不會(huì)出現(xiàn)不可預(yù)期的爆棧。更重要的是非遞歸的每個(gè)步驟都是顯式的不像遞歸那樣把邏輯藏在函數(shù)調(diào)用里。在某些對性能要求苛刻的場景比如嵌入式開發(fā)、實(shí)時(shí)系統(tǒng)里少一次函數(shù)調(diào)用少一層棧幀就是實(shí)打?qū)嵉男阅苁找妗Ｔ儆芯褪敲嬖嚭涂荚?。非遞歸遍歷是面試官非常喜歡考察的點(diǎn)因?yàn)樗苤苯訖z驗(yàn)?zāi)闶欠裾嬲斫饬吮闅v的本質(zhì)而不只是會(huì)背遞歸模板。能不能用自己的話講清楚中序和后序的入棧、出棧時(shí)機(jī)基本上決定了這道題能不能拿滿分。理解非遞歸遍歷的前提是搞清楚遞歸版本到底做了什么。中序遞歸的順序是先往左走到底打印再往右走。后序遞歸的順序是先往左走到底再往右走到底最后打印。我們非遞歸要做的事情就是用一個(gè)顯式棧把遞歸版本的隱式邏輯給復(fù)刻出來。2. 準(zhǔn)備工作棧結(jié)構(gòu)、節(jié)點(diǎn)定義與輔助函數(shù)既然是C語言實(shí)現(xiàn)準(zhǔn)備工作就得做得扎實(shí)。C語言沒有現(xiàn)成的泛型棧容器不像C里面有std::stack可以直接用所以一切從零開始。2.1 二叉樹節(jié)點(diǎn)的結(jié)構(gòu)體定義二叉樹的節(jié)點(diǎn)結(jié)構(gòu)體定義沒有什么爭議常見的形式是這樣的typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;這里我用的數(shù)據(jù)域是int類型方便測試和調(diào)試。如果你需要存儲(chǔ)其他類型替換data的類型即可。在真正的實(shí)戰(zhàn)代碼中data字段可能會(huì)是一個(gè)結(jié)構(gòu)體、字符串甚至是一個(gè)用戶自定義類型但遍歷邏輯是完全一樣的。2.2 棧結(jié)構(gòu)的設(shè)計(jì)棧的結(jié)構(gòu)有兩種方案。一種是固定數(shù)組棧簡單高效適合節(jié)點(diǎn)數(shù)量已知或可預(yù)估的情況。另一種是鏈?zhǔn)綏?dòng)態(tài)分配內(nèi)存不受初始容量限制代碼稍微復(fù)雜一點(diǎn)。我在實(shí)際操作中更推薦數(shù)組棧理由很簡單性能好代碼直觀調(diào)試時(shí)也能直接看整個(gè)棧的內(nèi)容。固定大小取一個(gè)足夠大的值就行比如1000個(gè)節(jié)點(diǎn)。但如果你的二叉樹可能非常大那就考慮鏈?zhǔn)綏１苊鈼Ｒ绯龅膯栴}。數(shù)組棧的定義如下#define MAX_SIZE 1000 typedef struct { BiTNode *data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int isFull(Stack *s) { return s-top MAX_SIZE - 1; } void push(Stack *s, BiTNode *node) { if (isFull(s)) { printf(棧已滿無法入棧\n); return; } s-data[(s-top)] node; } BiTNode *pop(Stack *s) { if (isEmpty(s)) { printf(棧為空無法出棧\n); return NULL; } return s-data[(s-top)--]; } BiTNode *getTop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[s-top]; }這里有一個(gè)細(xì)節(jié)需要特別注意棧頂指針top的初始值。我習(xí)慣把top初始化為-1這樣入棧時(shí)先加一再存數(shù)據(jù)出棧時(shí)先取數(shù)據(jù)再減一。數(shù)組下標(biāo)從0開始存第一個(gè)元素邏輯上非常清晰。2.3 測試用二叉樹為了驗(yàn)證代碼我定義了這樣一棵二叉樹1 / \ 2 3 / \ \ 4 5 6中序遍歷的結(jié)果應(yīng)該是4 2 5 1 3 6。 后序遍歷的結(jié)果應(yīng)該是4 5 2 6 3 1。建樹的核心代碼大概是這樣的BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); node-data data; node-lchild NULL; node-rchild NULL; return node; } BiTree createTree() { BiTNode *node1 createNode(1); BiTNode *node2 createNode(2); BiTNode *node3 createNode(3); BiTNode *node4 createNode(4); BiTNode *node5 createNode(5); BiTNode *node6 createNode(6); node1-lchild node2; node1-rchild node3; node2-lchild node4; node2-rchild node5; node3-rchild node6; return node1; }后序遍歷時(shí)3號(hào)節(jié)點(diǎn)的左孩子為空右孩子是6號(hào)節(jié)點(diǎn)。這種“一邊為空另一邊非空”的結(jié)構(gòu)正好用來驗(yàn)證后序遍歷的細(xì)節(jié)有沒有寫對。3. 中序非遞歸遍歷的完整實(shí)現(xiàn)中序非遞歸遍歷的思路相對好理解。說是“中序”規(guī)則就是先處理左子樹再處理當(dāng)前節(jié)點(diǎn)最后處理右子樹。那么用棧模擬時(shí)核心思想就是“沿著左子樹一直往下走一路把節(jié)點(diǎn)都?jí)喝霔Ｖ兄钡阶笞訕錇榭杖缓髲棾鰲ｍ敼?jié)點(diǎn)訪問再轉(zhuǎn)向右子樹繼續(xù)這個(gè)過程”。3.1 中序非遞歸遍歷的代碼中序非遞歸遍歷的典型代碼如下void inOrder(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { // 一直向左走到頭沿途節(jié)點(diǎn)全部入棧 while (p ! NULL) { push(s, p); p p-lchild; } // 此時(shí)p為空彈出棧頂元素并訪問 if (!isEmpty(s)) { p pop(s); printf(%d , p-data); // 轉(zhuǎn)向右子樹 p p-rchild; } } printf(\n); }3.2 逐步拆解執(zhí)行過程我拿上面定義好的二叉樹來走一遍流程幫你直觀感受代碼的運(yùn)行邏輯。第一次進(jìn)入外層while循環(huán)時(shí)p指向根節(jié)點(diǎn)1。內(nèi)層while循環(huán)開始節(jié)點(diǎn)1入棧p指向節(jié)點(diǎn)2節(jié)點(diǎn)2入棧p指向節(jié)點(diǎn)4節(jié)點(diǎn)4入棧p指向NULL。此時(shí)棧從底到頂依次是[1, 2, 4]。內(nèi)層循環(huán)結(jié)束因?yàn)閜為NULL。進(jìn)入if語句彈出棧頂節(jié)點(diǎn)4打印4p轉(zhuǎn)向節(jié)點(diǎn)4的右孩子也就是NULL。回到外層循環(huán)判斷條件p為NULL但棧不為空條件成立繼續(xù)循環(huán)。再次進(jìn)入內(nèi)層whilep為NULL直接跳過。彈出棧頂節(jié)點(diǎn)2打印2p轉(zhuǎn)向節(jié)點(diǎn)2的右孩子也就是節(jié)點(diǎn)5。第三輪外層循環(huán)p指向節(jié)點(diǎn)5。內(nèi)層while節(jié)點(diǎn)5入棧p指向節(jié)點(diǎn)5的左孩子NULL。彈出節(jié)點(diǎn)5打印5p指向NULL。第四輪外層循環(huán)p為NULL棧不為空。彈出棧頂節(jié)點(diǎn)1打印1p指向節(jié)點(diǎn)3。第五輪外層循環(huán)p指向節(jié)點(diǎn)3。內(nèi)層while節(jié)點(diǎn)3入棧p指向節(jié)點(diǎn)3的左孩子NULL。彈出節(jié)點(diǎn)3打印3p指向節(jié)點(diǎn)3的右孩子6。第六輪外層循環(huán)p指向節(jié)點(diǎn)6。內(nèi)層while節(jié)點(diǎn)6入棧p指向NULL。彈出節(jié)點(diǎn)6打印6p指向NULL。第七輪外層循環(huán)p為NULL棧為空循環(huán)結(jié)束。最終輸出結(jié)果為4 2 5 1 3 6完全正確。3.3 中序非遞歸遍歷的關(guān)鍵技巧與易錯(cuò)點(diǎn)中序非遞歸遍歷的代碼結(jié)構(gòu)很清晰就是兩層循環(huán)套一個(gè)if。但越是這種看起來簡單的代碼越容易在細(xì)節(jié)上出問題。第一個(gè)容易踩的坑是外層while條件。這里必須是p ! NULL || !isEmpty(s)兩個(gè)條件缺一不可。如果寫成while(p ! NULL)處理到一半就會(huì)死循環(huán)或者漏節(jié)點(diǎn)。如果寫成while(!isEmpty(s))初始時(shí)p指向根節(jié)點(diǎn)而棧為空條件可能直接不成立。我見過不少朋友把這個(gè)邊界條件搞錯(cuò)導(dǎo)致代碼在某種輸入下就是輸出不對。第二個(gè)需要注意的點(diǎn)是訪問節(jié)點(diǎn)和轉(zhuǎn)向右子樹的順序。彈出節(jié)點(diǎn)后先printf打印然后p p-rchild。這個(gè)順序不能反過來。如果先讓p p-rchild那當(dāng)前節(jié)點(diǎn)就沒機(jī)會(huì)打印了遍歷順序就變了。第三個(gè)技巧是內(nèi)層while循環(huán)“當(dāng)前節(jié)點(diǎn)非空就入棧并走向左孩子”這個(gè)模式。這個(gè)模式其實(shí)是遍歷算法里的核心理解透了這個(gè)后面的后序遍歷會(huì)稍微輕松一點(diǎn)。如果把非遞歸遍歷比作開車內(nèi)層while就是在國道上一直往左開到底遇到路就走直到?jīng)]路為止pop操作就是回到上一個(gè)路口看看有沒有右轉(zhuǎn)的機(jī)會(huì)。4. 后序非遞歸遍歷兩種實(shí)現(xiàn)方案后序非遞歸遍歷的難度要比中序高一個(gè)檔次。原因很簡單后序遍歷的順序是左子樹、右子樹、根節(jié)點(diǎn)。這意味著根節(jié)點(diǎn)必須在左右子樹都處理完之后才能打印。在棧里面根節(jié)點(diǎn)會(huì)被“經(jīng)過”兩次第一次是從左子樹返回第二次是從右子樹返回。只有第二次經(jīng)過的時(shí)候才能打印根節(jié)點(diǎn)。問題來了我們怎么區(qū)分當(dāng)前是從左子樹返回還是從右子樹返回解決辦法有兩個(gè)方向。一是用標(biāo)記法在棧里額外記錄每個(gè)節(jié)點(diǎn)的訪問狀態(tài)二是用兩個(gè)棧用空間換邏輯的簡潔性。4.1 標(biāo)記法用輔助狀態(tài)記錄遍歷階段標(biāo)記法的核心思路是棧里存的不僅僅是節(jié)點(diǎn)指針還多存一個(gè)狀態(tài)字段表示當(dāng)前正在處理這個(gè)節(jié)點(diǎn)的哪個(gè)階段。0表示“左子樹還沒處理完剛?cè)霔！?表示“左子樹處理完了正在處理右子樹”2表示“左右子樹都處理完了可以打印”。我先定義棧元素結(jié)構(gòu)體typedef struct { BiTNode *node; int tag; } StackElement;對應(yīng)的棧定義和操作也稍作調(diào)整這里不再重復(fù)寫核心變化就是data數(shù)組的類型從BiTNode *變成StackElement。后序標(biāo)記法的核心遍歷代碼void postOrderWithTag(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { // 一直向左走到頭把沿途節(jié)點(diǎn)標(biāo)記為0入棧 while (p ! NULL) { StackElement elem; elem.node p; elem.tag 0; push(s, elem); p p-lchild; } // 查看棧頂元素 if (!isEmpty(s)) { StackElement *top (s.data[s.top]); // 如果從左子樹返回標(biāo)記為0則轉(zhuǎn)向右子樹標(biāo)記改為1 if (top-tag 0) { top-tag 1; p top-node-rchild; } else { // tag為1說明左右子樹都處理完了出棧并打印 printf(%d , top-node-data); pop(s); p NULL; } } } printf(\n); }這段代碼的關(guān)鍵在于當(dāng)tag為0時(shí)遇到棧頂節(jié)點(diǎn)不彈出只是把tag改為1然后嘗試走入右子樹。這樣就保證了根節(jié)點(diǎn)在棧里多待了一輪。當(dāng)右子樹處理完之后回到這個(gè)節(jié)點(diǎn)時(shí)tag已經(jīng)是1了這時(shí)才彈出打印。4.2 兩個(gè)棧實(shí)現(xiàn)后序遍歷相比標(biāo)記法兩個(gè)棧的實(shí)現(xiàn)思路更巧妙且代碼更好寫。我們先回憶一下后序的順序是左、右、根。如果反過來看就是根、右、左。那根、右、左這個(gè)順序恰恰是“先序變體”——先訪問根再訪問右子樹最后訪問左子樹。所以我們有這樣一個(gè)思路用第一個(gè)棧按照“根、右、左”的順序遍歷把訪問到的節(jié)點(diǎn)全部壓入第二個(gè)棧。最后把第二個(gè)棧里的內(nèi)容從頭彈出得到的就是“左、右、根”的正序后序遍歷。void postOrderTwoStacks(BiTree root) { if (root NULL) { return; } Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTNode *p pop(s1); push(s2, p); // 注意壓棧順序先壓左孩子再壓右孩子 // 這樣彈出的時(shí)候就先彈右孩子再彈左孩子 // 保證s1彈出的順序是根、右、左 if (p-lchild ! NULL) { push(s1, p-lchild); } if (p-rchild ! NULL) { push(s1, p-rchild); } } // 現(xiàn)在從s2中依次彈出打印的順序?yàn)樽蟆⒂?、?while (!isEmpty(s2)) { BiTNode *p pop(s2); printf(%d , p-data); } printf(\n); }這個(gè)方法代碼邏輯上非常優(yōu)雅不需要額外的狀態(tài)標(biāo)記也沒有判斷分支。缺點(diǎn)是空間上多用一個(gè)棧。我在實(shí)際寫代碼的時(shí)候也更傾向于這種方法因?yàn)檫壿嫼猛评聿蝗菀讓戝e(cuò)。4.3 對比兩種方案怎么選標(biāo)記法是更通用的方案因?yàn)樗梢詳U(kuò)展到任意需要知道節(jié)點(diǎn)被訪問次數(shù)的場景里。兩個(gè)棧的方法雖然簡潔但本質(zhì)上改變了思考問題的角度適用面要窄一些。從可讀性角度來說兩個(gè)棧實(shí)現(xiàn)的代碼幾乎不需要長篇注釋一眼就能看懂在干什么。從內(nèi)存效率來說標(biāo)記法只用了一個(gè)棧但棧元素要多存一個(gè)int類型字段。兩個(gè)?？赡苄枰玫蕉兜膬?nèi)存控件雖然在大多數(shù)場景下根本不是問題。如果是在面試中遇到這道題我建議優(yōu)先用兩個(gè)棧的方法因?yàn)榇a簡潔、邏輯清晰、不容易出錯(cuò)。如果是自己學(xué)習(xí)或者要在嵌入式這種資源受限的環(huán)境里實(shí)現(xiàn)那標(biāo)記法更合適。4.4 后序非遞歸遍歷的執(zhí)行過程拆解我用兩個(gè)棧的方法手動(dòng)走一遍上面那棵樹的過程。初始狀態(tài)s1里壓入節(jié)點(diǎn)1s2為空。第一步從s1彈出節(jié)點(diǎn)1打印內(nèi)容暫存入s2再將節(jié)點(diǎn)1的左孩子2和右孩子3依次壓入s1。注意壓入順序是先左后右所以s1棧頂是3。第二步從s1彈出節(jié)點(diǎn)3壓入s2。節(jié)點(diǎn)3的左孩子為空跳過右孩子6壓入s1。此時(shí)s1棧頂是6。第三步彈出節(jié)點(diǎn)6壓入s2。節(jié)點(diǎn)6沒有孩子。第四步此時(shí)s1彈出節(jié)點(diǎn)2壓入s2。節(jié)點(diǎn)2的左孩子4和右孩子5依次壓入s1先左后右所以棧頂是5。第五步彈出節(jié)點(diǎn)5壓入s2。第六步彈出節(jié)點(diǎn)4壓入s2。此時(shí)s1為空。s2從棧底到棧頂依次是1、3、6、2、5、4。注意這里的順序正好和正序后序相反所以依次彈出打印為4、5、2、6、3、1與理論結(jié)果完全一致。5. 常見問題與排查技巧實(shí)錄非遞歸遍歷代碼看起來不長但真調(diào)試起來還是有不少容易卡住的點(diǎn)。我把自己踩過的坑和平時(shí)答疑時(shí)遇到的高頻問題整理出來按問題現(xiàn)象和解決辦法對照著寫。5.1 輸出結(jié)果完全不對或者死循環(huán)如果你發(fā)現(xiàn)輸出完全不是自己預(yù)期的那樣甚至連打印都沒有大概率是外層while循環(huán)的條件寫錯(cuò)了。檢查一下是不是漏掉了p ! NULL這個(gè)條件或者把邏輯或?qū)懗闪诉壿嬇c。這種情況我在調(diào)試的時(shí)候一般會(huì)先在代碼里加入調(diào)試輸出在每次入棧、出棧時(shí)打印當(dāng)前節(jié)點(diǎn)值和棧的變化情況。看到棧的變化過程問題基本一眼就能定位。5.2 后序遍歷時(shí)某個(gè)節(jié)點(diǎn)提前打印了這種現(xiàn)象很典型。比如中序輸出是對的后序卻把根節(jié)點(diǎn)打印在中間而不是最后。問題基本出在標(biāo)記法的tag狀態(tài)沒有正確流轉(zhuǎn)。檢查一下是不是在tag為0的時(shí)候就把節(jié)點(diǎn)彈出了正確的做法是tag為0的時(shí)候只改tag并轉(zhuǎn)向右子樹不能彈出節(jié)點(diǎn)。如果用兩個(gè)棧的方法根節(jié)點(diǎn)不可能提前打印因?yàn)楦?jié)點(diǎn)一定是最后被打包進(jìn)s2的所以它必然是s2的棧底最后一個(gè)彈出。5.3 棧滿了怎么辦如果設(shè)定的MAX_SIZE太小而樹的節(jié)點(diǎn)數(shù)量超過了這個(gè)限制push的時(shí)候就會(huì)輸出“棧已滿無法入?！?。這種情況下有兩種解決辦法。一是把MAX_SIZE調(diào)大比如從1000改成100000簡單粗暴。二是改成動(dòng)態(tài)擴(kuò)容的?；蛘咧苯佑面?zhǔn)綏！Ｎ覀€(gè)人在做算法題的時(shí)候傾向于直接把數(shù)組開大一點(diǎn)因?yàn)楣?jié)點(diǎn)數(shù)量一般不會(huì)超過十萬1e5的數(shù)組在現(xiàn)代編譯器上毫無壓力。5.4 樹是空樹時(shí)怎么辦空樹是一個(gè)非常容易忽略的邊界條件。如果你的代碼在root為NULL的時(shí)候直接崩了那肯定是忘了在最開頭加判空邏輯。中序代碼里root為NULL時(shí)p初始就為NULL同時(shí)棧為空外層while條件不成立直接結(jié)束不會(huì)崩。但兩個(gè)棧的方法中一開始就把root壓入s1所以必須要提前判空。if (root NULL) { return; }這段代碼必須有。5.5 野指針問題C語言的經(jīng)典難題野指針。在非遞歸遍歷中野指針最容易出現(xiàn)在創(chuàng)建節(jié)點(diǎn)和釋放節(jié)點(diǎn)的時(shí)候。創(chuàng)建節(jié)點(diǎn)時(shí)malloc之后一定要檢查返回的指針是否為NULL。釋放節(jié)點(diǎn)時(shí)一定要先把子節(jié)點(diǎn)處理完再釋放當(dāng)前節(jié)點(diǎn)否則會(huì)造成訪問已釋放內(nèi)存的問題。BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); if (node NULL) { printf(內(nèi)存分配失敗\n); exit(1); } node-data data; node-lchild NULL; node-rchild NULL; return node; }另外malloc出來的節(jié)點(diǎn)一定要記得初始化lchild和rchild為NULL否則在判斷孩子是否存在時(shí)會(huì)讀到隨機(jī)值導(dǎo)致程序行為詭異。5.6 二叉樹退化成鏈表時(shí)的表現(xiàn)如果二叉樹退化成了一條單鏈表比如每個(gè)節(jié)點(diǎn)都只有左孩子那非遞歸遍歷的時(shí)間復(fù)雜度仍然是O(n)空間復(fù)雜度是O(n)。但如果是遞歸實(shí)現(xiàn)這個(gè)場景就非常容易爆棧。我實(shí)測過遞歸中序遍歷一個(gè)10萬層深的單鏈樹基本上直接段錯(cuò)誤。非遞歸版本用數(shù)組棧大概在1000萬層以上才會(huì)碰到棧容量問題1000萬以內(nèi)的深度完全沒壓力。這也是為什么在一些極端數(shù)據(jù)結(jié)構(gòu)下非遞歸遍歷幾乎是唯一選擇。6. 一個(gè)通用的五步解題法學(xué)完中序和后序的非遞歸遍歷我總結(jié)了一套通用的解題思路適配前序、中序、后序三種非遞歸遍歷。這是一個(gè)方法論層面的總結(jié)希望幫你看清楚本質(zhì)。第一步先把遍歷順序用文字寫出來。前序是“根左右”中序是“左根右”后序是“左右根”。第二步想一想在這個(gè)順序里哪些節(jié)點(diǎn)需要暫時(shí)存起來等后面再處理。一般來說只要某個(gè)子樹的根節(jié)點(diǎn)不是優(yōu)先打印它就需要放到棧里等待。中序和后序里根節(jié)點(diǎn)都不會(huì)被優(yōu)先打印所以都需要壓棧。第三步?jīng)Q定棧里需要額外存儲(chǔ)什么信息。如果只存節(jié)點(diǎn)指針就夠那是中序這種簡單的場景。如果需要區(qū)分左右子樹是否處理完就需要額外存tag標(biāo)記或者用兩個(gè)棧來規(guī)避。第四步寫出“往左走到頭、沿途入?！钡墓羌艽a。中序、后序的最外層邏輯基本一致變化的只是出棧之后打印的時(shí)機(jī)和轉(zhuǎn)向右子樹的方式。第五步根據(jù)不同的順序調(diào)整打印時(shí)機(jī)。中序是彈出時(shí)打印后序是右子樹處理完后打印。這套分析法對學(xué)習(xí)其他樹的遍歷也有幫助比如線索二叉樹、N叉樹遍歷本質(zhì)上還是在問什么時(shí)候打印什么時(shí)候轉(zhuǎn)向需要什么額外的狀態(tài)信息。7. 優(yōu)化與擴(kuò)展不只是寫對還要寫得好代碼寫對的下一步是寫得好。有兩個(gè)優(yōu)化方向值得花時(shí)間琢磨。第一個(gè)優(yōu)化方向是把內(nèi)存分配降到最低。在嵌入式開發(fā)和系統(tǒng)編程里malloc和free都是有代價(jià)的頻繁調(diào)用會(huì)造成內(nèi)存碎片。如果樹是預(yù)先構(gòu)建好且大小已知的可以直接在棧區(qū)聲明一個(gè)固定大小的節(jié)點(diǎn)指針數(shù)組完全避免動(dòng)態(tài)分配。第二個(gè)優(yōu)化方向是模板化。樹節(jié)點(diǎn)的data類型不一定是int可能是char、字符串、自定義結(jié)構(gòu)體。你可以把typedef改成泛型類型用void*指向數(shù)據(jù)然后用宏定義或者函數(shù)指針來實(shí)現(xiàn)通用容器。這種做法在大型項(xiàng)目里比較常見但純C語言里會(huì)犧牲一些類型安全需要自己權(quán)衡。第三個(gè)擴(kuò)展點(diǎn)是層級(jí)遍歷。非遞歸遍歷并不局限于棧用隊(duì)列實(shí)現(xiàn)的層序遍歷也是面試常客。層序遍歷的順序是一層一層從左到右用隊(duì)列保存當(dāng)前層的節(jié)點(diǎn)然后依次處理。理解了中序和后序的棧式遍歷隊(duì)列版層序遍歷本質(zhì)上是同一個(gè)思路——用數(shù)據(jù)結(jié)構(gòu)來模擬“下一個(gè)該訪問誰”的調(diào)度邏輯。我在處理實(shí)際問題的時(shí)候還有一個(gè)習(xí)慣用一個(gè)公共的打印函數(shù)或者統(tǒng)一的遍歷接口把不同遍歷方式的結(jié)果輸出成同樣的格式。調(diào)試的時(shí)候切換遍歷方式快得多不用每個(gè)函數(shù)里都重寫一遍打印邏輯。8. 完整代碼匯總最后貼上完整代碼直接用GCC編譯就能跑。代碼里我不再分段拆解保持一個(gè)完整的可直接運(yùn)行的文件。#include stdio.h #include stdlib.h #define MAX_SIZE 1000 typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef struct { BiTNode *data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int isFull(Stack *s) { return s-top MAX_SIZE - 1; } void push(Stack *s, BiTNode *node) { if (isFull(s)) { printf(棧已滿無法入棧\n); return; } s-data[(s-top)] node; } BiTNode *pop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[(s-top)--]; } BiTNode *getTop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[s-top]; } BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); if (node NULL) { printf(內(nèi)存分配失敗\n); exit(1); } node-data data; node-lchild NULL; node-rchild NULL; return node; } BiTree createTree() { BiTNode *node1 createNode(1); BiTNode *node2 createNode(2); BiTNode *node3 createNode(3); BiTNode *node4 createNode(4); BiTNode *node5 createNode(5); BiTNode *node6 createNode(6); node1-lchild node2; node1-rchild node3; node2-lchild node4; node2-rchild node5; node3-rchild node6; return node1; } void inOrder(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { while (p ! NULL) { push(s, p); p p-lchild; } if (!isEmpty(s)) { p pop(s); printf(%d , p-data); p p-rchild; } } printf(\n); } void postOrder(BiTree root) { if (root NULL) { return; } Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTNode *p pop(s1); push(s2, p); if (p-lchild ! NULL) { push(s1, p-lchild); } if (p-rchild ! NULL) { push(s1, p-rchild); } } while (!isEmpty(s2)) { BiTNode *p pop(s2); printf(%d , p-data); } printf(\n); } int main() { BiTree root createTree(); printf(中序遍歷結(jié)果: ); inOrder(root); printf(后序遍歷結(jié)果: ); postOrder(root); return 0; }這個(gè)版本的代碼可以編譯后直接運(yùn)行。如果你在操作系統(tǒng)里跑注意把控制臺(tái)編碼調(diào)成UTF-8避免中文字符串亂碼。9. 從遍歷到更深層的理解掌握了中序和后序的非遞歸遍歷你其實(shí)已經(jīng)掌握了樹這種數(shù)據(jù)結(jié)構(gòu)里最核心的一類操作。樹的遍歷并不是孤立的它和遞歸、棧、隊(duì)列、狀態(tài)機(jī)這些知識(shí)點(diǎn)緊密相關(guān)。比如非遞歸遍歷里“標(biāo)記狀態(tài)”的思想后續(xù)在學(xué)習(xí)圖的深度優(yōu)先和廣度優(yōu)先搜索時(shí)還會(huì)再次遇到。DFS的棧實(shí)現(xiàn)、BFS的隊(duì)列實(shí)現(xiàn)本質(zhì)上是同一套邏輯在不同的數(shù)據(jù)結(jié)構(gòu)上的應(yīng)用。如果你準(zhǔn)備繼續(xù)深挖建議在紙上多畫幾棵樹手動(dòng)模擬五次以上的遍歷過程。很多人學(xué)不透遍歷的原因不是代碼難而是腦子里對“當(dāng)前代碼執(zhí)行到哪一步、棧里存了哪些節(jié)點(diǎn)”沒有一個(gè)直觀的畫面。把每一個(gè)入棧、出棧、轉(zhuǎn)向的動(dòng)作在紙上畫出來一遍不夠畫三遍三遍不夠畫五遍畫到能閉著眼睛說出每一步為止。這個(gè)過程很像學(xué)騎自行車?yán)碚撜f得再多不如真的蹬兩圈。我個(gè)人的體會(huì)是非遞歸遍歷不是一個(gè)可以靠死記硬背通過的題目它需要你在紙面上把節(jié)點(diǎn)狀態(tài)的變化過程徹底過一遍。等你想通了“棧頂節(jié)點(diǎn)的tag說明什么”“什么時(shí)候該轉(zhuǎn)向右子樹”這兩個(gè)問題后序遍歷就不再是攔路虎。再順手對比一下前序、中序、后序三種遍歷在棧結(jié)構(gòu)上的差別你會(huì)發(fā)現(xiàn)它們都是在回答同一個(gè)問題下一步該訪問誰。