数据结构--霍夫曼树与霍夫曼编码

妖狐艹你老母 2021-12-17 16:33 373阅读 0赞

### 文章目录 ###

*  最优树的定义
 *  如何构造最优树（霍夫曼算法）
 *  霍夫曼编码
 *   *  前缀编码
 *  总结

# 最优树的定义 #

**节点的路径长度定义为：从根节点到该节点的路径上分支的数目**。

**树的路径长度定义为：树中每个节点的路径长度之和。**

**树的带权路径长度定义为：树中所有叶子节点的带权路径长度之和**。（叶子节点权值\*节点路径长度）

在所有含 n 个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。

# 如何构造最优树（霍夫曼算法） #

1.  根据给定的`n`个权值 \{ w 1 , w 2 , . . . , w n \} \\\{w\_1, w\_2, ..., w\_n\\\} \{ w1,w2,...,wn\}，构造`n`棵二叉树的集合 F = \{ T 1 , T 2 , . . . , T n \} F = \\\{T\_1, T\_2, ... , T\_n\\\} F=\{ T1,T2,...,Tn\}，其中每棵二叉树中均只含一个带权值为 w i w\_i wi的根结点,其左、右子树为空树;
2.  在`F`中**选取其根结点的权值为最小的两棵二叉树**，分别作为左、右子树构造 一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
3.  从`F`中删去这两棵树，同时加入刚生成的新树;
4.  重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。

例如：已知权值 W = \{ 5 , 6 , 2 , 9 , 7 \} W = \\\{5,6,2,9,7\\\} W=\{ 5,6,2,9,7\}

![\[外链图片转存失败(img-b2v8JNer-1562589594377)(http://note.youdao.com/yws/res/16239/75C3E75544CE49A1A1A140AE70F6E11E)\]][img-b2v8JNer-1562589594377_http_note.youdao.com_yws_res_16239_75C3E75544CE49A1A1A140AE70F6E11E]

# 霍夫曼编码 #

将构成电文的每个不同字符作为叶子结点，其权值为电文中字 符的使用频率或次数，构造哈夫曼树。此哈夫曼树中从根到每个叶子结点都有一条唯一的路径，对路径上各分支约定，左分支标识为“0”码，右标识为“1”码，则从根结点到叶子结点的路径上分支的“0”、“1”码组成的字符串即为该叶子结点的霍夫曼编码。

举例:数据传送中的二进制编码,要传送数据 state, seat, act, tea, cat, set, a, eat，如 何使传送的长度最短?

首先规定二叉树的构造为左走 0，右走 1。

为了保证长度最短，先看字符出现的次数，然后将出现次数当作权，如下所示。

![\[外链图片转存失败(img-d3F25aA0-1562589594389)(http://note.youdao.com/yws/res/16250/B1A64894DB5946F2B33A309EAF56AC71)\]][img-d3F25aA0-1562589594389_http_note.youdao.com_yws_res_16250_B1A64894DB5946F2B33A309EAF56AC71]

构建霍夫曼树的过程：

![\[外链图片转存失败(img-KCPapmew-1562589594393)(http://note.youdao.com/yws/res/16252/1BD26841D24645869215062B7870DC06)\]][img-KCPapmew-1562589594393_http_note.youdao.com_yws_res_16252_1BD26841D24645869215062B7870DC06]

霍夫曼编码：

![\[外链图片转存失败(img-lyYtaHEa-1562589594406)(http://note.youdao.com/yws/res/16258/00133F33E19B4F1D84F623FA1355B670)\]][img-lyYtaHEa-1562589594406_http_note.youdao.com_yws_res_16258_00133F33E19B4F1D84F623FA1355B670]

所以有 state 的编码为`00111101101`，stat的编码为`001111011`。

## 前缀编码 ##

若要设计长短不等的编码,则必须是任一个字符的编码都不是另外一个字符编码的前缀,这种编码称做前缀编码。（否则解析时会出现错误）

# 总结 #

1.  用n个权值(对应n个叶子结点)构造哈夫曼树，共需要 n − 1 n-1 n−1次合并，即哈夫曼树中非叶子结点的总数为 n − 1 n-1 n−1，总结点个数为 2 n − 1 2n-1 2n−1。
2.  哈夫曼树中没有度为1的结点，**因为非叶子结点都是通过两个结点合并而来**。但是，没有度为1的二叉树并不一定是哈夫曼树。
3.  用 n 个权值(对应n个叶子结点)构造的哈夫曼树，形态并不是唯一的。
4.  哈夫曼编码是能使电文代码总长最短的编码方式。此结论由哈夫曼树是带权路径长度最小的树的特征可得。
5.  哈夫曼编码是一种前缀编码，保证其在译码时不会产生歧义。因为，在哈夫曼编码中，每个字符都是叶子结点，而叶子结点不可能从根结点到其他叶子结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀。
6.  深度为 h h h的哈夫曼树，其叶子结点的最大编码长度为 h − 1 h-1 h−1。

[img-b2v8JNer-1562589594377_http_note.youdao.com_yws_res_16239_75C3E75544CE49A1A1A140AE70F6E11E]: /images/20211213/35f06859b4734fc1916d0ac02a4f3016.png
[img-d3F25aA0-1562589594389_http_note.youdao.com_yws_res_16250_B1A64894DB5946F2B33A309EAF56AC71]: /images/20211213/4fbdc7c5b6b54c17b6871a055b67a3ee.png
[img-KCPapmew-1562589594393_http_note.youdao.com_yws_res_16252_1BD26841D24645869215062B7870DC06]: /images/20211213/69397e42eb1743c185a70465e3a6167c.png
[img-lyYtaHEa-1562589594406_http_note.youdao.com_yws_res_16258_00133F33E19B4F1D84F623FA1355B670]: /images/20211213/9f26685fe72b4e2f989784c8550d9a93.png