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