遞歸和非遞歸遍歷這個話題我前后給不同水平的讀者講過很多遍。很多人在初學二叉樹時感覺遞歸版本三五行就搞定非遞歸版本卻要換個棧繞來繞去總有一種“能用遞歸就懶得寫非遞歸”的心態(tài)。實際上遞歸版本隱藏了函數(shù)調(diào)用棧的進出過程而真正理解二叉樹的訪問順序恰恰需要你親手把那個“隱藏的?！庇么a表達出來。這篇文章我就用C語言把遞歸和非遞歸的三種深度優(yōu)先遍歷全部寫一遍再加上層序遍歷順便把創(chuàng)建二叉樹、棧和隊列的輔助實現(xiàn)都補齊讓你能直接編譯運行邊跑邊看結(jié)果。這篇文章適合正在復習數(shù)據(jù)結(jié)構(gòu)、準備筆試面試的初學者也適合想快速重拾二叉樹遍歷細節(jié)的開發(fā)者。我會從“為什么要區(qū)分遞歸和非遞歸”講起給出完整代碼和運行結(jié)果最后分享一些我在調(diào)試這類代碼時踩過的坑?？赐曛竽憧梢哉罩a一步步跟也可以把它當成一份可復用地的手冊下次遇到樹的題目直接查。1. 二叉樹基礎(chǔ)與遞歸遍歷1.1 鏈式存儲與創(chuàng)建方式C語言里寫二叉樹最通用的結(jié)構(gòu)體定義長這樣typedef struct BiTNode { int data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode, *BiTree;每個節(jié)點只存三種信息當前節(jié)點自己的數(shù)據(jù)、左孩子指針、右孩子指針。葉子節(jié)點的左右孩子指針都指向NULL這是遍歷過程中判斷“能不能繼續(xù)往下走”的關(guān)鍵條件。有了結(jié)構(gòu)體之后還得解決“怎么從輸入構(gòu)建一棵樹”。我習慣用先序序列配合空標記來創(chuàng)建輸入中遇到特殊字符#就表示這個子樹位置為空。比如序列AB#D##C##代表的是一棵特定形狀的樹創(chuàng)建函數(shù)的邏輯是典型的遞歸讀到一個非空字符就創(chuàng)建當前節(jié)點然后遞歸創(chuàng)建左子樹再遞歸創(chuàng)建右子樹。BiTree createTree(char **str) { if (**str # || **str \0) { (*str); return NULL; } BiTree node (BiTree)malloc(sizeof(BiTNode)); node-data **str; (*str); node-lchild createTree(str); node-rchild createTree(str); return node; }我建議初學者自己動手畫一畫這棵樹然后對照序列手動模擬一遍遞歸創(chuàng)建過程。只要這一步理解了后面理解遍歷遞歸同樣會順暢很多。1.2 遞歸遍歷為什么代碼能這么短遞歸遍歷的核心思想非常簡單一棵二叉樹本身由“根節(jié)點、左子樹、右子樹”組成那么遍歷一棵樹的問題就能拆成“處理根節(jié)點 遍歷左子樹 遍歷右子樹”三個子問題。因為左右子樹仍然是二叉樹所以同一個函數(shù)可以反復調(diào)用自己直到遇到NULL節(jié)點才返回。先序、中序、后序的唯一區(qū)別在于“訪問根節(jié)點”這個動作放在什么位置。訪問動作可以是打印、計數(shù)、累加也可以是其他業(yè)務(wù)邏輯。下面給出最常見的打印版本void preorderRecursive(BiTree root) { if (root NULL) return; printf(%c , root-data); // 先訪問根 preorderRecursive(root-lchild); preorderRecursive(root-rchild); } void inorderRecursive(BiTree root) { if (root NULL) return; inorderRecursive(root-lchild); printf(%c , root-data); // 中序左、根、右 inorderRecursive(root-rchild); } void postorderRecursive(BiTree root) { if (root NULL) return; postorderRecursive(root-lchild); postorderRecursive(root-rchild); printf(%c , root-data); // 后序左、右、根 }三份代碼唯一的不同就是printf(%c , root-data)這行代碼的位置。很多人背順序靠口訣“先根左右、中左根右、后左右根”但我一直覺得單純背口訣不如理解調(diào)用順序。你只要記住一句話遞歸函數(shù)在做同樣的事把當前節(jié)點當作根來處理子問題就交給下一層遞歸順序就自然寫出來了。1.3 遞歸背后的調(diào)用棧遞歸之所以能跑起來是因為編譯器和運行時系統(tǒng)維護了一個函數(shù)調(diào)用棧。每次進入preorderRecursive函數(shù)系統(tǒng)會為該次調(diào)用分配一塊棧幀里面保存了返回值地址、參數(shù)root、局部變量等信息。當函數(shù)內(nèi)部再次調(diào)用自身時新的棧幀壓在舊的上面當前一層的子調(diào)用全部返回后棧幀彈出程序回到上一層繼續(xù)執(zhí)行。我用一個很簡單的例子說明。假設(shè)樹的結(jié)構(gòu)是A / \ B C / \ D EpreorderRecursive(A)執(zhí)行printf輸出A然后調(diào)用preorderRecursive(B)。這時候A這一幀還在棧里等著B這一幀入棧。B輸出B接著調(diào)用preorderRecursive(D)。D輸出D左右子樹都是NULLD函數(shù)返回B函數(shù)繼續(xù)調(diào)用preorderRecursive(E)E輸出E后返回B整個函數(shù)執(zhí)行完畢返回A再繼續(xù)調(diào)用preorderRecursive(C)C輸出C后結(jié)束。所以最終結(jié)果是A B D E C。如果你在調(diào)試器里觀察函數(shù)調(diào)用棧就能看到這種“往下鉆、再往回退”的過程。理解了這一步非遞歸版本其實就是在用一個我們自己創(chuàng)建的棧來模擬這套行為只是棧里存的不是函數(shù)棧幀而是樹的節(jié)點指針。2. 非遞歸遍歷為什么要繞開遞歸2.1 遞歸的局限與棧模擬思路遞歸代碼好寫但不見得總是好用。每次函數(shù)調(diào)用都會消耗系統(tǒng)棧空間樹的深度過大時比如一條鏈狀的樹有十萬個節(jié)點函數(shù)調(diào)用深度會跟著到十萬層系統(tǒng)棧往往只有幾兆到幾兆字節(jié)很容易棧溢出。非遞歸版本手動管理棧能在堆上分配空間容量可控而且邏輯明明白白不會出現(xiàn)“調(diào)用棧爆炸”的問題。除了穩(wěn)定性面試和筆試也特別喜歡考非遞歸。原因很簡單遞歸版本誰都會寫但能把遞歸轉(zhuǎn)換為迭代說明你真正看懂了“訪問順序到底是怎么形成的”。很多人一遇到非遞歸就懵歸根到底是沒想清楚一個關(guān)鍵問題棧里應(yīng)該壓什么什么時機彈出彈出之后下一步做什么以深度優(yōu)先遍歷來說非遞歸遍歷需要在棧里保存“當前還沒處理完的節(jié)點”。因為在樹上往下走時我們隨時可能要回到之前路過的節(jié)點而棧的后進先出特性剛好合適后遇到的子樹先處理完先遇到的祖先節(jié)點最后處理完。這實際上和遞歸的函數(shù)調(diào)用順序完全一致。2.2 手寫棧的完整實現(xiàn)為了不依賴操作系統(tǒng)棧我要自己準備一個棧結(jié)構(gòu)。這里用數(shù)組實現(xiàn)為了簡化問題棧容量先固定為100足夠應(yīng)付演示場景。實際項目中你可以改成動態(tài)擴容版本邏輯大同小異。#define MAXSIZE 100 typedef struct { BiTree data[MAXSIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int push(Stack *s, BiTree node) { if (s-top MAXSIZE - 1) return 0; s-data[(s-top)] node; return 1; } int pop(Stack *s, BiTree *node) { if (isEmpty(s)) return 0; *node s-data[(s-top)--]; return 1; } int getTop(Stack *s, BiTree *node) { if (isEmpty(s)) return 0; *node s-data[s-top]; return 1; }top初始為-1入棧時先加一再寫入出棧時先取出再減一。這個設(shè)計可以把“棧頂指針”理解為指向當前有效元素的索引而不是下一個空位置寫起來比較直觀。我在對照遞歸過程時用得最多的操作是getTop因為很多非遞歸算法的下一步要根據(jù)棧頂節(jié)點的情況來決定而并不急著彈出。2.3 前序和中序非遞歸的核心區(qū)別先看前序非遞歸。前序是“根左右”也就是說每遇到一個節(jié)點第一件事就是訪問它然后再去處理子樹。這時候訪問完當前節(jié)點后需要先把右子樹壓棧再把左子樹壓棧。因為棧是后進先出先壓右樹下一輪才能先彈出左樹保證左子樹先被處理。void preorderIter(BiTree root) { Stack s; initStack(s); if (root ! NULL) push(s, root); while (!isEmpty(s)) { BiTree node; pop(s, node); printf(%c , node-data); if (node-rchild) push(s, node-rchild); if (node-lchild) push(s, node-lchild); } }整個過程可以這樣理解棧頂永遠放著“下一個要處理”的節(jié)點。彈出時立即打印打印完把自己的左右子樹按“右先左后”壓棧就能保持“先左邊后右邊”的遍歷順序。中序非遞歸就更有意思了。中序是“左根右”所以不能一遇到節(jié)點就打印得先把左子樹整個處理完才能訪問當前節(jié)點。實現(xiàn)思路是從根節(jié)點開始一直沿左子樹往下走沿途經(jīng)過的節(jié)點全部壓棧直到左孩子為NULL然后彈出棧頂節(jié)點這個節(jié)點一定是“左子樹已經(jīng)處理完”的節(jié)點打印它隨后把當前指針移到它的右子樹對右子樹重復同樣的過程。void inorderIter(BiTree root) { Stack s; initStack(s); BiTree cur root; while (cur ! NULL || !isEmpty(s)) { while (cur ! NULL) { push(s, cur); cur cur-lchild; } pop(s, cur); printf(%c , cur-data); cur cur-rchild; } }這里最容易出錯的地方在循環(huán)結(jié)束條件。很多初學版本只寫了while (!isEmpty(s))結(jié)果當?？盏玞ur不為NULL時循環(huán)提前退出導致漏掉節(jié)點。正確條件是cur ! NULL || !isEmpty(s)?？詹荒茏鳛槲ㄒ唤Y(jié)束標志因為剛彈出最后一個節(jié)點后它的右子樹可能還沒處理。我建議你手動拿一棵三個節(jié)點的樹完整走一遍中序過程。比如樹是B為根B有左孩子A和右孩子C中序應(yīng)該是A B C。第一步一直走到最左的A并壓棧然后彈A打印再移動到A的右子樹NULL此時棧里還有B彈B打印移動到CC入棧彈C打印。總共執(zhí)行了A B C每一步都清晰可見。2.4 后序非遞歸兩種易用方案后序“左右根”是非遞歸里最麻煩的一個因為根節(jié)點必須等左右子樹都處理完之后才能打印。如何在代碼里判斷“當前節(jié)點的左右子樹都處理完了”我在這里給兩種比較實用的方案。方案一雙棧法雙棧法的思路很巧妙。既然后序遍歷是“左右根”那我能不能先求出一個“根右左”的序列然后反轉(zhuǎn)成“左右根”前序遍歷很容易實現(xiàn)是“根左右”。只要把前序中壓棧的順序稍微改一下變成先壓左孩子再壓右孩子遍歷出來的結(jié)果就是“根右左”。把每一次訪問到的節(jié)點壓到第二個棧里最后把第二個棧全部彈出順序就是后序。void postorderIterTwoStack(BiTree root) { if (root NULL) return; Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTree node; pop(s1, node); push(s2, node); if (node-lchild) push(s1, node-lchild); if (node-rchild) push(s1, node-rchild); } while (!isEmpty(s2)) { BiTree node; pop(s2, node); printf(%c , node-data); } }你可能會疑惑為什么push(s1, node-lchild)和push(s1, node-rchild)的順序和前序正好相反因為s1彈出某個節(jié)點后會把左右子樹入棧而棧的后進先出會讓下一次優(yōu)先彈出后壓入的那一個。先壓左再壓右彈出的順序就是先右后左于是s2中收集到的順序就成了“根右左”。把s2倒序輸出就得到“左右根”。方案二單棧標記法雙棧法邏輯簡單但需要兩個棧。如果只想用一個棧最常用的辦法是在棧里給每個節(jié)點附帶一個狀態(tài)標記表示“當前節(jié)點的左子樹處理完了還是右子樹也處理完了”。typedef struct { BiTree ptr; int flag; } StackElem; void postorderIterOneStack(BiTree root) { StackElem stack[MAXSIZE]; int top -1; BiTree cur root; while (cur ! NULL || top ! -1) { while (cur ! NULL) { stack[top].ptr cur; stack[top].flag 0; cur cur-lchild; } while (top ! -1 stack[top].flag 1) { printf(%c , stack[top--].ptr-data); } if (top ! -1) { stack[top].flag 1; cur stack[top].ptr-rchild; } } }這段代碼的意思歸納為先把從當前節(jié)點出發(fā)的所有左孩子壓棧標記都為0表示左子樹還沒處理完。當左子樹到底之后檢查棧頂如果棧頂節(jié)點的flag為0說明左子樹已經(jīng)遍歷完輪到處理右子樹于是把flag改成1然后把當前指針切換到右子樹繼續(xù)重復“往左鉆”的過程。如果flag為1說明右子樹也已經(jīng)處理完這時彈出并打印節(jié)點。單棧法的優(yōu)勢是省空間但理解起來需要一點時間。我建議第一次接觸時先跑雙棧版把結(jié)果跑對了再回頭把單棧版和遞歸調(diào)用的函數(shù)棧幀對照著看會更容易接受。3. 層序遍歷與完整測試3.1 用隊列實現(xiàn)層序遍歷深度優(yōu)先遍歷是沿著一條路走到黑再回頭。層序遍歷則是按“層級”從上到下、從左到右逐個訪問比如根節(jié)點一層、它的左右孩子一層、再下一層。層序遍歷不能用棧得用隊列因為先進來的節(jié)點要先被處理符合“一層一層推進”的邏輯。隊列可以用數(shù)組模擬循環(huán)隊列也可以用鏈表。為了和之前的棧代碼保持一致我用數(shù)組加front和rear兩個指針來實現(xiàn)#define QUEUE_MAX 100 typedef struct { BiTree data[QUEUE_MAX]; int front; int rear; } Queue; void initQueue(Queue *q) { q-front 0; q-rear 0; } int isQueueEmpty(Queue *q) { return q-front q-rear; } int enQueue(Queue *q, BiTree node) { if ((q-rear 1) % QUEUE_MAX q-front) return 0; q-data[q-rear] node; q-rear (q-rear 1) % QUEUE_MAX; return 1; } int deQueue(Queue *q, BiTree *node) { if (isQueueEmpty(q)) return 0; *node q-data[q-front]; q-front (q-front 1) % QUEUE_MAX; return 1; } void levelOrder(BiTree root) { Queue q; initQueue(q); if (root ! NULL) enQueue(q, root); while (!isQueueEmpty(q)) { BiTree node; deQueue(q, node); printf(%c , node-data); if (node-lchild) enQueue(q, node-lchild); if (node-rchild) enQueue(q, node-rchild); } }隊列容量這里預留了一個空位來區(qū)分隊列滿和隊列空所以實際能存99個節(jié)點。對于演示級別的樹完全夠用。如果你想處理更大規(guī)模的數(shù)據(jù)可以把隊列改成鏈式存儲邏輯是一樣的。3.2 創(chuàng)建一棵測試樹并驗證結(jié)果光看代碼不夠直接跑一遍最直觀。為了測試所有遍歷函數(shù)我寫了一個main函數(shù)按先序序列創(chuàng)建一棵固定樹。假設(shè)樹的形狀是A / \ B C / \ \ D E F對應(yīng)的先序序列為ABD##E##C#F##。其中#表示空節(jié)點。注意看C只有右孩子F所以C后面先是一個#表示左孩子為空再是F最后兩個#表示F的左右孩子為空。int main() { char *str ABD##E##C#F##; BiTree root createTree(str); printf(先序遞歸: ); preorderRecursive(root); printf(\n); printf(中序遞歸: ); inorderRecursive(root); printf(\n); printf(后序遞歸: ); postorderRecursive(root); printf(\n); printf(先序非遞歸: ); preorderIter(root); printf(\n); printf(中序非遞歸: ); inorderIter(root); printf(\n); printf(后序非遞歸(雙棧): ); postorderIterTwoStack(root); printf(\n); printf(后序非遞歸(單棧): ); postorderIterOneStack(root); printf(\n); printf(層序遍歷: ); levelOrder(root); printf(\n); return 0; }編譯運行后的輸出應(yīng)該是先序遞歸: A B D E C F 中序遞歸: D B E A C F 后序遞歸: D E B F C A 先序非遞歸: A B D E C F 中序非遞歸: D B E A C F 后序非遞歸(雙棧): D E B F C A 后序非遞歸(單棧): D E B F C A 層序遍歷: A B C D E F我特別想提醒你注意幾個對應(yīng)關(guān)系先序遞歸和非遞歸輸出完全相同這驗證了迭代版只是把遞歸的調(diào)用棧換成了顯式棧中序同樣如此兩種后序非遞歸方法的結(jié)果也都一致說明兩個不同思路實際上描述的是同一種遍歷順序。層序遍歷按層輸出根A、第二層B C、第三層D E F順序清晰。如果你的運行結(jié)果和這個不一致多半是入棧順序?qū)懛椿蛘咻斎胄蛄欣锏?數(shù)量不對。這時候不要急著改代碼先在紙上畫出樹再手動模擬一遍往往比干瞪眼找bug快很多。4. 常見問題與避坑經(jīng)驗4.1 代碼運行常見的坑棧容量不夠前面寫的固定大小為100的棧處理幾十個節(jié)點的樹沒問題。但如果樹的節(jié)點數(shù)超過容量壓棧函數(shù)會返回0而我在演示代碼里沒有檢查返回值結(jié)果就是元素丟失遍歷結(jié)果莫名其妙。正式寫代碼時要么在push里處理擴容要么在調(diào)用處判斷返回值缺一不可?？諛涮幚砗芏啾闅v函數(shù)對空樹返回的順序很敏感。比如preorderIter在root為NULL時棧為空循環(huán)不執(zhí)行函數(shù)自然結(jié)束這沒問題。但單棧后序?qū)懛ɡ锶绻鹀ur初始為NULL且棧為空while (top ! -1 stack[top].flag 1)內(nèi)部不會彈任何節(jié)點主循環(huán)判斷條件cur ! NULL || top ! -1也很快退出輸出為空。看起來輸出空結(jié)果正確但如果你把空樹的root傳入某些沒有初始化的函數(shù)可能訪問野指針。建議在所有遍歷函數(shù)開頭先判斷root NULL直接返回空結(jié)果。中序非遞歸循環(huán)條件寫錯我剛學的時候中序?qū)懗蓋hile (!isEmpty(s))遍歷一個完整樹時經(jīng)常少打印右子樹節(jié)點。原因前面提過棧空時cur可能還指向右子樹必須把cur ! NULL納入判斷。這個錯誤非常隱蔽因為如果樹剛好是完全二叉樹可能結(jié)果碰巧是對的但只要右子樹還有更深的節(jié)點漏節(jié)點問題就暴露了。后序單棧法搞混flag含義我見過很多人在單棧法里把flag0當作“右子樹處理完”然后打印時機完全反了。要記住一個簡單約定flag0表示這個節(jié)點剛剛?cè)霔Ｗ笞訕溥€沒處理flag1表示左子樹已處理完接下來要處理右子樹等右子樹也處理完即遇到flag1且再次回到該節(jié)點時才允許打印。所以正確邏輯是初始入棧flag0出循環(huán)時遇到flag0就改成flag1并轉(zhuǎn)到右子樹遇到flag1就打印并彈出。次序反了輸出就會變成“根左右”之類的前序遍歷。4.2 怎么驗證自己真的懂了我自己的經(jīng)驗是驗證理解程度的最好辦法不是默寫代碼而是拿著一個至少四層的樹手動模擬每一步棧的變化。準備一張紙左邊寫樹右邊畫棧每執(zhí)行一步就把棧里從底到頂?shù)脑亓谐鰜?。舉個例子中序遍歷中第一次while (cur ! NULL)會一直壓左孩子壓到最底層。這時候棧里從底到頂是根、根的左孩子、左孩子的左孩子……你會看到棧底永遠是最早的祖先節(jié)點棧頂是最新到達的節(jié)點。然后彈出棧頂并打印再切到它的右子樹。這個過程模擬幾輪以后自然就理解了“左根右”是怎么通過棧實現(xiàn)的。如果用手動模擬太慢我建議你在代碼里臨時加一個打印函數(shù)在每次入棧、出棧時輸出當前棧內(nèi)容。比如在inorderIter里壓入一個節(jié)點后打印push: node-data彈出時打印pop: node-data運行結(jié)果就是完整的棧操作日志對照日志看代碼會清楚很多。4.3 再往前一步可以做什么遍歷是所有二叉樹操作的基礎(chǔ)會寫遞歸和非遞歸之后可以順手把下面幾個問題一起練了用遍歷序列重建二叉樹已知先序和中序或者已知后序和中序重建整棵樹。這個題目能反向檢驗你對遍歷順序的理解。線索化二叉樹利用葉子節(jié)點空指針存前驅(qū)和后繼信息讓中序遍歷不需要棧也能完成非遞歸遍歷的延伸應(yīng)用。表達式樹求值把中綴表達式轉(zhuǎn)成樹用后序遍歷求值那時你會再次感受到“后序遍歷為什么適合計算”。層序遍歷的變體比如按層輸出、每層換行、之字形打印等這些題都是在層序基礎(chǔ)上加點判斷條件。這些擴展看著多但萬變不離其宗。核心還是回到“棧模擬遞歸、隊列模擬層次”這兩個基本思路上。把今天這套C語言代碼理解透了其他語言版本也就是換一層語法外殼而已。最后分享一個我調(diào)試時的小習慣在寫非遞歸遍歷前先寫遞歸版本并把輸出結(jié)果打印出來然后寫迭代版本兩個輸出并排比較。只要某一條遍歷順序?qū)Σ簧暇驼f明?；蜿犃械牟僮黜樞蛴袉栴}。這個方法雖然笨但排查效率很高比反復看代碼猜錯在哪里快得多。