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

樹(shù)與二叉樹(shù)（★★★★★）

【考法分析】

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

【要點(diǎn)分析】

1、樹(shù)與二叉樹(shù)的特性：

（1）樹(shù)的概念：

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

結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)的個(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ù)的高度：一顆樹(shù)的最大層次數(shù)記為樹(shù)的高度（深度）

（2）二叉樹(shù)的重要特性：

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

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

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

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

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

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

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

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

2、特殊的樹(shù)

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

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

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

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

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

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

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

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

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

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

哈弗曼樹(shù)的構(gòu)造：（1）根據(jù)給定的權(quán)值集合，找出最小的兩個(gè)權(quán)值，構(gòu)造一棵子樹(shù)最為其孩子結(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ù)哈夫曼樹(shù)進(jìn)行邊長(zhǎng)編碼，編碼長(zhǎng)度與路徑長(zhǎng)度相關(guān)，左側(cè)分支編碼為0（或1），右側(cè)分支編碼為1（或0），從根結(jié)點(diǎn)到對(duì)應(yīng)葉子結(jié)點(diǎn)所有路徑分支上的編碼記錄下來(lái)，即為該葉子結(jié)點(diǎn)的編碼。

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

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

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

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

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

【備考點(diǎn)撥】

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

2、掌握一些特殊的樹(shù)的定義和特性；

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

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