很多考生在備考2022年軟件設(shè)計師考試，希賽小編為大家整理了2022年軟件設(shè)計師考試知識點（六十二）：樹與二叉樹，供考生備考復(fù)習(xí)。

樹與二叉樹（★★★★★）

【考法分析】

1、本知識點的主要考查形式有：對數(shù)與二叉樹的一些概念和特性的描述，判斷其正誤；對于特殊的二叉樹（平衡樹、哈弗曼樹、滿二叉樹、排序樹等）定義、特性的描述判斷正誤、或根據(jù)題干描述構(gòu)造特殊的二叉樹，找到對應(yīng)的選項；考查二叉樹的遍歷結(jié)果，或根據(jù)遍歷序列，找到對應(yīng)的二叉樹。

【要點分析】

1、樹與二叉樹的特性：

（1）樹的概念：

雙親、孩子和兄弟：結(jié)點的子樹的根稱為該結(jié)點的孩子；相應(yīng)地，該結(jié)點稱為其子結(jié)點的雙親。具有相同雙親的結(jié)點互為兄弟

結(jié)點的度：一個結(jié)點的子樹的個數(shù)記為該結(jié)點的度

葉子節(jié)點：也稱為終端結(jié)點，指度為0的結(jié)點

內(nèi)部結(jié)點：指度不為0的結(jié)點稱為分支節(jié)點或非終端節(jié)點。除根結(jié)點之外，分支結(jié)點也稱為內(nèi)部結(jié)點

結(jié)點的層次：根為第一層，根的孩子為第二層，依次類推，若某節(jié)點在第i層，則其孩子結(jié)點在第i+1層

樹的高度：一顆樹的最大層次數(shù)記為樹的高度（深度）

（2）二叉樹的重要特性：

1、在二叉樹的第i層上最多有2i-1個結(jié)點（i≥1）；

2、深度為k的二叉樹最多有2k -1個結(jié)點（k≥1）；

3、對任何一棵二叉樹，如果其葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。

4、如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號（從第1層到

L log2n ?+1層，每層從左到右），則對任一結(jié)點i（1≤i≤n），有：

如果i=1，則結(jié)點i無父結(jié)點，是二叉樹的根；如果i>1，則父結(jié)點是L i/2 ? ；

如果2i>n，則結(jié)點i為葉子結(jié)點，無左子結(jié)點；否則，其左子結(jié)點是結(jié)點2i；

如果2i+1>n，則結(jié)點i無右子葉點，否則，其右子結(jié)點是結(jié)點2i+1。

2、特殊的樹

二叉樹：二叉樹是每個結(jié)點最多有兩個孩子的有序數(shù)，可以為空樹，可以只有一個結(jié)點。

滿二叉樹：任何結(jié)點，或者是樹葉，或者恰有兩棵非空子樹。

完全二叉樹：最多只有最小面的兩層結(jié)點的度可以小于2，并且最下面一層的結(jié)點全都集中在該層左側(cè)的若干位置。

平衡二叉樹：樹中任一結(jié)點的左右子樹高度之差不超過1。

查找二叉樹：又稱之為排序二叉樹。任一結(jié)點的權(quán)值，大于其左孩子結(jié)點，小于其右孩子結(jié)點。

線索二叉樹：在每個結(jié)點中增加兩個指針域來存放遍歷時得到的前驅(qū)和后繼信息。

最優(yōu)二叉樹：又稱為哈弗曼樹，它是一類帶權(quán)路徑長度最短的樹。

路徑是從樹中一個結(jié)點到另一個結(jié)點之間的通路，路徑上的分支數(shù)目稱為路徑長度。

樹的路徑長度是從樹根到每一個葉子之間的路徑長度之和。結(jié)點的帶權(quán)路徑長度為從該結(jié)點到樹根之間的路徑長度與該結(jié)點權(quán)值的乘積。

樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。

哈弗曼樹的構(gòu)造：（1）根據(jù)給定的權(quán)值集合，找出最小的兩個權(quán)值，構(gòu)造一棵子樹最為其孩子結(jié)點，二者權(quán)值之和作為根結(jié)點；（2）在原集合中刪除這兩個結(jié)點的權(quán)值，并引入根節(jié)點的權(quán)值；（3）重復(fù)步驟（1）和步驟（2），直到原權(quán)值集合為空。

哈夫曼編碼：根據(jù)哈夫曼樹進行邊長編碼，編碼長度與路徑長度相關(guān)，左側(cè)分支編碼為0（或1），右側(cè)分支編碼為1（或0），從根結(jié)點到對應(yīng)葉子結(jié)點所有路徑分支上的編碼記錄下來，即為該葉子結(jié)點的編碼。

3、樹的遍歷操作：遍歷是按某種策略訪問樹中的每個結(jié)點，且僅訪問一次的過程。

前序遍歷：又稱為先序遍歷，按根左右的順序進行遍歷。

后序遍歷：按左右根的順序進行遍歷。

中序遍歷：按左根右的順序進行遍歷。

層次遍歷：按層次順序進行遍歷。

【備考點撥】

1、掌握樹相關(guān)的概念和特性；

2、掌握一些特殊的樹的定義和特性；

3、掌握哈夫曼樹的構(gòu)造過程，哈夫曼編碼的構(gòu)造。

4、掌握樹的遍歷，能夠根據(jù)樹的遍歷序列反向構(gòu)造二叉樹的過程。