一、首先要知道哈弗曼樹的原理：
如果有一些結點的權值分别是0,1，2,3,4,5,6,7,8,9
建構出的Huffmantree是什麼？
<a href="http://s1.51cto.com/wyfs02/M01/86/41/wKiom1e6YU7SQ9Y3AAAcaqfNGT0543.png" target="_blank"></a>
根據權值{0,1,2,3,4,5,6,7,8,9}構成10棵二叉樹的集合H，其中每一棵二叉樹隻有一個根節點分别為{0,1,2,3,4,5,6,7,8,9}；，左右子樹為空；
在建構的二叉樹中選擇權值最最小的兩棵樹作為左右子樹構造一棵新的二叉樹，并且置新的二叉樹的根節點的權值為左右子樹權值之和；
在H中删掉上一步的兩棵樹，同時将新得到的二叉樹加入H中；
重複上述步驟，知道H中隻剩一棵樹，而這棵樹就是Huffmantree。
二、哈弗曼樹的建構：
因為每次選擇權值最小的兩棵樹建構新的樹，是以使用堆來實作，自然這裡需要建構最小堆；
三、檔案壓縮的原理：
檔案壓縮需要的是哈夫曼編碼，對于上面的Huffmantree，怎樣來進行編碼呢？
從根節點開始，根節點的右支編碼為1，而左支編碼為0，依次遞歸下去，得到如下編碼圖：
哈夫曼編碼隻是對葉子節點編碼；而且可以發現權值越小的，它的哈夫曼編碼越長，權值越大的，哈夫曼編碼越短。
那如何運用到檔案壓縮中呢？
舉一個簡單的例子吧，假設有一個檔案的内容是“abbcccdddd“,‘a’出現的次數是1，‘b’出現的次數是2，‘c’出現的次數是3，‘d’出現的次數是4，以各字元出現的次數建構一個哈夫曼樹，并為各字元編碼，結果是：
‘a’：100； ‘b’：101； ‘c’：11； ‘d’：0；
以編碼的形式按照原字元的順序寫入壓縮檔案，就應該是這樣滴：
1001011011111110000
這一個0或1代表一個二進制位，那壓縮檔案是多大呢？3個位元組
原檔案是多大呢？10個位元組
這就是檔案壓縮的原理。
四、檔案壓縮的過程：
根據上面的例子，首先要統計待壓縮檔案中各字元出現的次數，然後構造Huffmantree，得到編碼，把編碼寫入壓縮檔案，不夠一個位元組的就在後面補零，為了實作解壓縮，需要将每個字元出現的次數寫入配置檔案。
五、檔案解壓縮的過程：
通過配置檔案，建構Huffmantree得到哈弗曼編碼，根據壓縮檔案裡的編碼到Huffmantree裡面找，找到葉子結點，就把葉子節點的字元寫入解壓縮檔案中。
本文轉自 七十七快 51CTO部落格，原文連結:http://blog.51cto.com/10324228/1840666