赫夫曼编码可以构造出一种不等长的二进制，使编码后的电文长度最短，且保证不产生二义性
赫夫曼树
相关定义
权：树结点间的连线相关的数
结点的路径长度：从根结点到该结点的路径上的连接数
树的路径长度：树中每个叶子结点的路径长度之和
结点带权路径长度：结点的路径长度与结点权值的乘积
树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和。 WPL越小,说明二叉树性能越优。
构造赫夫曼树
1.在森林中选出两颗根结点的权值最小的二叉树，权值小的放左边，权值大的放右边
2.合并两颗选出的二叉树：增加一个新结点n作为新二叉树的根，权值为左右孩子权值之和
3.回到森林中，选出权值最小的根结点，与刚刚形成的结点n比较，小的放左边，大的放右边
4.返回步骤二，直到森林中的树被选完
赫夫曼编码
一些名词
定长编码：规定位数表示字符
变长编码：单个编码长度不一字，可以根据整体出现频率来调节
前缀码：没有任何码字是其他码字的前缀
赫夫曼编码思路
1.根据输入字符串，统计字符出现次数，建立优先级队列
2.根据优先级队列建立输入字符串的赫夫曼树
3.遍历赫夫曼树，左1右0，建立字符编码表
4.编码encode:根据字符编码形成字符串编码
5.解码decode：根据编码字符串遍历赫夫曼树，左0右1，找到叶子结点的字符，从而解码字符。
代码链接