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

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

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

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

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

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

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

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

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

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

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

(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)圖所示的二叉樹的帶權路徑長度小，這棵樹就是哈夫曼樹。可以驗證，哈夫曼樹的帶權路徑長度小。

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

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

2）首先判斷當前集合節點的個數是否大于1，如果不大于，則程序結束，集合里的節點即為創建好的哈夫曼樹的根節點，如果大于1，則轉至3

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

4）將新樹按權值由小到大的順序插入到集合中，轉至2。

實現代碼如下:

mytypes.h

bitree.h

bitree.c

linklist.h

linklist.c

main.c

makefile: