哈弗曼樹往往都會根據哈夫曼編碼結合著來說，因此這篇文章，主要結合著面試問題來說明。
一、基本概念
哈夫曼樹的目的是找出存放一串字符所需的最少的二進制編碼， 原理是通過統計出每種字符出現的頻率！不斷地對其合併。
舉個例子：有一串字符，現在把這些字符進行統計，頻率表 A：60, B:45, C:13 D:69 E:14 F:5 G:3。現在要對這些字符進行編碼，但是前提是使用最少的二進制編碼。這時候怎麼辦呢？這就用到了我們的哈弗曼樹。
我們需要構造一個哈弗曼樹，構造赫夫曼樹的算法是一個貪心算法，貪心的地方在於：總是選取當前頻率(權值)最低的兩個結點來進行合併，構造新結點。
現在我們就來構造一顆哈弗曼樹。
二、構造哈弗曼樹
剛剛我們已經說了，構造哈夫曼樹是每次選取當前頻率最低的兩個節點來進行合併就好了。
1、原始序列
2、選取最小的F和G節點合併
3、選取目前最小的C節點與8合併
4、繼續重複以上步驟進行合併
到此為止，我們的哈弗曼樹就已經構造出來了。接下來我們添加01規則，進行哈夫曼編碼。
三、哈夫曼編碼
哈夫曼編碼的規則是，左邊添加0，右邊添加1。看下圖就明白了。
OK，也就是在每一條邊上添加了01。此時我們來看每一個字符的編碼。
A：10 B：01 C：0011 D：11 E：000 F：00101 G：00100
四、java實現哈夫曼編碼
我們直接給出一個整體的哈夫曼編碼的java實現。
第一步：定義一個節點
第二步：實現哈夫曼編碼
分享到:
閱讀更多 Java的架構師技術棧 的文章
