版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: 笔记 - Huffman 树与 Huffman 编码 categories:
Huffman 编码是一种基于 Huffman 树的, 按字符概率构造的, 能保证编码平均长度最短的编码方式
<!-- more -->{% note warning %} https://cplib.tifa-233.com/src/code/util/huffman_tree.hpp 存放了笔者对该算法/数据结构的最新实现, 建议前往此处查看相关代码 {% endnote %}
Huffman 树即为根结点到所有叶子结点的带权路径长度之和最小的树
对于一棵 $k$ 叉的 Huffman 树, 我们首先要确保 结点个数 $n$ 满足 $(k-1)\mid(n-1)$, 否则我们可以补充若干个权值为 $0$ 的结点使其成立
首先按结点的权值排序, 然后取出 $k$ 个权值最小的结点合并为一个新结点并插入该序列, 新结点的权值为这 $k$ 个点权值之和, 直到序列中只剩下 $1$ 个结点为止
Huffman 编码通过对 Huffman 树进行层序遍历得到