【数据结构】哈曼夫树与哈夫曼编码

哈曼夫树与哈夫曼编码

导读

大家好，很高兴又和大家见面啦！！！

在上一篇内容中我们介绍了树与森林的遍历，并且我们还通过C语言实现了树与森林的遍历。

树与森林的内容就要告一段落了，接下来我们将进入树与二叉树的最后一部分内容——树与二叉树的应用。

在今天的内容中，我们将会学习第一种应用——哈夫曼树与哈夫曼编码。下面我们就进入今天的内容吧！！！

一、哈夫曼树

1.1 相关概念

结点的权：当树中结点被赋予一个表示某种意义的数值时，这个数值就是该结点的权；

带权路径长度：从树的根到一个结点的路径长度与该结点上权值的乘积称为该结点的带权路径长度；

树的带权路径长度：树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为：

其中 ：

【数据结构】哈曼夫树与哈夫曼编码_权值_07

1.2 哈夫曼树的构造

从树的带权路径长度的公式我们不难发现，影响树的带权路径长度的因素就两个——结点的权值，结点的路径长度；

因此当我们要构造一棵哈夫曼树时，其核心逻辑就是：

• 权值小的路径长，权值大的路径短

那我们如何通过这个逻辑来构造一颗哈夫曼树呢？具体的步骤如下所示：

• 将n个结点分别作为n棵仅含一个结点的二叉树，构成森林F；
• 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将权值置为左、右子树上根结点的权值之和；
• 从F中删除刚才选出的两棵树，同时将新得到的树加入F中；
• 重复步骤2 和步骤3，直至F中仅剩一棵树为止；

下面我们就以上图所示的四个结点A/B/C/D为例，来构造一颗哈夫曼树：

【数据结构】哈曼夫树与哈夫曼编码_权值_09

根据哈夫曼树的构造步骤，可以看到对于结点A/B/C/D而言，其能构造的哈夫曼树正是前面的图片中例举的树1。

1.3 哈夫曼树的性质

从上述构造的过程中，我们不难看出，在由n个结点构成的哈夫曼树具有以下特点：

1. 树中最初的结点都为叶结点；
2. 权值越小的结点到根结点的路径长度越大；
3. 哈夫曼树的结点总数为 2n - 1；
4. 哈夫曼树中不存在度为1的结点

可能还有朋友不太理解这四点，下面我就来简单的解释一下；

在哈曼夫树的特点中，前两点实际上说的就是树的带权路径长度的公式中的两个影响因素——权值与结点路径长度。

根据二叉树的性质：

二、哈夫曼编码

2.1 相关概念

固定长度编码：在数据通信中，若每个字符用相等长度的二进制位表示，这种编码方式称为固定长度编码。

可变长度编码：若对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。

前缀编码：若没有一个编码是另一个编码的前缀，则称为这样的编码为前缀编码。

哈夫曼编码：由哈夫曼树获取的编码就是哈夫曼编码，这是一种非常有效的数据压缩编码。

2.2 概念理解

要理解上述的这些概念，首先我们需要理解什么是编码。

简单的理解，编码就是通过二进制位这种数码的形式来表示一些文字、数字等数据。

再具体一点，那就是通过二进制位来表示A/B/C/D这四个字符，用来表示这些字符的二进制数码就是这些字符的编码。

要表示这些字符，我们可以采用下述的几种编码方式：

2.2.1 固定长度编码

• 通过2个二进制位进行编码：

A —— 00
B —— 01
C —— 10
D —— 11

像这种以同等长度的二进制位进行编码的方式就是固定长度编码。

在这种编码方式下，二进制的位数就决定了我们能够表示的字符个数。

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这四个字符进行编码，如下所示：

【数据结构】哈曼夫树与哈夫曼编码_结点_19

当我们规定哈夫曼树的左子树为0，右子树为1时，我们得到的哈夫曼编码则是：

A —— 00
B —— 01
C —— 10
D —— 11

同理，当我们将左子树规定为1，右子树规定为0时，则对应的哈夫曼编码为：

A —— 11
B —— 10
C —— 01
D —— 00

结语

在今天的内容中我们介绍了哈夫曼树与哈夫曼编码的相关知识点。通过今天的内容，我们学习了一些基本概念：

• 结点的权值——结点被赋予的一个表示某种意义的数值；
• 带权路径长度——从树的根结点到一个结点的路径长度与该结点上权值的乘积
• 树的带权路径长度——树中所有叶结点的带权路径长度之和；
• 哈夫曼树——树的带权路径长度最小的二叉树
• 固定长度编码——对每个字符用长度相等的二进制位表示的编码方式
• 可变长度编码——对不同字符用不等长的二进制为表示的编码方式
• 前缀编码——没有一个编码是另一个编码的前缀的编码方式
• 哈夫曼编码——由哈夫曼树获得的编码

今天的内容到这里就全部结束了，在下一篇内容中我们将介绍《并查集》，大家记得关注哦！

如果大家喜欢博主的内容，可以点赞、收藏加评论支持一下博主，当然也可以将博主的内容转发给你身边需要的朋友。最后感谢各位朋友的支持，咱们下一篇再见！！！