数据机构-哈夫曼树

什么是哈夫曼树？

先来看哈夫曼树的定义：
哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。

看到这个定义我是一脸懵逼的，什么叶子节点和权重还好，那么路径是指什么呢，一个节点到另一个节点之间的途径？而且带权路径长度又是指什么呢？

什么是路径？

在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。

上面的二叉树当中，从根结点A到叶子结点H的路径，就是A，B，D，H。
所以路径长度就是3，也就是A=>B=>D=>H。

什么是结点的带权路径长度？

结点的带权路径长度是指：该结点权重的乘积 * 树的根结点到该结点的路径长度。
也就是 1x3=3。

那么树的带权路径长度就是：所有叶子结点的带权路径长度之和
也就是 1x3+2x3+3x2+4x2+5x2=33

哈夫曼树的构造

假设有5个叶子结点，权重依次是1,2,3,4,5，如何构建一颗哈夫曼树，也就是带权路径长度最小的树呢？

伪代码实现：
看到上面所说的每次把权值最小的两个节点合并，是不是瞬间就想到了最小堆呢，我们把权值存放在最小堆里，每次取根节点就可以了。这里直接放截图

哈夫曼编码其实就是哈夫曼树的一种应用
他是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合