Tree

哈夫曼树

1. 定义
   在含有 n 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树成为 哈夫曼树 ，也称 最优二叉树 。
2. 带权路径长度 WPL
   树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为：
   $$WPL = \sum_{i=1}^{n} w_i l_i$$
3. 哈夫曼树的构造
   哈夫曼树中不存在度为 1 的结点
4. 哈夫曼编码 最短二进制前缀编码（前缀编码：没有一个是另一个编码前缀）
   叶结点的权值代表出现的次数，字符编码解释为从根结点至该字符路径上的标记序列
   一般边标记为 0 转向左孩子，标记为 1 转向右孩子
   WPL 可视为最终编码得到二进制编码的长度