基本介紹
赫夫曼樹（Huffman tree）：
- 給定 n 個 權值 作為 n 個 葉子節點，構造一顆二叉樹，若該樹的 帶權路徑長度（WPL）達到最小，稱這樣的二叉樹為 最優二叉樹，也稱為 哈夫曼樹（Huffman Tree），還有的叫 霍夫曼樹
- 赫夫曼樹是帶權路徑長度最短的樹，權值較大的節點離根節點較近
詳情請看百度百科——哈夫曼樹
重要概念
-
路徑 和 路徑長度：
在一顆樹中，從一個節點往下可以到達的孩子或孫子節點之間的通路，稱為 路徑。
通路中分支的數目稱為路徑長度。若規定根節點的層數為 1，則從根節點到第 L 層節點的路徑長度為 L-1
-
節點的權 和 帶權路徑長度
若将樹中節點賦給一個有着某種含義的數值，則這個數值稱為該節點的 權。
節點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。
-
樹的帶權路徑長度
所有葉子節點的帶權路徑長度之和，記為 WPL（weighted path length），權值越大的節點離根節點越近的二叉樹才是最優二叉樹
- 下圖
WPL
如上圖：
-
權
-
路徑長度
-
帶權路徑長度
-
樹的帶權路徑長度
建立思路
以數列
[ 13,7,8,3,29,6,1 ]
進行講解。
- 首先将它進行從小到大進行排序，排序後是：
1,3,6,7,8,13,29
- 取出根節點權值最小的兩棵樹：
1 和 3
- 組成一棵新的二叉樹，該二叉樹的根節點權值是：這兩顆樹的權值之和，如下圖：
資料結構與算法——赫夫曼樹（哈夫曼樹） - 再将這顆新的二叉樹，以 根節點的權值大小，再次排序，并不斷重複上述步驟
資料結構與算法——赫夫曼樹（哈夫曼樹）
如圖所示：将剩餘未處理的節點，與新的根節點權值進行排序，那麼再次取最小的兩棵樹
4 和 6
，組成新的根節點 10
一般來說，可以将左節點指向權值較大的，右節點指向權值較小的，但是這個不做特别規定。重複以上過程，直到組成如下圖這顆赫夫曼樹
單單看文字圖解，就有點索然無味了，下面進行代碼實作。
代碼實作
首先進行推導實作，友善了解。
推導實作
/**
* 赫夫曼樹實作
*/
public class HuffmanTreeTest {
/**
* 首先推導實作
*/
@Test
public void processDemo() {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
// 1. 為了實作友善，先将每個元素轉成 Node 對象，并裝入 arrayList 中
List<Node> nodes = new ArrayList<>();
for (int i : arr) {
nodes.add(new Node(i));
}
// 2. 從小到大排序
Collections.sort(nodes);
// 3. 取出兩個較小的樹
// 因為從小到大排序了
Node left = nodes.get(0);
Node right = nodes.get(1);
// 4. 構成成新的二叉樹
Node parent = new Node(left.value + right.value);
parent.left = left;
parent.right = right;
// 5. 從 list 中删除已經處理過的二叉樹
nodes.remove(left);
nodes.remove(right);
// 6. 将新的二叉樹添加到 list 中，為下一輪建構做準備
nodes.add(parent);
// 最後來看一下結果
System.out.println("原始數組：" + Arrays.toString(arr));
System.out.println("新的節點：" + nodes);
}
}
/**
* 節點
*
* 為了讓Node 對象進行排序，用Collections工具類集合排序
* 讓Node 實作Comparable接口，因為會用到 Collections.sort(nodes); 進行排序，是以一定要實作Comparable接口
*/
class Node implements Comparable<Node> {
int value; // 權
Node left;
Node right;
public Node(int value) {
this.value = value;
}
/**
* 為了列印友善
*
* @return
*/
@Override
public String toString() {
return value + "";
}
/**
* 從小到大排序
*
* @param o
* @return
*/
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
}
運作結果輸出
原始數組：[13, 7, 8, 3, 29, 6, 1]
新的節點：[6, 7, 8, 13, 29, 4]
可以看到，第一輪的處理之後，的确如我們的建立思路解說一緻。
那麼建立一顆完整的赫夫曼樹的核心代碼就在上面，隻要對上述步驟進行重複執行，就可以了。
完整實作
@Test
public void createHuffmanTreeTest() {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
//建構赫夫曼樹
Node huffmanTree = createHuffmanTree(arr);
// 前序周遊
huffmanTree.list();
}
private Node createHuffmanTree(int[] arr) {
// 1. 為了實作友善，先将每個元素轉成 Node 對象，并裝入 arrayList 中
List<Node> nodes = new ArrayList<>();
for (int i : arr) {
nodes.add(new Node(i));
}
//核心代碼重複執行
while (nodes.size() > 1) {
// 2. 從小到大排序
Collections.sort(nodes);
// 3. 取出兩個較小的樹
Node left = nodes.get(0);
Node right = nodes.get(1);
// 4. 構成成新的二叉樹
Node parent = new Node(left.value + right.value);
parent.left = left;
parent.right = right;
// 5. 從 list 中删除已經處理過的二叉樹
nodes.remove(left);
nodes.remove(right);
// 6. 将新的二叉樹添加到 list 中，為下一輪建構做準備
nodes.add(parent);
}
// 傳回赫夫曼樹的 root 節點
// 因為前面從小到大排序的，最後一個就是最大節點
return nodes.get(0);
}
測試輸出，輸出的是前序周遊的順序。
67
29
38
15
7
8
23
10
4
1
3
6
13