哈夫曼树与哈夫曼编码

哈夫曼树：结点中赋予一个某种意义的值，称为结点的权值，从根结点开始，到目标结点经过的边数，称为路径长度，路径长度乘以权值，称为带权路径长度；

例如：根结点代表着快递集散点，一个叶子结点权值是5，在业务逻辑中代表着重量是5斤的货物📦，路径长度是3，业务逻辑代表着3公里，3 * 5 = 15 假设代表着从根结点开始配送这一件货物的成本 开销是15升汽油

越重的物品，配送距离越长，开销越大，假设说每一层结点都有一个快递柜，只可以存放一件物品，这样就让收件人自己来取，而不用大老远送过去了，那么我们就应该优先把最重的物品，放在距离快递集散点（根结点）越近的位置。重量轻的（权值小的）小件物品我们可以送远一点。
那么这个想法其实就是最短带权路径

例：假设快递站今天收到了6件需要派送的物品，重量（斤）分别是 6，9，1，3，2，12
如果快递员不懂巧妙利用最短带权路径，而是经过一个快递柜就按顺序把一件放进柜子，剩下的继续配送，那么构成的树就会是：

可以看到总耗费汽油109升。

但是转念一想，既然都可以放菜鸟柜，我为什么不把重的提前放下车，省点汽油呢？于是第二天快递员就改变思路，形成下面的二叉树：

果然，第二天只消耗了75升汽油，成本大大节约了

总结：综上所述，使得带权路径WPL最小的树，就称之为哈夫曼树。也可以称之为：最优二叉树

例子：

牢记哈夫曼树只有叶子结点能存放字符；同时哈夫曼树仅有度为0或者度为2的结点（因为是两两组合，不存在度为1）

（1）一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（108）个不同的码字
因为哈夫曼树只有叶子结点能存放码字
根据二叉树的性质，最后一个非叶结点是：215 / 2 向下取整 = 107
所以叶子结点就是：215 - 107 = 108
所以，能存放108个不同的码字

（2