11.2.1基本介紹

1.????? 給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若該樹(shù)的帶權(quán)路徑長(zhǎng)度(wpl)達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman Tree)。還有的書(shū)翻譯為霍夫曼樹(shù)。

2.????? 赫夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，權(quán)值較大的結(jié)點(diǎn)離根較近

11.2.2赫夫曼樹(shù)幾個(gè)重要概念和舉例說(shuō)明

1.????? 路徑和路徑長(zhǎng)度:在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或?qū)O子結(jié)點(diǎn)之間的通路，稱(chēng)為路徑。通路中分支的數(shù)目稱(chēng)為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。

2.????? 結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度:若將樹(shù)中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱(chēng)為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為:從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。

3.????? 樹(shù)的帶權(quán)路徑長(zhǎng)度:樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為WPL(weighted path length),權(quán)值越大的結(jié)點(diǎn)離根結(jié)點(diǎn)越近的二叉樹(shù)才是最優(yōu)二叉樹(shù)。

4.????? WPL最小的就是赫夫曼樹(shù)

11.2.3赫夫曼樹(shù)的創(chuàng)建思路圖解

給你一個(gè)數(shù)列{13,7,8,3,29,6,1}，要求轉(zhuǎn)成一顆赫夫曼樹(shù).

思路分析(示意圖):

構(gòu)成赫夫曼樹(shù)的步驟

1.????? 從小到大進(jìn)行排序,將每一個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)都是一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以看成是一顆最簡(jiǎn)單的二叉樹(shù)

2.????? 取出根節(jié)點(diǎn)權(quán)值最小的兩顆二叉樹(shù)

3.????? 組成一顆新的二叉樹(shù),該新的二叉樹(shù)的根節(jié)點(diǎn)的權(quán)值是前面兩顆二叉樹(shù)根節(jié)點(diǎn)權(quán)值的和

4.????? 再將這顆新的二叉樹(shù)，以根節(jié)點(diǎn)的權(quán)值大小再次排序，不斷重復(fù)1-2-3-4的步驟，直到數(shù)列中,所有的數(shù)據(jù)都被處理，就得到一顆赫大曼樹(shù)

圖解

11.2.4赫夫曼樹(shù)的代碼實(shí)現(xiàn)

代碼實(shí)現(xiàn)