笔试中经常遇到的哈夫曼树

哈夫曼树学习

前面学习过一些二叉树的知识,但是对于哈夫曼树的学习似乎被我忽略了.但是在最近的学习当中我又遇到了相关的问题,所以我查找资料并复习了一些哈夫曼树的知识.

首先我们来看一下哈夫曼树的构建

给定一组字符和其出现的频率(权值),我们来创建一颗哈夫曼树

字符	A	B	C	D	E
出现频次	1	3	8	6	2

• 构建步骤
• 1.以权值作为根结点构建n颗二叉树,组成森林
• 2.在森林中选出2个根结点最小的树合并,作为一颗新树的左右子树,且新树的根结点为其左右子树根结点之和
• 3.从森林中删除刚才选取的2棵树,并将新树加入森林
• 4.重复2、3步骤,直到森林只剩一颗树为止,该树即为哈夫曼树.

最初的森林,都是一样高的树

找到权值最小的两个,构建一颗全新的树

将构建的带权树放进森林(他就变成了最亮的仔)

继续寻找两个权值最小的建树

将建好的树继续放到森林里

继续寻找权值最小的两棵树构建一个新树

将建好的树放到森林中,并删除已经加入到新树建设中的树

继续选择权值最小的两棵树新建树

可以看到最终我们将整个森林构建成了一颗树(哈夫曼树),而所有的带权字符都在哈夫曼树的叶子结点

构建哈夫曼编码

首先来了解一下前缀编码
如果在一个编码系统中,任一编码都不是其他编码的前缀(最左子串),则称改编码系统中的编码是前缀编码,

举个栗子来说

有一组编码01,001,010,100,110就不是前缀编码,因为01是010的前缀,若去掉01或者010就是前缀编码.

若是前缀编码,则在电文中各字符对应的编码之间不需要分割符,如果不是前缀编码,则必须使用分隔符,否则会生产二义性.

• 哈夫曼编码是前缀编码
• 哈夫曼编码是最优前缀编码

那么如何根据所建立的哈夫曼树来编写哈夫曼编码的呢?

首先我们需要知道我们该如何进行编码呢?以什么方式进行编码呢？

对于这个问题,在这里规定了编码方式。既对树中的每个左分支赋予0,右分支赋予1(也可以规定左1右0),则从根到每个叶子结点的通路上,各分支的赋值分别构成一个二进制串,该二进制串就称为哈夫曼编码.

就拿上述将哈夫曼构建中的树来进行编码

可以通过分支上的数字来进行编码
如下
A:1000
B:101
C:0
D:11
E:1001

• 总结

• 1.n个权值构建出来的哈夫曼树拥有n个叶子结点

• 2.每个哈夫曼编码都不是另一个哈夫曼编码的前置

• 3.哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近

• 4.带权路径长度:树中所有的叶子结点的权值乘上其道根结点的路径长度,与最终的哈夫曼编码总长度成正比关系.