軟考軟件設(shè)計(jì)師上午的選擇題里數(shù)據(jù)結(jié)構(gòu)一直是必考模塊而二叉樹在其中占比又特別高。我備考和幫人備考時(shí)最明顯的感覺是這塊內(nèi)容不難但很碎——今天問遍歷序列明天問平衡因子后天問哈夫曼編碼。很多同學(xué)卡在及格線附近往往就是樹這一塊有兩三個(gè)考點(diǎn)沒有真正吃透。這篇文章把我認(rèn)為最核心的幾組知識(shí)點(diǎn)串起來講包括形態(tài)性質(zhì)、遍歷與還原、二叉排序樹和平衡樹、哈夫曼樹、線索二叉樹以及樹森林轉(zhuǎn)換目標(biāo)是讓你拿到一套能直接套用的做題方法考前兩三天也能快速過一遍。1. 二叉樹形態(tài)與性質(zhì)先把送分題撿起來1.1 二叉樹不是每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子這么簡單軟考上午題特別喜歡在一道題里同時(shí)考二叉樹的定義和性質(zhì)。你要先記住一個(gè)容易被忽略的點(diǎn)二叉樹不是簡單的度為2的樹它強(qiáng)調(diào)每個(gè)節(jié)點(diǎn)最多只有兩個(gè)孩子并且左右子樹有嚴(yán)格次序交換左右子樹后就是另一棵二叉樹了。這個(gè)區(qū)分在判斷題里出現(xiàn)過很多次。接著就是兩條高頻性質(zhì)幾乎是每年都會(huì)露面的那種二叉樹第 i 層最多有 2^(i-1) 個(gè)節(jié)點(diǎn)。因?yàn)槊客乱粚庸?jié)點(diǎn)數(shù)最多翻倍從1開始第 i 層就是 2^(i-1)。深度為 k 的二叉樹最多有 2^k - 1 個(gè)節(jié)點(diǎn)k≥1。這就是把每一層的最大值加起來等比數(shù)列求和的結(jié)果。很多同學(xué)不明白為什么要單獨(dú)記一條葉節(jié)點(diǎn)數(shù)等于度為2的節(jié)點(diǎn)數(shù)加1也就是 n0 n2 1。這個(gè)公式出現(xiàn)頻率極高而且它可以用很直觀的方式理解每產(chǎn)生一個(gè)度為2的節(jié)點(diǎn)就相當(dāng)于多了一條從上面分叉下來的路整棵樹的葉子就會(huì)比分叉點(diǎn)個(gè)數(shù)多1。做題時(shí)直接套公式就行不用自己去推。我隨手舉個(gè)例子一棵二叉樹有11個(gè)度為2的節(jié)點(diǎn)問它有多少個(gè)葉子。答案就是12不需要看樹長什么樣直接 n0 n2 1。這種題就是典型的送分題錯(cuò)了很可惜。1.2 完全二叉樹與滿二叉樹的節(jié)點(diǎn)計(jì)算套路滿二叉樹比較好理解每一層都是滿的。真正容易出錯(cuò)的是完全二叉樹它的定義是最后一層可以不滿但必須從左到右連續(xù)排列。軟考喜歡拿完全二叉樹的編號(hào)做文章。如果你用數(shù)組從1開始順序存儲(chǔ)一棵完全二叉樹就會(huì)得到這幾個(gè)結(jié)論編號(hào)為 i 的節(jié)點(diǎn)左孩子編號(hào)是 2i右孩子編號(hào)是 2i1它的父節(jié)點(diǎn)編號(hào)是 ?i/2?完全二叉樹含 n 個(gè)節(jié)點(diǎn)時(shí)高度是 ?log?n? 1。我記得有一年考題問的是某完全二叉樹共有700個(gè)節(jié)點(diǎn)問葉子節(jié)點(diǎn)數(shù)。這種題看著復(fù)雜其實(shí)有個(gè)快速結(jié)論完全二叉樹中度為1的節(jié)點(diǎn)最多只有1個(gè)所以 n n0 n1 n2再結(jié)合 n0 n2 1就能解出來。700個(gè)節(jié)點(diǎn)的完全二叉樹葉子數(shù)為350個(gè)度為1的節(jié)點(diǎn)為1個(gè)你可以用這個(gè)結(jié)果去倒推體驗(yàn)一下。再做一道常見的判斷題完全二叉樹一定是滿二叉樹嗎反過來呢答案是滿二叉樹一定是完全二叉樹但完全二叉樹不一定是滿二叉樹。這個(gè)邏輯搞清楚之后很多選項(xiàng)都能一眼排除。1.3 順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的適用邊界二叉樹在計(jì)算機(jī)里有兩種存儲(chǔ)方式順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。順序存儲(chǔ)就是把節(jié)點(diǎn)按層序放進(jìn)數(shù)組它最適合完全二叉樹和滿二叉樹因?yàn)榭臻g不浪費(fèi)而且父子和兄弟關(guān)系都能用下標(biāo)算出來。但如果是普通二叉樹尤其是斜樹順序存儲(chǔ)就非常浪費(fèi)。比如一棵深度為5、實(shí)際只有5個(gè)節(jié)點(diǎn)的右斜樹順序存儲(chǔ)可能要開 2^5 - 1 31 個(gè)位置中間全是空位。這種時(shí)候就應(yīng)該用鏈?zhǔn)酱鎯?chǔ)也就是二叉鏈表每個(gè)節(jié)點(diǎn)包含 data、left、right 三個(gè)部分。軟考還經(jīng)?？家粋€(gè)空鏈域數(shù)量的題n 個(gè)節(jié)點(diǎn)的二叉鏈表一共有 2n 個(gè)指針域其中只有 n-1 個(gè)指針指向孩子節(jié)點(diǎn)剩下的空鏈域就是 n1 個(gè)。這個(gè)結(jié)論簡單就是每個(gè)節(jié)點(diǎn)除了根節(jié)點(diǎn)外都有一條來自父親的邊所以非空指針一定是 n-1。復(fù)習(xí)這個(gè)模塊時(shí)我建議你心里始終繃一根弦性質(zhì)公式一定要自己手動(dòng)推一遍而不是死記。考試的時(shí)候一旦選項(xiàng)比較模糊理解公式的來龍去脈比硬背結(jié)論更穩(wěn)。2. 遍歷序列還原二叉樹把遞歸切分練成肌肉記憶2.1 前序中序的還原原理與手推流程這是軟考二叉樹里最能體現(xiàn)會(huì)與不會(huì)差距的題型。給出一棵二叉樹的前序遍歷和中序遍歷要求還原整棵樹或者進(jìn)一步求它的后序遍歷。很多同學(xué)拿到題就蒙其實(shí)規(guī)律很簡單前序遍歷的第一個(gè)節(jié)點(diǎn)就是根而這個(gè)根在中序遍歷里的位置恰好把左右子樹分開。舉個(gè)例子前序遍歷是 ABDGHCEFI中序遍歷是 GDHBAECFI。第一步前序第一個(gè) A 是根。在中序遍歷里找到 AA 左邊是 GDHB右邊是 ECFI所以左子樹有4個(gè)節(jié)點(diǎn)右子樹有4個(gè)節(jié)點(diǎn)。第二步回到前序遍歷根 A 后面緊接著的4個(gè)節(jié)點(diǎn) BDGH 屬于左子樹再往后4個(gè) CEFI 屬于右子樹。第三步對(duì)左子樹重復(fù)同樣的邏輯前序 BDGH 中第一個(gè) B 是左子樹的根中序 GDHB 中 B 在最右邊說明 B 只有左子樹而沒有右子樹。繼續(xù)分下去D 是 B 的左孩子G 和 H 分別是 D 的左右孩子。右邊也這樣推前序 CEFI 中 C 是右子樹根中序 ECFI 中 C 的左邊是 E、右邊是 FI最后 F 是 I 的父節(jié)點(diǎn)。整棵樹就還原出來了A / \ B C / / \ D E F / \ \ G H I看到?jīng)]有整個(gè)過程就是前序定根中序分左右這是一個(gè)遞歸過程。考前我強(qiáng)烈建議你拿兩三個(gè)例子親手畫一遍不要只是在腦子里想畫一次之后速度會(huì)快很多。2.2 后序中序與層序中序的推法差異后序遍歷和中序遍歷的組合同樣可以還原二叉樹但規(guī)律要反過來用后序遍歷的最后一個(gè)節(jié)點(diǎn)是根。還是用上面這棵樹后序遍歷是 GHDBEIFCA。第一步后序最后一個(gè) A 是根。中序里 A 左邊 GDHB 是左子樹右邊 ECFI 是右子樹。第二步左子樹的后序序列是 GHD B其中最后一個(gè) B 是左子樹的根中序 GDHB 里 B 在最右說明 B 沒有右子樹。再細(xì)分得到 D 為 B 的左孩子G、H 為 D 的左右孩子。第三步右子樹的后序序列是 EIFC最后一個(gè) C 是根中序 ECFI 表明 C 的左孩子是 E右子樹由 F、I 構(gòu)成而后序 EIFC 中 F 排在 I 前面且 F 是那一小段的根所以 I 是 F 的右孩子。層序中序相對(duì)少一些但也會(huì)考。層序遍歷的第一個(gè)節(jié)點(diǎn)永遠(yuǎn)是根剩下的節(jié)點(diǎn)要依靠中序來分配左右。做題思路是不斷在中序里找子樹根。因?yàn)閷有虮緛砭褪菑纳系较?、從左到右輸出的所以在給定中序后從層序靠前的節(jié)點(diǎn)開始逐個(gè)放入對(duì)應(yīng)子樹段就能還原。不過軟考里層序的題目更多是選擇題形式比如給你一棵樹層序遍歷的結(jié)果問中序或前序是什么。這時(shí)候你就需要理解層序與隊(duì)列之間的關(guān)系。2.3 還原題里容易踩的兩個(gè)坑第一個(gè)坑把前序和后序搞混。前序的第一個(gè)是根后序的最后一個(gè)才是根。這個(gè)錯(cuò)誤在考場(chǎng)上特別常見尤其是連續(xù)做兩三道序列題之后人容易機(jī)械套用。第二個(gè)坑認(rèn)為前序后序也能唯一確定一棵二叉樹。這是經(jīng)典誤區(qū)。前序 AB、后序 BA 的時(shí)候根是 A但 B 可能是 A 的左孩子也可能是 A 的右孩子沒法確定。所以只有前序和后序無法唯一還原二叉樹。軟考曾在判斷題里專門設(shè)過這個(gè)陷阱。第三個(gè)坑是還原完之后沒有校驗(yàn)。我建議你每次還原出樹之后快速用前序或中序走一遍看能不能和題目給定序列對(duì)上。這一步看起來多花十秒實(shí)際上能救回不少粗心分。3. 遞歸遍歷與非遞歸遍歷從背代碼到畫棧3.1 三種遞歸遍歷為什么容易混淆二叉樹的三種遞歸遍歷本質(zhì)區(qū)別只有訪問根的時(shí)機(jī)前序是根左右中序是左根右后序是左右根。考概念的時(shí)候大家都會(huì)但一旦給出具體二叉樹問遍歷結(jié)果就容易出錯(cuò)。我用上面那棵樹做一遍輸出你對(duì)照感受前序A B D G H C E F I中序G D H B A E C F I后序G H D B E I F C A你會(huì)發(fā)現(xiàn)中序的結(jié)果特別重要因?yàn)槎媾判驑涞闹行虮闅v一定是遞增序列這是后面二叉樹排序樹章節(jié)的基石。考試?yán)锝?jīng)常讓考生根據(jù)一棵實(shí)際BST的插入過程來判斷其中序遍歷結(jié)果其實(shí)只要記住左根右遞歸定義就一定能寫對(duì)。3.2 前序和中序非遞歸實(shí)現(xiàn)的棧模板很多資料一上來就放非遞歸代碼把初學(xué)者嚇跑。其實(shí)非遞歸無非就是自己維護(hù)一個(gè)棧模擬系統(tǒng)函數(shù)調(diào)用棧的進(jìn)出過程。考場(chǎng)上雖然不一定讓你寫完整代碼但理解它有助于你做序列輸出題。前序非遞歸的模板特別簡練根節(jié)點(diǎn)入棧 while 棧非空: 彈出 p訪問 p 若 p 有右孩子右孩子入棧 若 p 有左孩子左孩子入棧為什么先壓右孩子再壓左孩子因?yàn)闂Ｊ呛筮M(jìn)先出先壓右孩子左孩子就會(huì)先彈出這樣訪問順序才是左子樹在前、右子樹在后。中序非遞歸稍微繞一點(diǎn)核心思想是一路向左走走到不能再走就彈棧訪問然后再轉(zhuǎn)向右子樹p 根節(jié)點(diǎn) while p 不為空或棧非空: while p 不為空: 棧.push(p) p p.left p 棧.pop() 訪問 p p p.right你可以在紙上對(duì)樹模擬幾遍中序遍歷的棧變化先是連續(xù)入棧 A、B、D、GG沒有左孩子彈出G然后 p 指向 G 的右孩子為空所以繼續(xù)彈D……整個(gè)過程就是遞歸展開的樣子。3.3 后序與層序的考試出現(xiàn)形式后序非遞歸的模板比前序、中序都麻煩軟考很少直接考代碼但經(jīng)?？枷铝心膫€(gè)序列不可能是后序遍歷的結(jié)果。這種題你要抓住后序遍歷的核心特征左右根根一定是最后訪問的。作為一個(gè)反例如果一個(gè)序列的結(jié)尾是一個(gè)明明在中序里靠中間的節(jié)點(diǎn)那就肯定不是后序。后序還有一種簡便記憶法把前序遍歷的根左右改成根右左然后整體倒過來就得到后序遍歷。這個(gè)技巧在一些選擇題里非常好用尤其是不用真正寫出代碼的時(shí)候。層序遍歷則必須用隊(duì)列根節(jié)點(diǎn)入隊(duì)出隊(duì)時(shí)訪問然后把左右孩子依次入隊(duì)。軟考里有個(gè)很經(jīng)典的延伸考點(diǎn)是判斷一棵二叉樹是否為完全二叉樹用層序遍歷的思路一旦遇到缺失孩子的情況后面就不允許再出現(xiàn)帶孩子的節(jié)點(diǎn)否則就不是完全二叉樹。這個(gè)判斷方法比數(shù)節(jié)點(diǎn)個(gè)數(shù)更快值得記下來。4. 二叉排序樹與平衡二叉樹構(gòu)建、刪除、旋轉(zhuǎn)的核心邏輯4.1 BST構(gòu)建、查找效率的同一根主線二叉排序樹也叫二叉查找樹它的規(guī)則很直觀左子樹所有節(jié)點(diǎn)都小于根節(jié)點(diǎn)右子樹所有節(jié)點(diǎn)都大于根節(jié)點(diǎn)。由此推出一個(gè)最常用的結(jié)論——中序遍歷BST得到的是遞增序列。這個(gè)結(jié)論在軟考里幾乎年年出現(xiàn)要么直接考輸出要么隱藏在查找邏輯里。構(gòu)樹的過程就是不斷比較從根開始比當(dāng)前節(jié)點(diǎn)小就走左大就走右直到找到空位置插入。比如依次插入 50、30、80、20、40、90、35、45構(gòu)建出來的BST就是下面這樣50 / \ 30 80 / \ \ 20 40 90 / \ 35 45這里我想多說一句查找效率的問題。BST查找的平均比較次數(shù)等于查找路徑上的節(jié)點(diǎn)數(shù)因此樹越胖越平衡效率越高。如果一個(gè)BST退化成一條鏈比如插入序列已經(jīng)是完全有序的 10、20、30、40、50那查找復(fù)雜度就是 O(n)和線性表沒有區(qū)別。軟考經(jīng)常拿這個(gè)說事問你二叉排序樹一定能提高查找效率嗎答案是否定的關(guān)鍵看樹的形態(tài)。成功查找時(shí)的平均查找長度 ASL 是軟考實(shí)打?qū)嵉挠?jì)算點(diǎn)。以上面那棵樹為例各節(jié)點(diǎn)層數(shù)分別是 1、2、2、3、3、3、4、4加起來22除以節(jié)點(diǎn)數(shù)8得到ASL成功為2.75?？碱}里如果給你一棵現(xiàn)成的BST讓你算ASL你只需要按層統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)就夠了。4.2 AVL四態(tài)旋轉(zhuǎn)的分類與判斷平衡二叉樹AVL是在BST基礎(chǔ)上增加了平衡約束任意節(jié)點(diǎn)的左右子樹高度差不超過1。高度差也就是左子樹高度減右子樹高度叫平衡因子取值只可能是 -1、0、1。插入節(jié)點(diǎn)后如果某個(gè)節(jié)點(diǎn)的平衡因子絕對(duì)值變成2就要旋轉(zhuǎn)調(diào)整。旋轉(zhuǎn)按失衡的兩個(gè)方向分成四類類型典型形態(tài)調(diào)整方式LL失衡節(jié)點(diǎn)的左子樹的左子樹插入對(duì)失衡節(jié)點(diǎn)做右旋RR失衡節(jié)點(diǎn)的右子樹的右子樹插入對(duì)失衡節(jié)點(diǎn)做左旋LR失衡節(jié)點(diǎn)的左子樹的右子樹插入先對(duì)左孩子左旋再對(duì)失衡節(jié)點(diǎn)右旋RL失衡節(jié)點(diǎn)的右子樹的左子樹插入先對(duì)右孩子右旋再對(duì)失衡節(jié)點(diǎn)左旋光記這四類名稱還不夠你得會(huì)判斷。我拿一個(gè)簡單序列舉例依次插入 15、20、12、18、10、8。插入前五個(gè)節(jié)點(diǎn)時(shí)樹一直保持平衡直到插入8。此時(shí)節(jié)點(diǎn)12的左子樹下是10再往下是8左子樹高度變2而右子樹為空所以12的平衡因子是2需要調(diào)整。再判斷插入方向12的左孩子是10而8是10的左孩子典型LL型所以對(duì)12做一次右旋。調(diào)整后10成為這個(gè)子樹的根8和12分別是它的左右孩子最終整棵樹依然平衡。做題時(shí)最容易錯(cuò)的是LR和RL。核心做法是先把連續(xù)下降的那條路徑找出來如果路徑先左后右就是LR先右后左就是RL。旋轉(zhuǎn)時(shí)不要去想復(fù)雜的結(jié)構(gòu)只需要記住LR要兩次旋轉(zhuǎn)并且第一步的旋轉(zhuǎn)點(diǎn)是失衡節(jié)點(diǎn)的孩子不是失衡節(jié)點(diǎn)本身。4.3 平均查找長度的考場(chǎng)速算AVL經(jīng)常和ASL結(jié)合出題。因?yàn)槠胶鈽涞母叨容^低成功查找的ASL通常接近 log 級(jí)別。不過考場(chǎng)給的樹一般很小直接按層數(shù)累加就行。失敗查找的ASL偶爾也會(huì)考。你需要知道失敗查找比較次數(shù)等于落入外部節(jié)點(diǎn)時(shí)經(jīng)過的內(nèi)部節(jié)點(diǎn)數(shù)這等于把樹的所有空指針位置看作外部節(jié)點(diǎn)然后逐層統(tǒng)計(jì)。這類題只要作圖的時(shí)候把空孩子位置補(bǔ)成虛線方塊計(jì)算就一目了然。我在備考時(shí)的一個(gè)體會(huì)是BST的刪除規(guī)則必須牢固掌握因?yàn)檐浛加袝r(shí)候會(huì)把刪除和插入混在一起考。刪除分三種情況葉子節(jié)點(diǎn)直接刪只有一個(gè)孩子就用孩子頂上來有兩個(gè)孩子時(shí)通常用左子樹的最大節(jié)點(diǎn)或者右子樹的最小節(jié)點(diǎn)來替換被刪節(jié)點(diǎn)然后再刪掉那個(gè)用于替換的節(jié)點(diǎn)。記住左子樹最大這個(gè)方向就夠了因?yàn)檫@樣替換后二叉排序樹性質(zhì)依然保持。5. 哈夫曼樹和哈夫曼編碼計(jì)算WPL的快捷方法5.1 構(gòu)造規(guī)則與WPL的兩種算法哈夫曼樹也叫最優(yōu)二叉樹它的核心指標(biāo)是帶權(quán)路徑長度 WPL也就是所有葉子的權(quán)值乘以路徑長度的總和。構(gòu)造算法本身不難一句話每次從集合里取出兩個(gè)權(quán)值最小的節(jié)點(diǎn)合并成一個(gè)新節(jié)點(diǎn)新節(jié)點(diǎn)的權(quán)值就是兩者之和再放回集合不斷重復(fù)直到只剩一個(gè)根。我用經(jīng)典權(quán)值集合 2、3、4、7 來演示取出2和3合并得5集合變?yōu)?、5、7取出4和5合并得9集合變?yōu)?、9取出7和9合并得16構(gòu)造完成。最終樹中7的路徑長度是14的路徑長度是22和3的路徑長度都是3所以 WPL 7×1 4×2 2×3 3×3 30。這里我要推薦一個(gè)考場(chǎng)上的快捷算法不需要計(jì)算每個(gè)葉子深度再相乘只需要把每次合并產(chǎn)生的新權(quán)值再次累加。上面三步產(chǎn)生的中間權(quán)值是5、9、16加起來也是30。道理很簡單每次合并一次相當(dāng)于被合并的權(quán)值整體向上走了一層累加的中間權(quán)值正好等于所有葉子權(quán)值與深度乘積的總和。用這個(gè)辦法做題速度至少快一倍。5.2 編碼不唯一但WPL唯一的理解哈夫曼編碼就是在哈夫曼樹上約定左分支為0、右分支為1從根到葉子的路徑串起來就是該葉子的編碼。上面例子里如果規(guī)定左0右1一種可能的編碼是7 → 04 → 102 → 1103 → 111每個(gè)編碼都不是另一個(gè)編碼的前綴這就是前綴碼解碼時(shí)不會(huì)產(chǎn)生歧義。壓縮效果就體現(xiàn)在高頻字符用短碼、低頻字符用長碼?？荚嚂?huì)問某字符集的哈夫曼編碼長度之和是多少本質(zhì)上還是在算WPL只不過把權(quán)值看成出現(xiàn)次數(shù)。很多同學(xué)會(huì)糾結(jié)是不是只有一棵特定的樹才最優(yōu)不是。當(dāng)有相同權(quán)值存在或者合并順序不同時(shí)樹的結(jié)構(gòu)可以不一樣編碼方案也不唯一但所有方案得到的最小WPL是一樣的。軟考判斷題特別喜歡考哈夫曼樹唯一嗎你要能馬上反應(yīng)過來不唯一。5.3 高頻陷阱題匯總哈夫曼樹有幾個(gè)隱藏結(jié)論選擇題直接拿來用很方便哈夫曼樹中不存在度為1的節(jié)點(diǎn)每個(gè)內(nèi)部節(jié)點(diǎn)都有兩個(gè)孩子。有 n 個(gè)葉子節(jié)點(diǎn)的哈夫曼樹總的節(jié)點(diǎn)數(shù)是 2n-1。權(quán)值越大的葉子越靠近根路徑越短。哈夫曼編碼是前綴碼也是可變長編碼。有一種題目會(huì)反過來問給定編碼總長度和各個(gè)頻率求某一字符的編碼長度。這時(shí)候你可以先構(gòu)造完整的哈夫曼樹再數(shù)對(duì)應(yīng)葉子的深度。還有一種是要求你判斷某一組編碼是否能作為哈夫曼編碼。除了看它是不是前綴碼外還要注意哈夫曼編碼對(duì)應(yīng)的樹必須是無單字節(jié)乏力的滿二叉樹結(jié)構(gòu)也就是每個(gè)非葉子都恰好有兩個(gè)孩子。只要不滿足選項(xiàng)就是錯(cuò)的。另外構(gòu)造時(shí)如果遇到權(quán)值相同的節(jié)點(diǎn)選擇不同會(huì)影響樹的形狀但只要合并策略正確WPL依然最優(yōu)。做題時(shí)不必為了標(biāo)準(zhǔn)答案糾結(jié)。6. 線索二叉樹與樹森林轉(zhuǎn)換冷門考點(diǎn)的快速記憶6.1 線索二叉樹的標(biāo)志位和后繼判定線索二叉樹看起來冷門但軟考真的會(huì)考而且一旦考到就是不折不扣的送分題因?yàn)轭}型很固定。它解決的問題是普通二叉樹在遍歷時(shí)要知道某個(gè)節(jié)點(diǎn)的前驅(qū)和后繼必須重新遍歷一遍很麻煩。于是我們把節(jié)點(diǎn)的空指針利用起來讓左空指針指向前驅(qū)右空指針指向后繼。關(guān)鍵在標(biāo)志位。每個(gè)節(jié)點(diǎn)增加兩個(gè)標(biāo)記 ltag 和 rtag0表示指針指向孩子1表示指針指向前驅(qū)或后繼。你必須記住這一點(diǎn)因?yàn)樗鼪Q定了指針的語義。考試最常見的考法是給一棵中序線索二叉樹問某個(gè)節(jié)點(diǎn)在中序遍歷中的后繼是誰。判斷規(guī)則只有一條如果該節(jié)點(diǎn)的右指針不是線索也就是 rtag0那么后繼是它右子樹的最左下節(jié)點(diǎn)如果右指針是線索rtag1那么右指針直接指向的后繼節(jié)點(diǎn)就是答案。舉個(gè)例子前面那棵樹的中序遍歷是 GDHBAECFI。節(jié)點(diǎn)D有右子樹右孩子是HH沒有左孩子所以D的中序后繼是H節(jié)點(diǎn)E沒有右孩子它的右指針被線索指到它的中序后繼F。這類題畫圖時(shí)線索線都是虛線看到虛線就要想到這代表前驅(qū)或后繼而不是孩子。6.2 樹轉(zhuǎn)二叉樹左孩子右兄弟的映射表樹和二叉樹之間的轉(zhuǎn)換軟考從來不考具體畫圖而是考遍歷對(duì)應(yīng)關(guān)系。樹轉(zhuǎn)二叉樹的核心規(guī)則叫左孩子右兄弟第一個(gè)孩子保留在左指針其他孩子依次作為上一個(gè)孩子的右孩子這樣一棵多叉樹就變成了二叉樹。這里最容易錯(cuò)的是遍歷對(duì)應(yīng)關(guān)系我整理成了固定表樹或森林的遍歷方式對(duì)應(yīng)二叉樹的遍歷方式樹的先根遍歷二叉樹的先序遍歷樹的后根遍歷二叉樹的中序遍歷森林的先序遍歷二叉樹的先序遍歷森林的中序遍歷二叉樹的中序遍歷注意樹的后根遍歷不是對(duì)應(yīng)二叉樹的后序遍歷而是對(duì)應(yīng)二叉樹的中序遍歷。這個(gè)反直覺的結(jié)論就是考題的重災(zāi)區(qū)一定要單獨(dú)強(qiáng)化記一下。我自己當(dāng)時(shí)備考就栽過一次后來再也沒錯(cuò)。6.3 森林轉(zhuǎn)二叉樹的鏈表特征森林轉(zhuǎn)換成二叉樹可以理解為先把每棵樹都轉(zhuǎn)成二叉樹再把后續(xù)每棵樹的根作為前一棵樹根的右孩子串起來。所以森林轉(zhuǎn)出來的二叉樹根節(jié)點(diǎn)一定沒有左孩子以外的問題不對(duì)根節(jié)點(diǎn)一定有左孩子除非第一棵樹根本身沒有孩子。更實(shí)用的結(jié)論是最終二叉樹根節(jié)點(diǎn)的右鏈上有多少個(gè)節(jié)點(diǎn)就代表原森林里有多少棵樹。因?yàn)橛益湸饋淼亩际切值軜洹Ｅe個(gè)例子如果森林由3棵樹組成轉(zhuǎn)換后二叉樹的根沿著右指針一直走一定能經(jīng)過另外兩個(gè)樹的根。做題遇到森林F對(duì)應(yīng)的二叉樹根節(jié)點(diǎn)右子樹為空說明什么這類題目答案就是原森林只有一棵樹。這些結(jié)論整體邏輯是一致的不要單獨(dú)背理解了根連接兄弟樹之后順理成章就能寫出來。7. 考前復(fù)習(xí)路線與易錯(cuò)清單7.1 知識(shí)依賴順序與時(shí)間預(yù)算備考二叉樹模塊我不建議按教材順序從頭到尾啃而是按照依賴關(guān)系安排順序。我自己的復(fù)習(xí)順序是這樣的先花半天搞定形態(tài)和性質(zhì)n0 n2 1、完全二叉樹計(jì)算、順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)再用一天主攻遍歷遞歸遍歷、非遞歸棧過程、序列還原。這一塊建議多畫圖接著用一天處理二叉排序樹和平衡樹構(gòu)建、刪除、平衡因子、旋轉(zhuǎn)哈夫曼樹單獨(dú)用半天重點(diǎn)是WPL快速算法和前綴碼判斷線索二叉樹和樹森林轉(zhuǎn)換放在最后半天因?yàn)樗鼈兒推渌鹿?jié)的關(guān)聯(lián)度低背清楚兩個(gè)表格就行。如果你整體復(fù)習(xí)時(shí)間只剩兩天那就壓縮第一步和第五步把大部分時(shí)間給遍歷和BST/AVL因?yàn)檎嬲拇蠓种殿}目集中在這兩塊。7.2 我的踩坑記錄與應(yīng)試技巧寫到這里我想分享幾個(gè)實(shí)戰(zhàn)中特別容易踩的點(diǎn)。第一做題習(xí)慣。還原二叉樹時(shí)我喜歡用簡單的括號(hào)表示法先草稿比如 A(B(D(G,H),),C(E,F(,I)))寫起來快不占地方。這種簡寫方式讓我在考場(chǎng)節(jié)省了不少時(shí)間你不妨也試試。第二判斷AVL旋轉(zhuǎn)方向時(shí)不要只盯著失衡節(jié)點(diǎn)看而要看插入點(diǎn)相對(duì)于失衡節(jié)點(diǎn)到底在左左、左右、右左還是右右。先找失衡節(jié)點(diǎn)再看它的孩子方向最后看插入點(diǎn)方向三步固定不動(dòng)。第三算哈夫曼WPL時(shí)如果對(duì)中間累加算法不放心就按葉子深度相乘來驗(yàn)算一遍。兩道算法結(jié)果一致才敢往答題卡上填。第四完全二叉樹判斷用層序遍歷不要數(shù)個(gè)數(shù)。層序遍歷過程中一旦遇到一個(gè)節(jié)點(diǎn)缺少左孩子或右孩子后面所有節(jié)點(diǎn)都必須是沒有孩子的葉子否則就不是完全二叉樹。最后再提醒一句復(fù)習(xí)到最后階段把那些最容易被繞的短句反復(fù)過幾遍——前序第一個(gè)是根后序最后一個(gè)是根樹的后根遍歷對(duì)應(yīng)二叉樹的中序遍歷哈夫曼樹無度為1的節(jié)點(diǎn)中序線索二叉樹中右指針為空時(shí)指向后繼節(jié)點(diǎn)。這些句子在考場(chǎng)上一眼能判斷對(duì)錯(cuò)干擾選項(xiàng)基本就廢掉了。二叉樹這一塊拿穩(wěn)分上午考試就能踏實(shí)很多。