【离散数学】树（一）哈夫曼编码基本原理

本节我们将介绍以下内容：

给定 n 个叶子结点，每个结点带权值，构造一棵二叉树，如果带权路径长度最短，则称为哈夫曼树（最优二叉树），权值最大的结点最接近根结点

给定一组符号S及其权值W（出现的概率）

根据这张表格，我们来构造一棵哈夫曼树

哈夫曼压缩是一种能够大幅度压缩自然语言文件空间的数据压缩技术，不再使用8位二进制数表示每一个字符，而是用较少的比特表示出现频率高的字符，而用较多的比特表示出现频率低的字符

在我们构造出哈夫曼树后，将所有的权值删去，并给每条边赋值0或1
在此我们定义 左 0 右 1

据此，我们尝试解码一个短串：

011011111

从根结点开始，遇到 0 ，向左下移动一次，得到字符 A

开始解码下一个字符，从根结点开始，遇到2个 1 ，向右下移动2次，遇到 0 ，向左下移动一次，得到字符 C

开始解码下一个字符，从根结点开始，遇到5个 1 ，向右下移动5次，得到字符 E

所以我们解码得到的字符为 ACE

关于哈夫曼编码的基本原理就介绍到此了，谢谢大家！