二叉树的一种特殊的数是霍夫曼树：霍夫曼树是基于权重的。比如数组T，和权重W（或者概率W）
T[a,d,g,b,y,h]
W[1,3,5,4,7,9]
权重和字符是对应的，怎么构建霍夫曼树呢。最终构建一个二叉树让所有路径相加权值最小，具体原理自己去推证吧。下面说方法

霍夫曼树

1. 第一步：从W中选择两个最小的权重，1和3,相加成4

   
   1.JPG

2. 然后由4和剩下的元素组成数组
   [4,5,4,7,9]

3. 从中选择两个最小的进行第一步,相加成8

   
   2.JPG

4. 由8和剩下的三个元素组成数组
   [8,5,7,9]
   循环，循环吧

5. 最终结果如下

   
   3.JPG

霍夫曼编码

上面的霍夫曼树，如果把左边分支设置为0，右边分支设置为1，从顶部到底部得到的01编码就是对应字符的霍夫曼编码

a:0000
d:0001
b:001
h:01
g:10
y:11
这里最重要的是：任何一个编码不是另一个编码的前缀，也就是说收到的报文只要匹配上编码就是这个字符，不用考虑还是其他字符的问题，霍夫曼编码应用在文档或者报文压缩里面。