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