【数据结构】哈曼夫树与哈夫曼编码
【数据结构】哈曼夫树与哈夫曼编码
哈曼夫树与哈夫曼编码
导读
在上一篇内容中我们介绍了树与森林的遍历，并且我们还通过C语言实现了树与森林的遍历。
树与森林的内容就要告一段落了，接下来我们将进入树与二叉树的最后一部分内容——树与二叉树的应用。
在今天的内容中，我们将会学习第一种应用——哈夫曼树与哈夫曼编码。下面我们就进入今天的内容吧！！！
一、哈夫曼树
1.1 相关概念
结点的权：当树中结点被赋予一个表示某种意义的数值时，这个数值就是该结点的权；
带权路径长度：从树的根到一个结点的路径长度与该结点上权值的乘积称为该结点的带权路径长度；
树的带权路径长度：树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为：
其中 ：
为第i个叶结点的权值
是从根结点到第i个叶结点的路径长度
是第i个叶结点的带权路径长度
哈夫曼树：在含有n个带权叶结点的二叉树中，其中带权路径长度（
）最小的二叉树称为哈夫曼树，也称最优二叉树。
上图所示的三棵二叉树中，通过计算，我们发现树1的
的值是最小的，并且它刚好就是一棵哈夫曼树。
我们如何来验证这个结论呢？下面我们就来看一下如何通过带权结点构造一棵哈夫曼树；
1.2 哈夫曼树的构造
从树的带权路径长度的公式我们不难发现，影响树的带权路径长度的因素就两个——结点的权值，结点的路径长度；
因此当我们要构造一棵哈夫曼树时，其核心逻辑就是：
- 权值小的路径长，权值大的路径短
那我们如何通过这个逻辑来构造一颗哈夫曼树呢？具体的步骤如下所示：
将n个结点分别作为n棵仅含一个结点的二叉树，构成森林F；
构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将权值置为左、右子树上根结点的权值之和；
从F中删除刚才选出的两棵树，同时将新得到的树加入F中；
重复步骤2 和步骤3，直至F中仅剩一棵树为止；
下面我们就以上图所示的四个结点
A/B/C/D
为例，来构造一颗哈夫曼树：
根据哈夫曼树的构造步骤，可以看到对于结点A/B/C/D而言，其能构造的哈夫曼树正是前面的图片中例举的树1。
1.3 哈夫曼树的性质
从上述构造的过程中，我们不难看出，在由n个结点构成的哈夫曼树具有以下特点：
树中最初的结点都为叶结点；
权值越小的结点到根结点的路径长度越大；
哈夫曼树的结点总数为
2n - 1
；
- 哈夫曼树中不存在度为1的结点
可能还有朋友不太理解这四点，下面我就来简单的解释一下；
在哈曼夫树的特点中，前两点实际上说的就是树的带权路径长度的公式中的两个影响因素——权值与结点路径长度。
当我们要使
最小时，就会有以下几种情况：
结点的权值较大，此时需要通过减少结点的路径长度来达到降低结点的带权路径长度；
结点的路径长度越长，此时需要通过减少结点的权值来达到降低结点的带权路径长度；
当然，如果结点的权值越小，路径同时越短，那么其对应的
越小。
根据二叉树的性质：
- 二叉树中叶结点的数量
比度为2的结点
多1，即
对于
n
个叶结点的二叉树有
n-1
个度为2的结点，并且我们在构造的过程中每次都选择两棵树作为新结点的孩子，共新建了
n - 1
个结点，因此在哈夫曼树中不存在度为1的结点。
在二叉树中，结点的总数为为所有结点的总和，即：
在哈夫曼树中，叶结点的个数为n，度为1的结点个数为0，度为2的结点个数为
。因此哈夫曼树的结点总数为：$$n + 0 + n - 1 = 2n - 1$$
在了解了哈夫曼树之后，下面我们就来看一下由哈夫曼树得到的哈夫曼编码；
二、哈夫曼编码
2.1 相关概念
固定长度编码：在数据通信中，若每个字符用相等长度的二进制位表示，这种编码方式称为固定长度编码。
可变长度编码：若对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。
前缀编码：若没有一个编码是另一个编码的前缀，则称为这样的编码为前缀编码。
哈夫曼编码：由哈夫曼树获取的编码就是哈夫曼编码，这是一种非常有效的数据压缩编码。
2.2 概念理解
要理解上述的这些概念，首先我们需要理解什么是编码。
简单的理解，编码就是通过二进制位这种数码的形式来表示一些文字、数字等数据。
再具体一点，那就是通过二进制位来表示A/B/C/D这四个字符，用来表示这些字符的二进制数码就是这些字符的编码。
要表示这些字符，我们可以采用下述的几种编码方式：
2.2.1 固定长度编码
- 通过2个二进制位进行编码：
A —— 00
B —— 01
C —— 10
D —— 11
像这种以同等长度的二进制位进行编码的方式就是固定长度编码。
在这种编码方式下，二进制的位数就决定了我们能够表示的字符个数。
比如这里的2个二进制位，它最多只能够表示4个字符，因为一个二进制位能且只能表示两个字符，多一个二进制位，能表示的字符就能翻一倍。有
个二进制位，就能表示
个字符。
2.2.2 可变长度编码
- 使用不同长度的二进制位进行编码：
A —— 0
B —— 10
C —— 101
D —— 1011
像这种采用不等长的二进制位的编码方式就是可变长度编码。
这种方式的好处就是编码时能够更加灵活的处理每个字符。比如将使用频率高的字符用较短的二进制位进行编码，将使用频率低的字符，用较长的二进制位进行编码，这样就能够使编码的平均长度减短，起到压缩数据的效果。
2.2.3 前缀编码
在上文展示的固定长度编码中，我们不难发现，A/B/C/D这四个字符的编码：
A —— 00
B —— 01
C —— 10
D —— 11
没有一种编码是另一种编码的前缀，因此这种编码就是前缀编码。
这种编码的好处就是在进行解码时，不会出现错误解码。但是，在上文展示的可变长度编码中，我们可以看到，字符B的编码
10
是字符C的编码
101
与字符D的编码
1011
的前缀；字符C的编码
101
是字符D的编码
1011
的前缀。
这也就是说，如果我们要给
CDAB
这组字符进行编码，此时我们会得到其编码为：
10110110101
在这种情况下如果我们进行解码的话，那我们就可以将其翻译为以下字符：
101 1011 0 101 —— C D A B
101 101 10 101 —— C C B C
这时我们就无法进行唯一翻译，像这种编码显然就不是一个合理的编码。
因此，如果采用前缀编码的方式，可以确保解码时的唯一性。
2.2.4 哈夫曼编码
哈夫曼编码是从哈夫曼树中获取的编码，就比如上文所示的哈夫曼树中，我们要给
A/B/C/D
这四个字符进行编码，如下所示：
当我们规定哈夫曼树的左子树为0，右子树为1时，我们得到的哈夫曼编码则是：
A —— 00
B —— 01
C —— 10
D —— 11
同理，当我们将左子树规定为1，右子树规定为0时，则对应的哈夫曼编码为：
A —— 11
B —— 10
C —— 01
D —— 00
可以看到，在哈夫曼编码中，可能编码的方式并不唯一。接下来我们就来看一下如何获取字符的哈夫曼编码；
2.3 哈夫曼编码的获取
将每一个字符当做一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。
比如在一组字符中，A出现了45次，B出现了23次，C出现了12次，D出现了18次，E出现了5次，F出现了8次，由这些字符及其出现频率作为权值构造的哈夫曼树如下所示：
我们规定哈夫曼树的左子树为0，右子树为1，则对应的哈夫曼编码为：
A —— 1
B —— 000
C —— 011
D —— 001
E —— 0100
F —— 0101
该哈夫曼树的
即为该二进制编码的长度，即：
通过计算可知，通过哈夫曼编码的长度为256；
这里有6个字符，如果我们采用固定长度编码，至少需要3位二进制位，而对应的编码长度为
；
通过二者的长度对比，我们不难发现，哈夫曼编码大大压缩了编码长度。
2.4 哈夫曼编码的特性
从上述的介绍中，我们可以总结出哈夫曼编码的几点特性：
哈夫曼编码是一种非常有效的数据压缩编码
哈夫曼编码一定是前缀编码
哈夫曼编码不是唯一的
下面我们就一起来理解一下这些特性；
2.4.1 哈夫曼编码的数据压缩
在前面的列子中我可以看到，当我们对A/B/C/D/E/F这五个字符进行编码时，按照固定长度编码的方式进行编码时，我们最少需要3个二进制位，从前面的计算中我们可以得到，总编码长度为333；
而通过哈夫曼树获取的哈夫曼编码，其编码长度为256，总共压缩了约25%的长度；
因此哈夫曼编码可以非常有效的实现数据压缩
2.4.2 哈夫曼编码一定是前缀编码
从上述的两个例子我们不难发现，根据数据构造的哈夫曼树的不同，其编码也会有所不同，所以哈夫曼编码可能是固定长度编码，也可能是可变长度编码，具体的形式需要根据构造的哈夫曼树决定。
但是哈夫曼编码一定是前缀编码，这是因为在哈夫曼树中，进行编码的字符一定是叶结点，并且叶结点的路径一定不会是其它叶结点的路径重合。
在二叉树中，会与叶节点出现路径重合的结点一定是分支结点，因此哈夫曼编码一定是前缀编码；
2.4.3 哈夫曼编码不唯一
当我们通过结点构建哈夫曼树时，即使是同样的结点，我们也可能构建出不同的哈夫曼树：
- 结点所在的左右子树不同：
- 对于一棵二叉树而言，其叶结点也有左右子树之分，同一个结点位于不同的子树时，其哈夫曼编码也会有所不同；
- 存在权值相同的结点
- 当我们在构造哈夫曼树时，如果出现两个结点的权值相同时，我们就会因为选择的不同而构造出不同的哈夫曼树
这里我们以下图中的例子进行说明：
图中所示的五个结点中，存在两个权值相同的结点，此时按时图示的哈夫曼树进行获取哈夫曼编码，就会出现两种情况，
根据左右子树的不同，又会存在其它的编码，图中我们例举了8种编码，分别对应8棵哈夫曼树；
结语
在今天的内容中我们介绍了哈夫曼树与哈夫曼编码的相关知识点。通过今天的内容，我们学习了一些基本概念：
结点的权值——结点被赋予的一个表示某种意义的数值；
带权路径长度——从树的根结点到一个结点的路径长度与该结点上权值的乘积
树的带权路径长度——树中所有叶结点的带权路径长度之和；
哈夫曼树——树的带权路径长度最小的二叉树
固定长度编码——对每个字符用长度相等的二进制位表示的编码方式
可变长度编码——对不同字符用不等长的二进制为表示的编码方式
前缀编码——没有一个编码是另一个编码的前缀的编码方式
哈夫曼编码——由哈夫曼树获得的编码
对于该篇的内容，我们要重点掌握哈夫曼树的构建，能够手动的通过结点构建一棵哈夫曼树。
今天的内容到这里就全部结束了，在下一篇内容中我们将介绍《并查集》，大家记得关注哦！
如果大家喜欢博主的内容，可以点赞、收藏加评论支持一下博主，当然也可以将博主的内容转发给你身边需要的朋友。最后感谢各位朋友的支持，咱们下一篇再见！！！