哈夫曼树:其实就是一个压缩算法，类似于最优解
例子：
有一次考试成绩分为4个等级：A、B、C、D，班级有100人，其中获得A的人数为20人，获得B为40人，获得C为10人，获得D为30人。问：输入所有人的成绩，获取每个人成绩对应的等级，如何使得判断次数最少？
伪代码：
for 100 to 0 //遍历100人get num //获得分数if A == num //分数属于Areturn Aelse if B == num //分数属于Breturn Belse if C == num //分数属于Creturn Celse if D == num //分数属于Dreturn D现在来看上面的代码，首先100人的分数是已知的，所以循环遍历100次，从广度来看，第一个判断A成立的次数是 20 次，所以分数为A的判断次数为 20 * 1，
而第二个B的判断，由于前面需要经过A是否成立的判断，所以分数为B的判断次数为 40 * 2，由此类推，第三个C的判断次数为10 * 3，第四个D的判断次数为30 *4。
一共为： 20 * 1 + 40 * 2 + 10 * 3 + 30 *4 = 250
现在我们优化下算法，把人数多的等级判断放在前面：
for 100 to 0 //遍历100人get num //获得分数if if B == num //分数属于Breturn Belse if D == num //分数属于Dreturn Delse A == num //分数属于Areturn Aelse if C == num //分数属于Creturn C第一个判断B成立的次数是 40 次，所以分数为B的判断次数为 40 * 1，
第二个D判断的次数为 30 * 2，第三个A判断的次数为20 * 3，第四个C判断的次数为10 *4。
一共为： 40 * 1 + 30 * 2 + 20 * 3 + 10 *4 = 200
结果很明显：第二种判断的次数少
哈夫曼树就是基于这个思想而来的，真正存放值的都为叶子节点(重要)，把出现次数几率越高的越靠近根节点，哈夫曼树主要是构建过程，他构建效率是比较低的。
节点多了权重，就是出现几率，我们对权重关心，对值并不关心
1.构建时，将数组按权重排序
2.每次从数组里取出前两个作为树的左孩子和右孩子，构建一个节点，节点的权重为两者之和
3.将节点的权重放入数组，重新按权重排序
4.循环第2步
当数组只剩一个元素，将它作为根节点
作用：二进制表示每个节点的值，所占空间最少
手写哈夫曼树：
/*** 哈夫曼*/static class HuffmanTree<T> {HuffmanNode<T> root;public void build(HuffmanNode<T>[] huffmanNodes) {if (huffmanNodes.length == 0) return;PriorityQueue<HuffmanNode<T>> priorityQueue = new PriorityQueue<>(new Comparator<HuffmanNode<T>>() {@Overridepublic int compare(HuffmanNode<T> o1, HuffmanNode<T> o2) {return o1.weight - o2.weight;}});for (HuffmanNode<T> huffmanNode : huffmanNodes) {priorityQueue.offer(huffmanNode);}while (priorityQueue.size() > 1) {//取出前两个元素HuffmanNode<T> top = priorityQueue.poll();HuffmanNode<T> second = priorityQueue.poll();//合成一个节点priorityQueue.offer(new HuffmanNode<T>(null, top.weight + second.weight, top, second));}root = priorityQueue.poll();}//节点static class HuffmanNode<T> {T value;//权重int weight;//左孩子HuffmanNode<T> leftChild;//右孩子HuffmanNode<T> rightChild;public HuffmanNode(T value, int weight) {this.value = value;this.weight = weight;}public HuffmanNode(T value, int weight, HuffmanNode<T> leftChild, HuffmanNode<T> rightChild) {this.value = value;this.weight = weight;this.leftChild = leftChild;this.rightChild = rightChild;}}}测试代码：
public static void main(String args[]) {HuffmanTree<String> huffmanTree = new HuffmanTree();HuffmanTree.HuffmanNode<String>[] nodes = new HuffmanTree.HuffmanNode[]{new HuffmanTree.HuffmanNode<String>("a", 20),new HuffmanTree.HuffmanNode<String>("b", 40),new HuffmanTree.HuffmanNode<String>("c", 10),new HuffmanTree.HuffmanNode<String>("d", 30),};huffmanTree.build(nodes);dfs(huffmanTree);}private void dfs(HuffmanTree<String> huffmanTree) {Deque<HuffmanTree.HuffmanNode> deque = new LinkedList<>();if (huffmanTree.root != null) {deque.offer(huffmanTree.root);}while (!deque.isEmpty()) {int size = deque.size();while (size > 0) {HuffmanTree.HuffmanNode node = deque.poll();System.out.print(node.value + " (" + node.weight + ") ");if (node.leftChild != null) {deque.offer(node.leftChild);}if (node.rightChild != null) {deque.offer(node.rightChild);}size--;}System.out.println();}}结果：
null(100) b(40) null(60) d(30) null(30) c(10) a(20)这样对于一个含有20个a，40个b，10个c，30个d的字符串，所用的二进制bit最少
如果左树为0，右数为1
其中
a的二进制表示为：111
b的二进制：0
d的二进制：10
c的二进制：110
所占位数为：3 * 20 + 1 * 40 + 2 * 10 + 3 * 30 = 210