哈夫曼树小记

哈夫曼树，亦被称为最优二叉树，其特点在于具有最小的带权路径长度，常被用于构建高效的编码方式，在信息传输与数据压缩等多个领域中具有重要的应用价值。

0x00 相关概念

1、路径
树结构中，从某一节点至另一节点所经过的数值序列。
2、路径长度
构成路径的分支数量。
3、结点的权
为节点分配的具体数值。
4、带权路径长度
该节点所具有的权重与其在路径中的位置相乘所得的结果。
5、树的带权路径长度
整棵树中所有末端节点（即叶子结点）各自带权路径长度的总和，通常用WPL表示（仅统计叶子结点）。

如图中所示案例，尽管结点数量一致，但由于结构存在差异，所计算出的WPL值也会有所不同。

哈夫曼依据最优二叉树的核心特性：
权值越高，距离根节点越近 ，提出了构建方式，因此这种二叉树也被称作哈夫曼树。

6、最优二叉树