2023計算機考研初試在即，在最后階段建議各位同學將知識點再系統復習一遍，以免有所遺漏！2022計算機考研數據結構第四單元知識點包含樹、二叉樹、樹和森林、哈夫曼樹和哈夫曼編碼。高頓考研為大家整理了2022計算機考研數據結構第四單元知識點的詳細內容，供大家參考復習！
樹
樹(有根樹)是包括n個結點的有限非空集合。
特性：遞歸數據結構，層次結構
定義一：…定義二：…
相關術語：
雙親：若一個結點有子樹，那么該結點稱為子樹根的雙親。
孩子：子樹的根是該結點的孩子。
兄弟：有相同雙親的結點。
祖先：從根結點到某個結點路徑上的所有結點都是該結點的祖先。
后裔：一個結點的所有子樹上的任何結點都是該結點的后裔。
結點的度：一個結點擁有的子樹數。
樹的度：樹中最大的結點的度。
樹葉：度為零的結點。
分支結點：度不為零的結點。
結點的層次：從根開始定義起，根為第1層，其余結點的層次等于其雙親結點的層次加1。
樹的高度：樹中結點的最大層次。
森林：樹的集合。
二叉樹
二叉樹是結點的有限集合，可以為空集，區分左右子樹。
(1)性質：
二叉樹的第i(i>1)層上至多有2i-1個結點。
高度為h的二叉樹上至多有2^h–1個結點。
葉結點的個數總是比度為2的結點的個數多一個。
(2)幾個概念：
滿二叉樹：高度為h的二叉樹恰好有2^h–1個結點時稱為滿二叉樹。
完全二叉樹：一棵二叉樹中，只有最下面兩層結點的度可以小于2，并且最下一層的葉結點集中在靠左的若干位置上，這樣的二叉樹稱為完全二叉樹。(性質見書P71)
擴充二叉樹：除葉子結點外，其余結點都必須有兩個孩子。
(3)相關運算：
Root(x):若二叉樹非空，則x有根的值，并返回true，否則返回false。
MakeTree(x,left,right):構造一棵二叉樹：根的值為x，以left和right為左右子樹。
BreakTree(x,left,right):拆分二叉樹為三部分：x為根的值，left和right分別為原二叉樹的左、右子樹。
(4)二叉樹的遍歷
前序遍歷、中序遍歷、后序遍歷、層次遍歷(規則見書P75)
遞歸算法見P77
(5)二叉樹的存儲表示
順序表示：完全二叉樹中的結點可以按層次順序，存儲在一片連續的存儲單元中。
鏈接表示：lChild和rChild為分別指向左、右孩子的指針，element是元素域。共有n-1個指針域非空，n+1個空指針域。
樹和森林
(1)樹和森林的存儲表示(見書P82)
多重鏈表表示法
孩子兄弟鏈表示法
雙親表示法
三重鏈表表示法
(*)注意和二叉樹的存儲表示區分!
(2)樹的遍歷
前序遍歷：訪問根結點;從左往右前序遍歷根的每一棵子樹。
后序遍歷：從左往右后序遍歷根的每一棵子樹;訪問根結點。
層次遍歷：從上往下，同一層從左往右，訪問樹中的每個結點。
(3)森林的遍歷
加入一個虛結點，作為各棵樹的根;遍歷這棵樹;刪去虛結點。
先序遍歷：訪問第一棵樹的根;按先序遍歷第一棵樹的根節點的子樹組成的森林;按先序遍歷除第一棵樹外其余樹組成的森林。
中序遍歷、后序遍歷以此類推。
(4)森林與二叉樹的轉換(見書P81)
哈夫曼樹和哈夫曼編碼
(1)路徑長度：在二叉樹中，從根到任意一個后裔結點的路徑長度是指從根結點到該后裔結點的路徑上所包括的邊的數目。
二叉樹的內路徑長度：從根到其它所有分支結點的路徑長度之和。
二叉樹的外路徑長度：從根到其它所有葉子結點的路徑長度之和。
二叉樹的加權路徑長度：二叉樹中所有葉子結點的加權路徑長度之和。
(2)哈夫曼樹和哈夫曼算法
最優二叉樹：具有最小加權路徑長度的二叉樹。
哈夫曼算法：由哈夫曼給出、用于構造最優二叉樹的算法。
a.用給定的一組權值{w1,w2,…,wn}，生成一個有n棵二叉樹組成的集合F={T1，T2，…，Tn}，其中，每棵二叉樹Ti只有一個結點，即權值為wi的根結點。
b.從F中選擇兩棵根結點權值最小的二叉樹，作為新二叉樹根的左、右子樹，新二叉樹根的權值是左、右子樹根結點的權值之和。
c.從F中刪除這兩棵二叉樹，另將新二叉樹加入F中。
d.重復(2)和(3)，直到F中只包含一棵二叉樹為止。
哈夫曼樹：用哈夫曼算法構造的最優二叉樹。
(3)哈夫曼編碼
哈夫曼樹的每個葉結點對應一個字符。在從哈夫曼樹的每個結點到其左孩子的邊上標上1。將從根到每個葉子的路徑上的數碼連接起來，就是該葉子所代表的字符的編碼。