哈夫曼樹的圖文解析

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

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

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

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

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

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

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

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

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

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

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

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

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

　　哈夫曼算法

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

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

　　構(gòu)造哈夫曼樹

　?。踙tml］ view plain copy/*

　　* 創(chuàng)建Huffman樹

　　*

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

　　*/

　　public Huffman（int a［］） {

　　HuffmanNode parent = null;

　　MinHeap heap;

　　// 建立數(shù)組a對應(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)。