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