引言
上篇博客学习了二叉树的基本操作原理，今天我们在此基础上学习二叉树的典型应用:赫夫曼编码树，赫夫曼编码(Huffman Coding)是一种编码方法。它使用变长编码表对源符号（如文件中的一个字母）进行编码，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。JPG图片及文件压缩就是用的赫夫曼编码。赫夫曼编码的节点带有权重(一般指出现频次),而且编码的字符都是叶子节点，他们的父节点保存左右子节点的权重和。它的结构图如下:
赫夫曼编码树结构
从图中看到频次越高的元素越接近根节点，反之亦然。规定做路径代号0，右路径代号1，而各个字符的编码就是从根节点到叶子节点的路径代码，如:右图A的编码为1,D为01，J为001，左图H的编码为101等等。下面是赫夫曼树的实现。
赫夫曼树的构建
已上图中的左图为例子说明它的构建和编码流程:
1.字符节点按权重从小到大排序
2.遍历过程主要执行节点合并操作:
1>最小权重的两个节点合并为一个新的子树，它的权重为左右节点的权重和(如图中的EF节点合并为子树，根节点权重为4);
2>后面挂载新的元素的时候(如挂载B节点)，比较新元素和子树的权重，前者大，则新元素节点为合并新子树的右边孩子(如上面左图中的B节点权重5比EF的根节点4大);
3.直到数组遍历完，都执行1>和2>流程
4.树构建完毕,从根节点到叶子节点的路径代码就是编码，每一层节点的编码都是基于它的父节点，因此可以通过递归实现，递归结束条件为遍历到叶子节点。
赫夫曼树数据结构描述
赫夫曼树节点元素:包含路径编码和权重，载体为前面用的二叉树节点BinaryNode.
/**
* Created by chenming on 17/1/11.
*/
public class HuffmanModel implements Comparable<HuffmanModel>{
public Integer weight;//权重
public int data;//data
public String code = "";//路径编码
public HuffmanModel(int data){
this.weight = this.data = data;//简化处理
}
@Override
public int compareTo(HuffmanModel o) {
return this.weight.compareTo(o.weight);
}
}
赫夫曼树构建实现
/**
* 根据优先级列表创建赫夫曼二叉树：
* 根据前两个节点,构造子树，然后与后面的节点合并成新的子树,挂载节点原则:
* 1.从底至上构建，
* 2.权重大的挂载右边，反之左边
* 3.根节点的权重为左右权重的和
*
* @param priorityArr 元素权重递增的数组
* @return 赫夫曼根节点
*/
public static BinaryNode<HuffmanModel> createHuffmanTree(Integer[] priorityArr) {
Stack<BinaryNode<HuffmanModel>> stack = new Stack<>();//这里仅做暂存合并树节点的容器
BinaryNode<HuffmanModel> newRootNode = null;//新建节点，连接新节点和之前生成的子树
if (priorityArr == null || priorityArr.length == 0) {
return newRootNode;
}
int i = 0;
//两两合并节点，构建子树入栈
while (i < priorityArr.length) {
//循环体做合并节点
BinaryNode<HuffmanModel> newNode = new BinaryNode<>(new HuffmanModel(priorityArr[i]));//叶子节点
if (i == 0) {//第一个节点,无法构建子树,直接入栈
stack.push(newNode);
i++;
continue;
}
//每一次将上次构建的子树和新的节点合并成新子树入栈
BinaryNode<HuffmanModel> tempRootNode = new BinaryNode<>(new HuffmanModel(0));//挂载叶子节点的新的根节点
BinaryNode<HuffmanModel> currentSubTree = stack.pop();//目前已经合并的子树根节点
//判断权重，新节点和子树节点合并
if (newNode.data.weight > currentSubTree.data.weight) {
tempRootNode.left = currentSubTree;
tempRootNode.right = newNode;
} else {
tempRootNode.left = newNode;
tempRootNode.right = currentSubTree;
}
/**
* 更新权重,权重为节点左右
*/
if (tempRootNode.left != null) {
tempRootNode.data.weight += tempRootNode.left.data.weight;
}
if (tempRootNode.right != null) {
tempRootNode.data.weight += tempRootNode.right.data.weight;
}
stack.push(tempRootNode);
i++;
}
newRootNode = stack.pop();//最后取出合并完成的树
return newRootNode;
}
代码结合注释比较好理解，不在赘述。
赫夫曼树编码实现
从根节点到叶子节点的遍历，递归即可。
/**
* 赫夫曼编码
* 每一次递归都基于父节点的code
* @param node 赫夫曼树根节点
* @param codeTable 存放编码结果，key为赫夫曼编码，value为元素值
*/
public static void huffmanEncode(BinaryNode<HuffmanModel> node, HashMap<String, Integer> codeTable) {
if (node.isLeaf()) {//到叶子节点了，递归结束
codeTable.put(node.data.code, node.data.data);//赫夫曼数的编码数据都在叶子节点, 保存编码表
return;
}
/**
* 向左遍历
*/
if (node.left != null) {
StringBuilder sb = new StringBuilder();
sb.append(node.data.code).append("0");
node.left.data.code = sb.toString();//子节点编码
huffmanEncode(node.left, codeTable);
}
/**
* 向右遍历
*/
if (node.right != null) {
StringBuilder sb = new StringBuilder();
sb.append(node.data.code).append("1");
node.right.data.code = sb.toString();//子节点编码
huffmanEncode(node.right, codeTable);
}
}
赫夫曼解码
根据路径编码串找到叶子节点，然后返回节点数据即可。
/**
* 赫夫曼解码
*
* @param code
* @param node
* @return
*/
public static int huffmanDecode(BinaryNode<HuffmanModel> node, String code) {
if (code == null || code.length() == 0) {
return -1;
}
BinaryNode<HuffmanModel> p = node;
char[] chars = code.toCharArray();
for (int i = 0; i < chars.length; i++) {
int c = chars[i] - '0';
//遍历路径判断
if (p != null) {
if (c == 0) {
p = p.left;
} else if (c == 1) {
p = p.right;
}
} else {
return -1;//没有查到
}
}
if (p != null && p.isLeaf()) {//必须是叶子节点
return p.data.data;
}
return -1;
}
注意:遍历完成后，节点必须是叶子节点，因为中间层节点是不挂载元素的，只保存了权重。
测试代码
@Test
public void testHuffman() {
System.out.println("=====赫夫曼=====");
Integer[] huffmanArr = {1, 2, 3, 4, 5};//简单起见,权重=编码数据,升序排列
BinaryNode<HuffmanModel> huffmanTree = BinaryTree.createHuffmanTree(huffmanArr);
HashMap<String, Integer> huffmanEncodeTable = new HashMap<>();
//赫夫曼编码huffmanEncodeTable保存赫夫曼编码
BinaryTree.huffmanEncode(huffmanTree, huffmanEncodeTable);
System.out.println("=====赫夫曼编码输出=====");
Iterator<Map.Entry<String, Integer>> iterator = huffmanEncodeTable.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> next = iterator.next();
System.out.println(next.getKey() + "==" + next.getValue());
}
System.out.println("=====赫夫曼解码输出=====");
iterator = huffmanEncodeTable.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> next = iterator.next();
System.out.println(next.getKey() + "==" + BinaryTree.huffmanDecode(huffmanTree, next.getKey()));
}
}
}
完整代码地址:数据结构与算法学习JAVA描述GayHub地址
下一篇我们研究下二叉树另一重要分支:平衡二叉树。
