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