如果你對(duì)“哈夫曼樹(shù)和哈夫曼編碼”還不了解，那就趕緊來(lái)看看高頓小編整理的2024計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)考點(diǎn)【哈夫曼樹(shù)和哈夫曼編碼】的具體信息吧！
2024計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)考點(diǎn)【哈夫曼樹(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)，就是該葉子所代表的字符的編碼。
　　本文內(nèi)容整理于網(wǎng)絡(luò)，僅供參考。
　　關(guān)于2024計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)考點(diǎn)【哈夫曼樹(shù)和哈夫曼編碼】的內(nèi)容，小編就給大家簡(jiǎn)單介紹到這里了。如果還有其他考研考試相關(guān)內(nèi)容想要了解的，就請(qǐng)登錄高頓考研頻道看看吧。
　　小編為2024考研的小伙伴們準(zhǔn)備了豐富的學(xué)習(xí)資料，點(diǎn)擊下方藍(lán)色圖片即可領(lǐng)取哦~
考研備考資料