近期忙着新版本的开发，此外正在回顾C语言，大部分时间没放在数据结构与算法的整理上，所以更新有点慢了，不过既然写了就肯定尽力将这部分完全整理好分享出来。
言归正传，开启本篇的正文。
一、什么是赫夫曼树
给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
以上来自百度百科，相信完全不了解的同学看完肯定一头雾水，啥玩意，这么多术语，权值？树的带权路径长度？都是什么鬼？别急，下面一一解释。
二、赫夫曼树中术语解释
路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径。
结点路径长度：一个结点到另一个结点之间路径上分枝数目称作路径长度。
比如上图中根结点到A结点路径长度为3
树的路径长度：从树根结点到每一结点的路径长度之和称作树的路径长度之和。这里是每一结点，而不仅仅是叶子结点。
比如上图树的路径长度为：1+1+2+2+2+2+3+3 = 16
结点权值：将树中的结点赋予一个有意义的数，称为该结点的权值。
结点的带权路径长度：从该结点到树根之间的路径长度与该结点权值的乘机叫做结点的带权路径长度。
比如上图中A结点带权路径长度为：3 * 5 = 15
树的带权路径长度：树中所有叶子结点的带权路径长度之和叫作树的带权路径长度。
上图树的带权路径长度为：3*5+15*3+40*2+30*2+10*2=220
树的带权路径长度可计作WPL，赫夫曼树就是WPL最小的的二叉树。
三、赫夫曼树的创建
了解了基本的概念之后我们继续看下赫夫曼树到底怎么创建呢？以下就直接说创建流程了。
比如我们有以下几个结点信息：A5(A代表结点名字，5代表其权值)，B15，C40，D30，E10。
构造赫夫曼树流程如下：
（1）先把有权值的叶子结点从小到大排序成一个有序序列：A5，E10，B15，D30，C40。
（2）取头两个最小权值的结点作为新结点M1的两个子结点，其中权值小的结点在左侧，权值大的在右侧。即A5为M1的左孩子，E10为M1的右孩子，M1结点权值为两个子结点权值的和15，即M15，如图：
（3）新结点M15替换A5与E10结点，插入有序序列中，依然保持从小到大排序：M15，B15，D30，C40。
（4）重复步骤(2)，将M15与B15作为新结点P的左右孩子，P的权值为30，如图：
（5） P30替换M15，B15插入有序序列中依然保持从小到大顺序：P30，D30，C40。
（6）重复步骤（2），将P30，D30作为新结点T的左右孩子，T结点权值为60，如图：
（7）T60替换P30，D30插入有序序列，依然保持从小到达排序：C40，T60。
（8）重复步骤（2），C40，T60作为新结点N的左右孩子，N权值为100，N即为根结点，完成赫夫曼树的构建，如图：
到此，赫夫曼树就已经构建完成，其WPL为：WPL=40*1+30*2+15*3+5*4+10*4=205
整个构建过程核心思想就是让权值小的结点距离根结点远，权值大的距离根结点近一些。
四、赫夫曼编码
赫夫曼老爷子研究最优树可不是仅仅为了构建就完事了，肯定有其用处的，赫夫曼树就是为了解决当年远距离通信的数据最优化问题。