為幫助考生備考軟考軟件設(shè)計(jì)師考試，希賽小編為大家整理了2022下半年軟件設(shè)計(jì)師知識(shí)點(diǎn)：樹與二叉樹，相信對(duì)大家備考會(huì)有幫助。

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

【考法分析】

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

【要點(diǎn)分析】

1、樹與二叉樹的特性：

（1）樹的概念：

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

結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)記為該結(jié)點(diǎn)的度

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

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

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

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

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

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

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

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

4、如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)（從第1層到

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

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

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

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

2、特殊的樹

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

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

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

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

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

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

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

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

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

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

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

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

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

前序遍歷：又稱為先序遍歷，按根左右的順序進(jìn)行遍歷。

后序遍歷：按左右根的順序進(jìn)行遍歷。

中序遍歷：按左根右的順序進(jìn)行遍歷。

層次遍歷：按層次順序進(jìn)行遍歷。

【備考點(diǎn)撥】

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

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

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

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