1. 從“遍歷”的痛點(diǎn)說(shuō)起為什么需要線索二叉樹(shù)如果你寫過(guò)二叉樹(shù)的遍歷代碼無(wú)論是遞歸還是非遞歸一定對(duì)那種“一步三回頭”的感覺(jué)不陌生。我們以最經(jīng)典的中序遍歷為例當(dāng)你訪問(wèn)完一個(gè)節(jié)點(diǎn)的左子樹(shù)返回到該節(jié)點(diǎn)本身后下一步需要去訪問(wèn)它的右子樹(shù)。這個(gè)“返回”的動(dòng)作在遞歸實(shí)現(xiàn)里由函數(shù)調(diào)用棧隱式完成而在非遞歸實(shí)現(xiàn)里則需要我們顯式地維護(hù)一個(gè)棧來(lái)記錄“我從哪里來(lái)”。問(wèn)題就出在這里。對(duì)于一個(gè)有n個(gè)節(jié)點(diǎn)的二叉樹(shù)無(wú)論采用哪種遍歷方式我們都需要花費(fèi)額外的空間?？臻g來(lái)存儲(chǔ)路徑信息空間復(fù)雜度是O(h)h是樹(shù)的高度。在最壞情況下比如一棵單支樹(shù)所有節(jié)點(diǎn)都只有左孩子或只有右孩子h就等于n空間復(fù)雜度退化為O(n)。這還不是最關(guān)鍵的更讓人頭疼的是遍歷過(guò)程中的“空指針”浪費(fèi)。仔細(xì)看一棵二叉樹(shù)每個(gè)節(jié)點(diǎn)通常有兩個(gè)指針域lchild和rchild分別指向左孩子和右孩子。對(duì)于一個(gè)有n個(gè)節(jié)點(diǎn)的二叉樹(shù)總共有2n個(gè)指針域。但實(shí)際上除了根節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)都需要一個(gè)指針來(lái)指向它所以真正被使用的指針只有n-1個(gè)。這意味著有將近n1個(gè)指針域是空的2n - (n-1) n1。這些空指針就像閑置的土地白白占著位置卻沒(méi)有產(chǎn)出。線索二叉樹(shù)Threaded Binary Tree的核心思想就是把這些空指針利用起來(lái)。具體怎么用呢我們把這些空指針重新定義如果某個(gè)節(jié)點(diǎn)的左孩子指針為空就讓它指向該節(jié)點(diǎn)在某種遍歷序列如中序、先序、后序中的前驅(qū)節(jié)點(diǎn)如果右孩子指針為空就讓它指向該節(jié)點(diǎn)在遍歷序列中的后繼節(jié)點(diǎn)。這些被重新利用、指向遍歷序列前驅(qū)或后繼的指針就叫做“線索”Thread。加了線索的二叉樹(shù)就像給一棵普通的樹(shù)裝上了“導(dǎo)航”。當(dāng)你站在任何一個(gè)節(jié)點(diǎn)上你不僅能知道它的孩子在哪還能立刻知道它在這個(gè)遍歷順序下的“上一個(gè)”和“下一個(gè)”是誰(shuí)。這樣一來(lái)遍歷整個(gè)樹(shù)就不再需要棧了你可以像遍歷鏈表一樣從一個(gè)節(jié)點(diǎn)出發(fā)順著后繼線索一路走到底時(shí)間復(fù)雜度O(n)而空間復(fù)雜度是常數(shù)O(1)。這對(duì)于需要頻繁遍歷的大型樹(shù)結(jié)構(gòu)或者內(nèi)存極其受限的嵌入式環(huán)境來(lái)說(shuō)是巨大的效率提升。2. 線索二叉樹(shù)的“骨架”核心設(shè)計(jì)與類型解析理解了“為什么”我們?cè)賮?lái)拆解“是什么”。線索化不是隨意進(jìn)行的它必須基于一種確定的遍歷次序。因此線索二叉樹(shù)主要分為三種中序線索二叉樹(shù)、先序線索二叉樹(shù)和后序線索二叉樹(shù)。其中中序線索化最為常見(jiàn)和經(jīng)典因?yàn)樗芊浅Ｖ庇^地反映出二叉搜索樹(shù)BST節(jié)點(diǎn)值的有序性。我們接下來(lái)的討論也主要以中序線索二叉樹(shù)為例。要實(shí)現(xiàn)線索化首先得解決一個(gè)根本問(wèn)題如何區(qū)分一個(gè)指針域里存放的到底是真正的孩子指針還是線索指針比如節(jié)點(diǎn)A的左指針指向了B我怎么能知道B是A的左孩子還是A的中序前驅(qū)呢解決方案是為每個(gè)節(jié)點(diǎn)增加兩個(gè)標(biāo)志位。通常的節(jié)點(diǎn)結(jié)構(gòu)定義如下以C語(yǔ)言為例typedef struct ThreadNode { ElemType data; // 數(shù)據(jù)域 struct ThreadNode *lchild, *rchild; // 左、右孩子指針 int ltag, rtag; // 左、右線索標(biāo)志 } ThreadNode, *ThreadTree;標(biāo)志位的含義是ltag 0表示lchild指向的是該節(jié)點(diǎn)的左孩子。ltag 1表示lchild指向的是該節(jié)點(diǎn)的中序前驅(qū)線索。rtag 0表示rchild指向的是該節(jié)點(diǎn)的右孩子。rtag 1表示rchild指向的是該節(jié)點(diǎn)的中序后繼線索。有了這個(gè)結(jié)構(gòu)一棵樹(shù)在內(nèi)存中的形態(tài)就清晰了。我們來(lái)看一個(gè)簡(jiǎn)單的例子。假設(shè)有一棵二叉樹(shù)它的中序遍歷序列是D, B, E, A, F, C, G。A / \ B C / \ / \ D E F G將這棵樹(shù)中序線索化后它的邏輯結(jié)構(gòu)就變成了一個(gè)雙向鏈表為了簡(jiǎn)化下圖只畫出了后繼線索實(shí)際上前驅(qū)線索也存在D - B - E - A - F - C - G原本D的右孩子為空現(xiàn)在rtag1rchild指向了BE的右孩子為空現(xiàn)在指向AF的右孩子為空現(xiàn)在指向CD的左孩子和G的右孩子依然為空但它們的lchild和rchild分別指向了它們的前驅(qū)和后繼在鏈表頭尾可能指向一個(gè)特定的頭節(jié)點(diǎn)或?yàn)镹ULL。注意在實(shí)現(xiàn)時(shí)為了方便操作我們常常會(huì)引入一個(gè)頭節(jié)點(diǎn)。這個(gè)頭節(jié)點(diǎn)的左指針(lchild)指向樹(shù)的根節(jié)點(diǎn)右指針(rchild)指向中序遍歷的最后一個(gè)節(jié)點(diǎn)。同時(shí)讓中序遍歷第一個(gè)節(jié)點(diǎn)的左線索和最后一個(gè)節(jié)點(diǎn)的右線索都指向這個(gè)頭節(jié)點(diǎn)。這樣整個(gè)線索二叉樹(shù)就形成了一個(gè)環(huán)狀的雙向鏈表可以從任意方向遍歷代碼處理起來(lái)更統(tǒng)一、更優(yōu)雅。3. 核心操作實(shí)戰(zhàn)線索化與遍歷的代碼實(shí)現(xiàn)理論講透了接下來(lái)就是硬核的代碼實(shí)現(xiàn)環(huán)節(jié)。這是理解線索二叉樹(shù)的關(guān)鍵我會(huì)把每一步的意圖和邊界條件都講清楚。3.1 中序線索化的遞歸實(shí)現(xiàn)線索化的本質(zhì)是在遍歷的過(guò)程中“順便”把空指針給填上。遞歸實(shí)現(xiàn)是最直觀的。我們需要一個(gè)全局變量pre用來(lái)始終指向剛剛訪問(wèn)過(guò)的前一個(gè)節(jié)點(diǎn)。ThreadNode *pre NULL; // 全局變量指向當(dāng)前訪問(wèn)節(jié)點(diǎn)的前驅(qū) // 中序遍歷線索化二叉樹(shù) void InThread(ThreadTree p) { if (p NULL) return; // 1. 遞歸線索化左子樹(shù) InThread(p-lchild); // 2. 處理當(dāng)前節(jié)點(diǎn)建立前驅(qū)線索 if (p-lchild NULL) { // 左孩子為空建立前驅(qū)線索 p-lchild pre; // 左指針指向前驅(qū) p-ltag 1; // 標(biāo)記為線索 } else { p-ltag 0; // 左指針是孩子標(biāo)記為0 } // 3. 處理前驅(qū)節(jié)點(diǎn)建立后繼線索 if (pre ! NULL pre-rchild NULL) { pre-rchild p; // 前驅(qū)的右指針指向當(dāng)前節(jié)點(diǎn)后繼 pre-rtag 1; // 標(biāo)記為線索 } else if (pre ! NULL) { pre-rtag 0; // 前驅(qū)的右指針是孩子標(biāo)記為0 } // 4. 更新前驅(qū)節(jié)點(diǎn) pre p; // 5. 遞歸線索化右子樹(shù) InThread(p-rchild); } // 創(chuàng)建頭節(jié)點(diǎn)并完成中序線索化的主函數(shù) void CreateInThread(ThreadTree T) { ThreadNode *head (ThreadNode*)malloc(sizeof(ThreadNode)); // 創(chuàng)建頭節(jié)點(diǎn) head-ltag 0; head-rtag 1; // 頭節(jié)點(diǎn)右標(biāo)志初始為線索 head-rchild head; // 右指針回指自身初始化 if (T NULL) { // 空樹(shù) head-lchild head; } else { head-lchild T; // 頭節(jié)點(diǎn)的左孩子指向根 pre head; // 初始化前驅(qū)為頭節(jié)點(diǎn) InThread(T); // 線索化原樹(shù) // 線索化結(jié)束后處理最后一個(gè)節(jié)點(diǎn) pre-rchild head; // 最后一個(gè)節(jié)點(diǎn)的后繼指向頭節(jié)點(diǎn) pre-rtag 1; head-rchild pre; // 頭節(jié)點(diǎn)的前驅(qū)指向最后一個(gè)節(jié)點(diǎn)通過(guò)右指針 } }代碼邏輯拆解InThread函數(shù)就是一個(gè)標(biāo)準(zhǔn)的中序遍歷遞歸框架。訪問(wèn)節(jié)點(diǎn)的操作被拆成了兩部分處理當(dāng)前節(jié)點(diǎn)p的前驅(qū)如果p的左孩子為空就讓它的左指針指向前驅(qū)pre。處理前驅(qū)節(jié)點(diǎn)pre的后繼如果pre不為空且它的右孩子為空就讓pre的右指針指向當(dāng)前節(jié)點(diǎn)p。這是理解的關(guān)鍵當(dāng)前節(jié)點(diǎn)p的前驅(qū)線索是在訪問(wèn)p時(shí)設(shè)置的而前驅(qū)節(jié)點(diǎn)pre的后繼線索是在訪問(wèn)到p時(shí)回頭去為pre設(shè)置的。CreateInThread函數(shù)負(fù)責(zé)初始化頭節(jié)點(diǎn)并處理頭尾相接的環(huán)形結(jié)構(gòu)。注意在開(kāi)始線索化前將pre初始化為頭節(jié)點(diǎn)這樣中序第一個(gè)節(jié)點(diǎn)的左線索就會(huì)指向頭節(jié)點(diǎn)。線索化完成后最后一個(gè)節(jié)點(diǎn)的右線索指向頭節(jié)點(diǎn)頭節(jié)點(diǎn)的右線索指向最后一個(gè)節(jié)點(diǎn)形成閉環(huán)。3.2 基于線索的非遞歸中序遍歷樹(shù)被線索化后遍歷就變得異常簡(jiǎn)單高效。我們不再需要棧只需要找到中序序列的第一個(gè)節(jié)點(diǎn)然后不斷尋找后繼即可。// 求中序線索二叉樹(shù)中中序序列下的第一個(gè)節(jié)點(diǎn) ThreadNode* FirstNode(ThreadNode* p) { while (p-ltag 0) { // 沿著最左下的路徑走 p p-lchild; } return p; } // 求中序線索二叉樹(shù)中節(jié)點(diǎn)p在中序序列下的后繼節(jié)點(diǎn) ThreadNode* NextNode(ThreadNode* p) { if (p-rtag 1) { // 右標(biāo)志為1直接通過(guò)右線索得到后繼 return p-rchild; } else { // 右標(biāo)志為0說(shuō)明有右孩子后繼是右子樹(shù)的最左下節(jié)點(diǎn) return FirstNode(p-rchild); } } // 非遞歸的中序遍歷利用線索 void InOrderByThread(ThreadTree head) { // 參數(shù)是頭節(jié)點(diǎn) for (ThreadNode* p FirstNode(head-lchild); p ! head; p NextNode(p)) { visit(p); // 訪問(wèn)節(jié)點(diǎn)例如打印數(shù)據(jù) } }遍歷邏輯的精妙之處FirstNode函數(shù)中序序列的第一個(gè)節(jié)點(diǎn)一定是整棵樹(shù)“最左下角”的那個(gè)節(jié)點(diǎn)。所以只要一直沿著左孩子(ltag0)走到底就行了。NextNode函數(shù)這是核心。求節(jié)點(diǎn)p的后繼分兩種情況如果p-rtag 1太好了右指針就是線索直接指向后繼return p-rchild。如果p-rtag 0說(shuō)明p有右孩子。根據(jù)中序遍歷規(guī)則左-根-右p的后繼一定在它的右子樹(shù)中并且是右子樹(shù)里中序第一個(gè)被訪問(wèn)的節(jié)點(diǎn)也就是右子樹(shù)的“最左下角”節(jié)點(diǎn)。所以調(diào)用FirstNode(p-rchild)。整個(gè)InOrderByThread遍歷就是一個(gè)簡(jiǎn)單的for循環(huán)從第一個(gè)節(jié)點(diǎn)開(kāi)始不斷獲取后繼直到回到頭節(jié)點(diǎn)為止。空間復(fù)雜度是O(1)。3.3 先序與后序線索化的特殊考量理解了中序先序和后續(xù)線索化的遞歸框架是類似的只是處理節(jié)點(diǎn)的時(shí)機(jī)不同先序是在遞歸左右子樹(shù)之前后序是在遞歸左右子樹(shù)之后。但它們各自有一個(gè)需要特別注意的“坑”。先序線索化的“死循環(huán)”陷阱 在先序遍歷中訪問(wèn)順序是“根-左-右”。假設(shè)我們對(duì)節(jié)點(diǎn)p進(jìn)行線索化如果p的左孩子為空我們將其左線索指向前驅(qū)pre。這沒(méi)問(wèn)題。但接下來(lái)我們要遞歸線索化p的左子樹(shù)。如果p的左孩子本來(lái)就是空的已經(jīng)被線索化了你再調(diào)用PreThread(p-lchild)傳入的就不是NULL而是p的前驅(qū)節(jié)點(diǎn)這會(huì)導(dǎo)致程序錯(cuò)誤地進(jìn)入前驅(qū)節(jié)點(diǎn)并試圖線索化它可能引發(fā)無(wú)限遞歸或邏輯混亂。解決方法在遞歸調(diào)用線索化左子樹(shù)之前必須檢查p-ltag是否為0是真正的孩子。只有是真孩子才進(jìn)行遞歸。void PreThread(ThreadTree p) { if (p NULL) return; // 處理當(dāng)前節(jié)點(diǎn)與前驅(qū)的關(guān)系... // ... if (p-ltag 0) { // 關(guān)鍵判斷只有左指針是真孩子才遞歸左子樹(shù) PreThread(p-lchild); } if (p-rtag 0) { // 只有右指針是真孩子才遞歸右子樹(shù) PreThread(p-rchild); } }后序線索化求后繼的復(fù)雜性 后序遍歷順序是“左-右-根”。對(duì)于一個(gè)節(jié)點(diǎn)p求它的后繼比中序要復(fù)雜。如果p-rtag 1簡(jiǎn)單右線索就是后繼。如果p-rtag 0說(shuō)明p有右孩子。但p的后繼不一定是右子樹(shù)的第一個(gè)后序節(jié)點(diǎn)。因?yàn)閜是根它的后繼應(yīng)該是如果p是其父節(jié)點(diǎn)的右孩子或者是其父節(jié)點(diǎn)的左孩子但父節(jié)點(diǎn)沒(méi)有右孩子那么p的后繼就是其父節(jié)點(diǎn)。如果p是其父節(jié)點(diǎn)的左孩子且父節(jié)點(diǎn)有右孩子那么p的后繼是父節(jié)點(diǎn)右子樹(shù)的后序第一個(gè)節(jié)點(diǎn)。 這就要求節(jié)點(diǎn)必須能訪問(wèn)到其父節(jié)點(diǎn)。在標(biāo)準(zhǔn)的二叉鏈表結(jié)構(gòu)中我們沒(méi)有父指針?biāo)詢H憑線索無(wú)法完成后序后繼的查找。這是后序線索二叉樹(shù)的一個(gè)局限。如果需要必須在節(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)parent指針。4. 實(shí)戰(zhàn)避坑與性能權(quán)衡什么時(shí)候該用線索二叉樹(shù)紙上得來(lái)終覺(jué)淺絕知此事要躬行。在實(shí)際項(xiàng)目中應(yīng)用線索二叉樹(shù)有幾個(gè)必須清楚的要點(diǎn)和常見(jiàn)的“坑”。4.1 插入與刪除操作的“雷區(qū)”線索二叉樹(shù)最大的優(yōu)勢(shì)是遍歷快但它最大的劣勢(shì)也在于此動(dòng)態(tài)修改插入、刪除節(jié)點(diǎn)極其復(fù)雜。因?yàn)椴迦牖騽h除一個(gè)節(jié)點(diǎn)會(huì)破壞原有的遍歷序列所有相關(guān)的線索都需要重新調(diào)整。這個(gè)調(diào)整的復(fù)雜度幾乎等同于重新線索化局部子樹(shù)。例如要在中序線索二叉樹(shù)中將節(jié)點(diǎn)S插入為節(jié)點(diǎn)P的右孩子。我們需要考慮多種情況如果P的右孩子原本為空那么插入后S的左線索要指向PP的右線索要指向S原來(lái)的后繼如果有的話S的右線索要指向P原來(lái)的后繼……邏輯交織非常容易出錯(cuò)。如果P原本有右孩子假設(shè)為PR情況就更復(fù)雜了需要處理P、PR、S三者的父子關(guān)系和線索關(guān)系。因此一個(gè)重要的實(shí)踐經(jīng)驗(yàn)是線索二叉樹(shù)最適合用于“一次構(gòu)建多次遍歷”的場(chǎng)景。也就是樹(shù)的結(jié)構(gòu)在初始化后基本固定或者很少發(fā)生變更但需要被頻繁地以某種順序遍歷。比如編譯器中表示程序語(yǔ)法結(jié)構(gòu)的語(yǔ)法樹(shù)AST在解析階段構(gòu)建完成后會(huì)在語(yǔ)義分析、優(yōu)化、代碼生成等階段被反復(fù)遍歷這種場(chǎng)景就適合線索化。4.2 空間與時(shí)間的權(quán)衡線索二叉樹(shù)用標(biāo)志位ltag,rtag換取了遍歷時(shí)O(1)的空間復(fù)雜度。這是一個(gè)典型的“空間換時(shí)間”或更準(zhǔn)確說(shuō)是“少量空間信息換大量遍歷時(shí)間”的策略?？臻g開(kāi)銷每個(gè)節(jié)點(diǎn)多了兩個(gè)整型標(biāo)志位。在32位系統(tǒng)上這通常是8字節(jié)。對(duì)于節(jié)點(diǎn)本身數(shù)據(jù)很小的樹(shù)比如只存一個(gè)整型鍵值這個(gè)開(kāi)銷比例是顯著的4字節(jié)數(shù)據(jù)8字節(jié)指針8字節(jié)標(biāo)志位。但對(duì)于節(jié)點(diǎn)數(shù)據(jù)很大的情況比如一個(gè)復(fù)雜的對(duì)象這個(gè)開(kāi)銷比例就可以接受。時(shí)間收益遍歷的常數(shù)因子極小沒(méi)有函數(shù)調(diào)用棧或輔助棧的開(kāi)銷對(duì)CPU緩存也更友好。在需要極高性能遍歷的實(shí)時(shí)系統(tǒng)或底層庫(kù)中這點(diǎn)優(yōu)勢(shì)可能很關(guān)鍵。4.3 常見(jiàn)問(wèn)題排查實(shí)錄在實(shí)際編碼和調(diào)試中以下幾個(gè)問(wèn)題最為常見(jiàn)線索化后遍歷陷入死循環(huán)或訪問(wèn)非法內(nèi)存原因幾乎都是因?yàn)闃?biāo)志位ltag/rtag設(shè)置錯(cuò)誤。在遞歸線索化函數(shù)中對(duì)于非空的孩子指針忘記將其標(biāo)志位設(shè)為0孩子。這會(huì)導(dǎo)致在后續(xù)的NextNode或遍歷函數(shù)中誤將孩子指針當(dāng)作線索指針去解引用從而跳轉(zhuǎn)到錯(cuò)誤的地址。排查編寫一個(gè)簡(jiǎn)單的檢查函數(shù)遍歷每個(gè)節(jié)點(diǎn)驗(yàn)證如果ltag0則lchild不應(yīng)為NULL除非是空樹(shù)如果rtag1則rchild指向的節(jié)點(diǎn)應(yīng)該是合理的。重點(diǎn)檢查葉子節(jié)點(diǎn)和只有一個(gè)孩子的節(jié)點(diǎn)。帶頭節(jié)點(diǎn)的線索二叉樹(shù)遍歷時(shí)漏掉第一個(gè)或最后一個(gè)節(jié)點(diǎn)原因頭節(jié)點(diǎn)與首尾節(jié)點(diǎn)的連接沒(méi)有正確閉環(huán)。在CreateInThread函數(shù)中必須確保中序第一個(gè)節(jié)點(diǎn)的左線索指向頭節(jié)點(diǎn)中序最后一個(gè)節(jié)點(diǎn)的右線索指向頭節(jié)點(diǎn)頭節(jié)點(diǎn)的右線索指向最后一個(gè)節(jié)點(diǎn)。排查手動(dòng)模擬一個(gè)小型二叉樹(shù)3-5個(gè)節(jié)點(diǎn)在紙上畫出線索化后的指針和標(biāo)志位特別是頭節(jié)點(diǎn)和首尾節(jié)點(diǎn)的連接關(guān)系。然后單步調(diào)試代碼對(duì)比實(shí)際內(nèi)存狀態(tài)與預(yù)期是否一致。先序線索化遞歸時(shí)發(fā)生棧溢出原因這就是前面提到的“死循環(huán)陷阱”。沒(méi)有在遞歸調(diào)用前判斷l(xiāng)tag和rtag導(dǎo)致通過(guò)線索指針錯(cuò)誤地進(jìn)行了遞歸。解決嚴(yán)格遵循模板在PreThread中只有if (p-ltag 0)時(shí)才調(diào)用PreThread(p-lchild)右子樹(shù)同理。多線程環(huán)境下的風(fēng)險(xiǎn)注意線索二叉樹(shù)不是線程安全的數(shù)據(jù)結(jié)構(gòu)。如果一個(gè)線程正在遍歷順著線索指針移動(dòng)而另一個(gè)線程同時(shí)修改了樹(shù)的結(jié)構(gòu)即使只是修改標(biāo)志位極有可能導(dǎo)致前一個(gè)線程訪問(wèn)到無(wú)效內(nèi)存或陷入邏輯循環(huán)。在并發(fā)場(chǎng)景下必須在外層加鎖保護(hù)。線索二叉樹(shù)是一種非常精巧的數(shù)據(jù)結(jié)構(gòu)優(yōu)化技巧它完美詮釋了計(jì)算機(jī)科學(xué)中“沒(méi)有銀彈”的思想——用特定的空間和信息冗余來(lái)?yè)Q取特定操作遍歷的極致性能。它不適合需要頻繁增刪的場(chǎng)景但在那些遍歷密集、結(jié)構(gòu)穩(wěn)定的領(lǐng)域如編譯器中間表示、靜態(tài)數(shù)據(jù)庫(kù)索引、只讀文件系統(tǒng)目錄樹(shù)等它依然有其獨(dú)特的價(jià)值。理解它不僅能讓你在《數(shù)據(jù)結(jié)構(gòu)》考試中游刃有余更能讓你在面臨真正的性能優(yōu)化問(wèn)題時(shí)多一種深刻而優(yōu)雅的解決方案。下次當(dāng)你面對(duì)一棵需要被反復(fù)審視的“樹(shù)”時(shí)不妨想一想它需要被“線索”化嗎