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