当前课程知识点：数据结构 > 第5章 树和二叉树 > 5.7 Huffman树 > 讲解（下）
学习了哈夫曼树之后
我们来看哈夫曼树的应用，第一个应用，哈夫曼编码
假设，给定了一个字符集
这个字符集当中
每一种字符出现的概率，也给你了
我们现在为这个字符集当中的每一种字符设计编码
这个就叫做哈夫曼编码问题
我们可以把给定的每一个字符，当作刚才讲的叶结点
而每种字符出现的概率
当做叶结点的权值
我们设计编码的一个初衷，是让将来使用这种字符集的文本
它的编码总长度，要尽可能的短
怎么保证短呢
应该让那些出现概率比较高的字符
它的编码要短一些
反之，出现概率比较低的
它的编码可以长一些
比如
英文这种字符集，元音字母
它出现的概率比较高
我们可以让它短一点
比如编码成0
而很少出现的字符
比如q
它出现的概率比较低
我们可以让它稍微长一点
这样就保证
文本的总的编码长度会短一些
这样一种编码，实际上就叫变长编码
你会发现，每一种字符
它的编码长度不一样
与变长编码相对应的，就是等长编码
现在很多字符集，它们的编码标准都是等长的
比如，最常见的ASCII码
它就是8位的
不管是a也好
还是q也好
它们的编码长度，都是8位的
还有
我们国家的GB2312或者GBK
它是一个16位的编码
还有，多语言支持地最好的Unicode编码
它也是一个16位的编码
这些都是等长的编码
比较好翻译回来
按照固定长度切分，就可以了
现在，我们不考虑定长编码(等长编码)
我们考虑变长编码
设计了一套变长编码
还有一个前提是，解码的时候没有歧义
也就是说
任何一个编码，都不是其他编码的前缀
只有满足这个特性
也就是满足前缀编码的特性
才能进行解码
这里想专门说明一下的是
满足这个条件的，也就是任何一个编码都不是其他编码的前缀
才叫做前缀编码
这个希望大家注意
比如，我们现在设计的变长编码是
0、10、和010
它们代表3种字符的编码
现在，我们接收到的
编码串，假设是0010
解码的时候，就会有歧义
它有多种解释
可以0，一划分
然后，这个0，再一划分
然后，后面的10，再一划分
它们都有对应的编码
也可以
0，一划分
然后，010
毕竟，这个编码它也是存在的
所以这时候，接收到的编码，在解码的时候是有歧义的
为什么会出现这种情况呢
这是因为，我们设计的这个变长编码
它不满足前缀编码的要求
特别是这个编码
你会发现，它是这个编码的前缀
也就是说
010是以0开头的
为了防止这种问题出现
我们必须在设计变长编码的同时，要满足前缀编码特性
很简单
我们利用二叉树，就可以了
现在，我们将哈夫曼树当中的左、右分支
分别编码成0和1
当然
左分支编码成1，也是可以的
现在，从根结点走到叶结点
我们将路径中各分支的0、1连接起来
就会变成一套前缀编码
比如5
这个叶结点
它的编码就是，从根走到5，会经历两条边，连起来是01
而3，它的编码是101
为什么设计的这一套编码
它一定是前缀编码呢
很简单
我们可以用反证法
假设某一个编码
它是以另一个编码为前缀的
比如
这里的4个X
假设是某一个字符
它的编码
而另外一个字符的编码是它
你要知道，a和b
它们是出现在叶结点的位置的
意味着，从根结点走到b会经历a
从根结点走到一个结点
会经历另外一个结点
这个结点就是b，这个结点是a
a是叶结点
它怎么可能到另外一个叶结点呢，叶结点是没有孩子的
所以，与我们假设是冲突的
我们将树的左、右分支，分别编码成0、1
最后，是不会出现这种前缀的情况
也就是说，设计出来的编码，一定是满足前缀编码的要求的
哈夫曼树的第二个应用，是用来判定优化
假设，我们现在统计某门课程各分数段的人数
或者说，统计一段英文当中，各字符出现的次数
我们应该尽量使条件的总的判断次数，要少一些
也就是说
可能性比较高的判定条件
应该写在前面
因为，我们将算法写成程序
程序总体上，还是从上往下执行的
那些出现概率比较高的判定条件
应该先比较、先判断
如果我们用switch语句来实现
要注意各个case子句的编写顺序
实际上
我们在学习C语言或者Java的时候，也讲过类似的东西
我们应该让
那些
出现概率比较高的case子句，把它们写在前面
比如这两个程序段，它们的不同在于，对分数段的判断不同
我们直接把分数整除一个10，以减少
case子句的个数，左边
我们先判断10，再判断9，我们是按照递减的顺序判断的
而一场正常的考试
出现在70多分、60多分，或者80多分
它们的概率是比较高的
我们先判断7、再判断6
再判断8
不像刚才那样
因为，考满分和90多分的比较少
我们将这些case子句往后放
这样使得若干个成绩，执行这个for循环的时候
总的比较次数要少一些
这就是判定优化
本章的内容，就到此结束
下一章，我们将进入图的学习
同学们，加油！
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
