国产成人精品三级麻豆,色综合天天综合高清网,亚洲精品夜夜夜,国产成人综合在线女婷五月99播放,色婷婷色综合激情国产日韩

二叉樹的一個典型應用－哈夫曼樹一

哈夫曼樹是二叉樹的一個典型應用，利用哈夫曼樹，我們可以形成哈夫曼編碼，進而實現(xiàn)對數(shù)據(jù)的壓縮與解壓處理。

哈夫曼樹(Huffman Tree),又叫優(yōu)二叉樹，指的是對于一組具有確定權(quán)值的葉子結(jié)點的具有小帶權(quán)路徑長度的二叉樹。

當中的幾個概念我們不得不說一下:

(1)路勁(Path):從樹中的一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成兩個結(jié)點間的路徑。

(2)路徑長度(Path Length):路徑上的分支樹。

(3)樹的路徑長度(Path Length of Tree):從樹的根結(jié)點到每個結(jié)點的路徑長度之和。在結(jié)點數(shù)目相同的二叉樹中，完全二叉樹的路徑長度短。

(4)結(jié)點的權(quán)(Weight of Node):在一些應用中，賦予樹中結(jié)點的一個有實際意義的樹。

(5)結(jié)點的帶權(quán)路徑長度(Weight Path Length of Node):從該結(jié)點到樹的根結(jié)點的路徑長度與該結(jié)點的權(quán)的乘積。

(6)樹的帶權(quán)路徑長度(WPL):樹中所有葉子結(jié)點的帶權(quán)路徑長度之和

在下圖所示的四棵二叉樹，都有4個葉子結(jié)點，其權(quán)值分別1、2、3、4,他們的帶權(quán)路徑長度分別為:

(a)WPL = 1 x 2 + 2 x 2 + 3 x 2 + 4 X 2 = 20

(b)WPL = 1 x 1 + 2 x 2 + 3 x 3 + 4 x 3 = 28

(c)WPL = 1 x 3 + 2 x 3 + 3 x 2 + 4 x 1 = 19

(d)WPL = 2 x 1 + 1 x 2 + 3 x 3 + 4 x 3 = 29

其中，(c)圖所示的二叉樹的帶權(quán)路徑長度小，這棵樹就是哈夫曼樹�？梢则炞C，哈夫曼樹的帶權(quán)路徑長度小。

那么我們應該如何構(gòu)建一個哈夫曼樹呢？其實并不復雜：

1）首先構(gòu)建一個葉子節(jié)點集合，這里我用鏈表來表示，每個節(jié)點在插入到鏈表中時是按照權(quán)值由小到大順序插入的。

2）首先判斷當前集合節(jié)點的個數(shù)是否大于1，如果不大于，則程序結(jié)束，集合里的節(jié)點即為創(chuàng)建好的哈夫曼樹的根節(jié)點，如果大于1，則轉(zhuǎn)至3

3）取出集合中前兩個節(jié)點(取出后集合中已經(jīng)刪除掉這兩個節(jié)點),由這兩個節(jié)點構(gòu)建一顆新樹，新樹的權(quán)值為這兩個節(jié)點之和。權(quán)值較小的節(jié)點為新樹的左孩子，較大的節(jié)點為新樹的右孩子。

4）將新樹按權(quán)值由小到大的順序插入到集合中，轉(zhuǎn)至2。

實現(xiàn)代碼如下:

mytypes.h

bitree.h

bitree.c

linklist.h

linklist.c

main.c

makefile: