為幫助考生備考軟考軟件設計師考試，希賽小編為大家整理了2022下半年軟件設計師知識點：樹與二叉樹，相信對大家備考會有幫助。

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

【考法分析】

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

【要點分析】

1、樹與二叉樹的特性：

（1）樹的概念：

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

結點的度：一個結點的子樹的個數記為該結點的度

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

內部結點：指度不為0的結點稱為分支節點或非終端節點。除根結點之外，分支結點也稱為內部結點

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

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

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

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

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

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

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

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

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

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

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

2、特殊的樹

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

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

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

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

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

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

最優二叉樹：又稱為哈弗曼樹，它是一類帶權路徑長度最短的樹。

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

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

樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和。

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

哈夫曼編碼：根據哈夫曼樹進行邊長編碼，編碼長度與路徑長度相關，左側分支編碼為0（或1），右側分支編碼為1（或0），從根結點到對應葉子結點所有路徑分支上的編碼記錄下來，即為該葉子結點的編碼。

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

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

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

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

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

【備考點撥】

1、掌握樹相關的概念和特性；

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

3、掌握哈夫曼樹的構造過程，哈夫曼編碼的構造。

4、掌握樹的遍歷，能夠根據樹的遍歷序列反向構造二叉樹的過程。