哈夫曼樹(shù)的圖文解析

　　假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、…、wn，哈夫曼樹(shù)的構(gòu)造規(guī)則為：

　　1. 將w1、w2、…，wn看成是有n 棵樹(shù)的森林（每棵樹(shù)僅有一個(gè)結(jié)點(diǎn)）；

　　2. 在森林中選出根結(jié)點(diǎn)的權(quán)值最小的兩棵樹(shù)進(jìn)行合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；

　　3. 從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；

　　4. 重復(fù)（02）、（03）步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)。

　　以{5，6，7，8，15}為例，來(lái)構(gòu)造一棵哈夫曼樹(shù)。

　　第1步：創(chuàng)建森林，森林包括5棵樹(shù)，這5棵樹(shù)的權(quán)值分別是5，6，7，8，15。

　　第2步：在森林中，選擇根節(jié)點(diǎn)權(quán)值最小的兩棵樹(shù)（5和6）來(lái)進(jìn)行合并，將它們作為一顆新樹(shù)的左右孩子（誰(shuí)左誰(shuí)右無(wú)關(guān)緊要，這里，我們選擇較小的作為左孩子），并且新樹(shù)的權(quán)值是左右孩子的權(quán)值之和。即，新樹(shù)的權(quán)值是11。 然后，將“樹(shù)5”和“樹(shù)6”從森林中刪除，并將新的樹(shù)（樹(shù)11）添加到森林中。

　　第3步：在森林中，選擇根節(jié)點(diǎn)權(quán)值最小的兩棵樹(shù)（7和8）來(lái)進(jìn)行合并。得到的新樹(shù)的權(quán)值是15。 然后，將“樹(shù)7”和“樹(shù)8”從森林中刪除，并將新的樹(shù)（樹(shù)15）添加到森林中。

　　第4步：在森林中，選擇根節(jié)點(diǎn)權(quán)值最小的兩棵樹(shù)（11和15）來(lái)進(jìn)行合并。得到的新樹(shù)的權(quán)值是26。 然后，將“樹(shù)11”和“樹(shù)15”從森林中刪除，并將新的樹(shù)（樹(shù)26）添加到森林中。

　　第5步：在森林中，選擇根節(jié)點(diǎn)權(quán)值最小的兩棵樹(shù)（15和26）來(lái)進(jìn)行合并。得到的新樹(shù)的權(quán)值是41。 然后，將“樹(shù)15”和“樹(shù)26”從森林中刪除，并將新的樹(shù)（樹(shù)41）添加到森林中。

　　此時(shí)，森林中只有一棵樹(shù)（樹(shù)41）。這棵樹(shù)就是我們需要的哈夫曼樹(shù)！

　　哈夫曼樹(shù)是一種樹(shù)形結(jié)構(gòu)，用哈夫曼樹(shù)的方法解編程題的算法就叫做哈夫曼算法。樹(shù)并不是指植物，而是一種數(shù)據(jù)結(jié)構(gòu)，因?yàn)槠浯娣欧绞筋H有點(diǎn)象一棵樹(shù)有樹(shù)叉因而稱為樹(shù)。 最簡(jiǎn)哈夫曼樹(shù)是由德國(guó)數(shù)學(xué)家馮。哈夫曼 發(fā)現(xiàn)的，此樹(shù)的特點(diǎn)就是引出的路程最短。

　　哈夫曼算法

　　哈夫曼樹(shù)是一種樹(shù)形結(jié)構(gòu)，用哈夫曼樹(shù)的方法解編程題的算法就叫做哈夫曼算法。樹(shù)并不是指植物，而是一種數(shù)據(jù)結(jié)構(gòu)。

　　定義：它是由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。因?yàn)檫@種樹(shù)最早由哈夫曼（Huffman）研究，所以稱為哈夫曼樹(shù)，又叫最優(yōu)二叉樹(shù)。

　　構(gòu)造哈夫曼樹(shù)

　?。踙tml］ view plain copy/*

　　* 創(chuàng)建Huffman樹(shù)

　　*

　　* @param 權(quán)值數(shù)組

　　*/

　　public Huffman（int a［］） {

　　HuffmanNode parent = null;

　　MinHeap heap;

　　// 建立數(shù)組a對(duì)應(yīng)的最小堆

　　heap = new MinHeap（a）;

　　for（int i=0; i《a.length-1; i++） {

　　HuffmanNode left = heap.dumpFromMinimum（）; // 最小節(jié)點(diǎn)是左孩子

　　HuffmanNode right = heap.dumpFromMinimum（）; // 其次才是右孩子

　　// 新建parent節(jié)點(diǎn)，左右孩子分別是left/right；

　　// parent的大小是左右孩子之和

　　parent = new HuffmanNode（left.key+right.key， left， right， null）;

　　left.parent = parent;

　　right.parent = parent;

　　// 將parent節(jié)點(diǎn)數(shù)據(jù)拷貝到“最小堆”中

　　heap.insert（parent）;

　　}

　　mRoot = parent;

　　// 銷毀最小堆

　　heap.destroy（）;

　　}

　　首先創(chuàng)建最小堆，然后進(jìn)入for循環(huán)。

　　每次循環(huán)時(shí)：

　?。?） 首先，將最小堆中的最小節(jié)點(diǎn)拷貝一份并賦值給left，然后重塑最小堆（將最小節(jié)點(diǎn)和后面的節(jié)點(diǎn)交換位置，接著將“交換位置后的最小節(jié)點(diǎn)”之前的全部元素重新構(gòu)造成最小堆）；

　?。?） 接著，再將最小堆中的最小節(jié)點(diǎn)拷貝一份并將其賦值right，然后再次重塑最小堆；

　?。?） 然后，新建節(jié)點(diǎn)parent，并將它作為left和right的父節(jié)點(diǎn)；

　?。?） 接著，將parent的數(shù)據(jù)復(fù)制給最小堆中的指定節(jié)點(diǎn)。