gogo专业大尺度亚洲高清人体,美女张开双腿让男生桶,亚洲av无码一区二区三区鸳鸯影院,久久久久国产精品人妻

二叉樹(shù)的一個(gè)典型應(yīng)用－哈夫曼樹(shù)一

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

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

當(dāng)中的幾個(gè)概念我們不得不說(shuō)一下:

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

(2)路徑長(zhǎng)度(Path Length):路徑上的分支樹(shù)。

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

(4)結(jié)點(diǎn)的權(quán)(Weight of Node):在一些應(yīng)用中，賦予樹(shù)中結(jié)點(diǎn)的一個(gè)有實(shí)際意義的樹(shù)。

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

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

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

(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)圖所示的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度小，這棵樹(shù)就是哈夫曼樹(shù)�？梢则�(yàn)證，哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度小。

那么我們應(yīng)該如何構(gòu)建一個(gè)哈夫曼樹(shù)呢？其實(shí)并不復(fù)雜：

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

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

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

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

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

mytypes.h

bitree.h

bitree.c

linklist.h

linklist.c

main.c

makefile: