在我们接近高科技的时代，离不开高效率的算法，比如：微信做的图片压缩技术、RAR、ZIP，就是利用哈夫曼树算法来处理。
1、首先理解几个概念
1.哈夫曼树概念：带权路径长度（WPL）最小的树称做为哈夫曼树。
2.路径长度：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支树目称做路径长度
看图：
1.png
2.png
3.png
2、哈夫曼树是如何构成的（集合必须是有序，每次相加之前都要进行排序，采用左小右大原则），先看一下步骤：
4.png
5.png
注意：每次把数字放上去之前，都要先排序，左小右大原则，然后在进行2组数字相加，得到父结点。
6.png
3、Huffman编码（集合必须是有序的）
哈夫曼研究这种最优的树目的是为了解决当年远距离通信（主要是电报）的数据传输的最优化问题。
比如：“BADCADFEED” 要网络传输给别人，显然用二进制的数字（0或1）来表示是很自然的想法，那我们用这六个字母ABCDEF二进制来表示
7.png
8.png
结点上的数字，表示代表出现的次数。比如：A 上的27，表示出现了27次，也就是路径出现27次。
4、代码实现哈夫曼树
import android.support.annotation.NonNull;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Stack;
/**
* author: bobo
* create time: 2018/12/14 9:34 PM
*/
public class HuffmanTree<T> {
TreeNode<T> root;
/**
* 构建哈夫曼树
*
* @param list
*/
public void createHuffmanTree(ArrayList<TreeNode<T>> list) {
if (list == null || list.isEmpty()) {
return;
}
while (list.size() > 1) {
Collections.sort(list);
TreeNode left = list.get(list.size() - 1);
TreeNode right = list.get(list.size() - 2);
TreeNode parent = new TreeNode("P", left.weight + right.weight);
parent.leftChild = left;
left.parent = parent;
parent.rightChild = right;
right.parent = parent;
list.remove(left);
list.remove(right);
list.add(parent);
}
root = list.get(0);
}
/**
* 一层一层取出数据，通过队列入队的方式存储形式
*
* @param root
*/
public void showHuffman(TreeNode root) {
LinkedList<TreeNode> list = new LinkedList<>();
//入队
list.offer(root);
while (!list.isEmpty()) {
//出对
TreeNode node = list.pop();
if (!node.data.equals("P")) { //如果是创建的结点P，就不打印了
System.out.println(node.weight + " = " + node.data);
}
//左子树不为空，则入队
if (node.leftChild != null) {
list.offer(node.leftChild);
}
//右子树不为空，则入队
if (node.rightChild != null) {
list.offer(node.rightChild);
}
}
}
/**
* 获取哈夫曼编码
*
* @param node
*/
public String getHuffmanCode(TreeNode node) {
TreeNode tNode = node;
//定义一个栈来排序用
Stack<String> stack = new Stack<>();
while (tNode != null && tNode.parent != null) {
//left 0 right 1
if (tNode.parent.leftChild == tNode) {
stack.push("0");
} else if (tNode.parent.rightChild == tNode) {
stack.push("1");
}
tNode = tNode.parent;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.toString();
}
/**
* 结点，和二叉树一样
*
* @param <T>
*/
public static class TreeNode<T> implements Comparable<TreeNode<T>> {
T data;
TreeNode<T> leftChild;
TreeNode<T> rightChild;
TreeNode<T> parent;
//权重
int weight;
public TreeNode(T data, int weight) {
this.data = data;
this.weight = weight;
this.leftChild = null;
this.rightChild = null;
this.parent = null;
}
@Override
public int compareTo(@NonNull TreeNode<T> o) {
if (this.weight > o.weight) {
return -1;
} else if (this.weight < o.weight) {
return 1;
}
return 0;
}
}
}
5、测试
@Test
public void testHuffmanTree(){
//添加结点数据
ArrayList<HuffmanTree.TreeNode> list = new ArrayList<>();
HuffmanTree.TreeNode<String> node = new HuffmanTree.TreeNode("good", 50);
list.add(node);
list.add(new HuffmanTree.TreeNode("morning", 10));
HuffmanTree.TreeNode<String> node2 =new HuffmanTree.TreeNode("afternoon", 20);
list.add(node2);
list.add(new HuffmanTree.TreeNode("hello", 110));
list.add(new HuffmanTree.TreeNode("hi", 200));
HuffmanTree tree = new HuffmanTree();
tree.createHuffmanTree(list);
tree.showHuffman(tree.root);
System.out.println("tree.getHuffmanCode(node); = " + tree.getHuffmanCode(node));
System.out.println("tree.getHuffmanCode(node2) = " + tree.getHuffmanCode(node2));;
}
6、测试结果
200 = hi
110 = hello
50 = good
10 = morning
20 = afternoon
tree.getHuffmanCode(node); = 001
tree.getHuffmanCode(node2) = 0001
7、结束
以上对Huffman树的理解。
