哈夫曼树（Huffman Tree），也叫霍夫曼树，或者赫夫曼树，又称为最优树，学习哈夫曼树之前我们先了解几个概念。
路径：从任一个节点往下到达其他节点之间的通路。
路径长度：路径中线段的个数。
节点的权：节点的值。
节点的带权路径长度：从根节点到该节点之间的路径长度与该节点权的乘积。
树的带权路径长度：所有叶子节点的带权路径长度之和。
在讲解哈夫曼树之前我们来看这样一个问题，我们都知道现在有个词叫大数据杀熟，也就是说在某一个平台你消费越多，折扣就越少，消费越少折扣越多，而平台根据大家的消费情况把大家分成 5 个等级，等级从高到低分别为：贵宾卡>豪卡>金卡>银卡>铜卡。也就是说你消费越低等级就越高，优惠力度就越大。
每次你消费的时候，平台会根据你以往的消费金额来判断是你什么级别的用户，然后在给你什么样的优惠额度，如上图所示，每次都这样查询。后来平台发现用户的消费金额小于 1000 的只有 1% ，如果每次先判断是否小于 1000 ，很明显大多数情况下是无效的。为了减少判断次数，最有效的查询方式就是用户最多的离根节点越近。假设消费金额在 5000-20000 的有 40% ，消费金额在 20000-50000 的有 45% ，这两个都占了 85 了，这种情况下可以像下面这样查询。
这里的百分比就相当于叶子节点的权值，假设用它构造一棵二叉树，这棵二叉树可以有多种，其中带权路径长度最小的就是最优树，也是哈夫曼树。哈夫曼树就是给定 n 个权值作为叶子节点，构造一棵二叉树，并且该树的带权路径长度达到最小。树的带权路径长度 WPL(Weighted Path Length of Tree) 可以记为 WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln) ，其中 W? 表示节点的权值， L? 表示从根节点到该节点的路径长度。要想让 WPL 最小，权值最大的节点要离根节点最近。如下图所示，是用权值为 9,3,2,8 构造的两棵树。
哈夫曼树的构造
哈夫曼构造的原则是权值越大离根节点越近，权值越小离根节点越远。哈夫曼树的构造使用的是贪心算法，他的步骤如下：
- 用给定的
n个权值创建n棵只有一个节点的树，把他们添加到集合S中。 - 每次从集合
S中取出两个权值最小的树，组成一棵新的二叉树，该树的权值为他的两个子节点的权值之和，然后把这棵树添加到集合S中。 - 重复步骤
2，直到集合中只有一棵树为止，这棵树就是哈夫曼树。
因为每次都是选择两棵子树合并成一棵，所以哈夫曼树只有度为 0 和 2 的节点，没有度为 1 的节点，也就是说哈夫曼树中每个节点要么没有子节点，要么有两个子节点，不可能只有一个子节点。一棵有 n 个叶子节点的哈夫曼树总共有 2*n-1 个节点。每次从集合中取出权值最小的两棵树，可以使用最小堆，来看下代码。
// 哈夫曼树的节点类。
public static class HNode {
private int value;// 权值。
private HNode left;// 左子节点。
private HNode right;// 右子节点。
private int deep;// 路径长度，也是节点的深度。
public HNode(int value) {
this.value = value;
}
public HNode(HNode left, HNode right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
}
private HNode root;// 根节点。
public void createTree(int[] nums) {
// 优先队列，也是最小堆。
Queue<HNode> queue = new PriorityQueue<>(Comparator.
comparingInt(o -> o.value));
// 创建节点并全部添加到队列中。
for (int num : nums)
queue.offer(new HNode(num));
while (queue.size() > 1) {// 大于 1 就合并。
HNode left = queue.poll();// 出队。
HNode right = queue.poll();
// 两棵子树合并成一棵。
HNode parent = new HNode(left, right, left.value + right.value);
// 把合并之后的子树添加到队列中。
queue.add(parent);
}
root = queue.poll();//最后一个出队。
}
// 树的BFS遍历，计算树的带权路径长度。
public int getWeight() {
Queue<HNode> queue = new LinkedList<>();
queue.add(root);// 把根节点添加到队列中。
int res = 0;// 树的带权路径长度。
while (!queue.isEmpty()) {
HNode cur = queue.poll();// 出队。
// 一个节点要么是叶子节点，要么有两个子节点，不可能只有一个子节点。
if (cur.left != null) {
// 非叶子节点计算他们的深度，子节点深度比父节点深度大 1 。
cur.left.deep = cur.deep + 1;
cur.right.deep = cur.deep + 1;
queue.add(cur.left);// 添加到队列中。
queue.add(cur.right);
} else {
// 累加叶子节点的带权路径长度。
res += cur.deep * cur.value;
}
}
return res;
}
哈夫曼编码
哈夫曼树的最大用处就是哈夫曼编码，他是一种用于无损数据压缩的权编码算法。比起定长的 ASCII 编码来说，哈夫曼编码能节省很多空间，尤其对于重复率比较高的字符数据。比如一个字符串有 67 个字母，其中有 50个字母 a ， 2 个字母 b ， 5 个字母 c ， 10 个字母 d 。如果我们使用定长的比特来表示他们，那么每个字母至少需要 2 个比特，总共需要 67*2=134 个比特。
00 表示 a
01 表示 b
10 表示 c
11 表示 d
来看下使用哈夫曼编码需要多少比特。看之前需要构建哈夫曼树，每个字母个数相当于该字母的权值，构建之后我们规定哈夫曼树中左分支为 0，右分支为 1，从根节点到每个叶节点路径上 0 和 1 组成的序列就是该叶子节点对应字符的编码。比如 a 是根节点的右分支，所以他是 1 ，c 从根节点往下是左左右，所以是 001 ，所以可以这样表示。
1 表示 a
000 表示 b
001 表示 c
01 表示 d
通过计算发现他们需要的比特是 91 ，比定长的比特 134 少，节省了不少空间。值得一提的是，在一个哈夫曼树编码中，不会出现某个编码是另一个编码的前缀的。什么意思呢？比如说如果我们选择 001 表示 a ， 00 表示 b ， 1 表示 3 ，当出现 001 的时候他是表示 a 还是表示 bc ？我们没法确定，但哈夫曼编码不会出现这种情况，因为在哈夫曼树中，每个字母对应的节点都是叶子节点，而他们对应的二进制码是由根节点到各自节点的路径所决定的，正因为他们都是叶子节点，所以每个节点的路径不可能是其他节点路径的前缀。来看下哈夫曼树的节点类。
static class HNode {// 哈夫曼树的节点类。
private Character ch;// 节点对应的字符，只有叶子节点有。
private int count;// 节点的权值。
private HNode left = null;// 左子节点。
private HNode right = null;// 右子节点。
HNode(Character ch, int freq) {
this.ch = ch;
this.count = freq;
}
public HNode(HNode left, HNode right, int freq) {
this.count = freq;
this.left = left;
this.right = right;
}
}
在来看下哈夫曼树的创建，和前面讲的类似，只不过这里多了统计字符串频率的步骤。
public HNode createTree(String str) {// 创建哈夫曼树。
// 统计每个字符出现的次数。
Map<Character, Integer> freq = new HashMap<>();
for (char ch : str.toCharArray())
freq.put(ch, freq.getOrDefault(ch, 0) + 1);
// 优先队列，也是最小堆。
Queue<HNode> queue = new PriorityQueue<>(Comparator.
comparingInt(a -> a.count));
// 为每个字母创建一个节点，并添加到队列中。
for (Map.Entry<Character, Integer> entry : freq.entrySet())
queue.add(new HNode(entry.getKey(), entry.getValue()));
while (queue.size() > 1) {// 大于 1 就合并。
HNode left = queue.poll();// 出队。
HNode right = queue.poll();
// 两棵子树合并成一棵。
HNode parent = new HNode(left, right, left.count + right.count);
queue.add(parent);// 把合并之后的子树添加到队列中。
}
return queue.poll();//最后一个出队。
}
接着来看哈夫曼树的编码和解码。
// 把叶子节点映射的编码存放到map中。
private static Map<Character, String> encodeMap(HNode root) {
Map<Character, String> map = new HashMap<>();
traverseTree(root, "", map);
return map;
}
// 递归哈夫曼树并将叶子节点的编码存储到map中。
private static void traverseTree(HNode root, String bitStr,
Map<Character, String> map) {
if (root == null)
return;
if (isLeaf(root)) { // 找到叶子节点，存储到map中。
map.put(root.ch, bitStr.length() > 0 ? bitStr : "1");
return;
}
// 分别遍历左右子节点，左分支为0，有右分支为1。
traverseTree(root.left, bitStr + "0", map);
traverseTree(root.right, bitStr + "1", map);
}
// 哈夫曼编码。
private static String encode(String str, Map<Character, String> map) {
StringBuilder sBuilder = new StringBuilder();
// 字符串中的字母换成对应的编码。
for (char ch : str.toCharArray())
sBuilder.append(map.get(ch));
return sBuilder.toString();
}
// 哈夫曼解码的第一种方式。
private static String decode(String encodeStr, Map<Character, String> map) {
StringBuilder decodeStr = new StringBuilder();
while (encodeStr.length() > 0) {
// 遍历字符对应的编码，从encodeStr中截取。
for (Map.Entry<Character, String> entry : map.entrySet()) {
String charEncode = entry.getValue();
if (encodeStr.startsWith(charEncode)) {
decodeStr.append(entry.getKey());
// 截取。
encodeStr = encodeStr.substring(charEncode.length());
break;
}
}
}
return decodeStr.toString();
}
// 哈夫曼解码的第二种方式。
private static String decode(HNode root, String encodeStr) {
StringBuilder sBuilder = new StringBuilder();
if (isLeaf(root)) {// 只有一个字母，直接添加。
while (root.count-- > 0)
sBuilder.append(root.ch);
} else {// 根据编码字符串进行解码。
int index = 0;
while (index < encodeStr.length()) {
int[] res = decode(root, index, encodeStr);
index = res[0];
sBuilder.append((char) res[1]);
}
}
return sBuilder.toString();
}
// 遍历哈夫曼树并解码。
private static int[] decode(HNode root, int index, String encodeStr) {
if (isLeaf(root)) // 找到叶子节点。
return new int[]{index, root.ch};
root = encodeStr.charAt(index++) == '0' ? root.left : root.right;
return decode(root, index, encodeStr);// 递归。
}
// 判断该节点是否是叶子节点。
public static boolean isLeaf(HNode root) {
return root.left == null && root.right == null;
}
哈夫曼树的解码我列出了两种方式，大家选择其中的一种即可，我们来测试下。
public static void main(String[] args) {
String str = "aabcddcaaaadcbbb";// 源字符串。
HuffmanCode mHuffmanCode = new HuffmanCode();
HNode root = mHuffmanCode.createTree(str);// 创建哈夫曼树。
Map<Character, String> map = encodeMap(root);
System.out.println("字母映射关系：" + map);
System.out.println("解码之前的字符串：" + str);
String encodeStr = encode(str, map);// 编码。
System.out.println("编码之后的字符串：" + encodeStr);
String decodeStr = decode(root, encodeStr);// 解码。
System.out.println("解码之后的字符串：" + decodeStr);
}
看一下运行结果：
字母映射关系：{a=0, b=10, c=110, d=111}
解码之前的字符串：aabcddcaaaadcbbb
编码之后的字符串：00101101111111100000111110101010
解码之后的字符串：aabcddcaaaadcbbb
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
