哈夫曼树和哈夫曼编码

快来打我* 2022-07-18 01:23 356阅读 0赞

# 哈夫曼树 #

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

# 基本概念 #

## 哈夫曼树（霍夫曼树）又称为最优树. ##

## 1、路径和路径长度 ##

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

## 2、结点的权及带权路径长度 ##

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

## 3、树的带权路径长度 ##

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

# 哈夫曼树的构造 #

## 哈夫曼树的构造 ##

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

# 举例 #

简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：

![这里写图片描述][20160904113908547]

虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成\{5,4,3,3\}，再根据第二步，取最小的两个权值构成新树，如图：

![这里写图片描述][20160904113924235]

再依次建立哈夫曼树，如下图：  
![这里写图片描述][20160904115535611]

其中各个权值替换对应的字符即为下图：

# 哈夫曼编码 #

![这里写图片描述][20160904113959013]

所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010

霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。

[20160904113908547]: /images/20220717/58c321c90be94698aa1a5039f4380d73.png
[20160904113924235]: /images/20220717/ab05810aaccf4c2da5be59b2111dadd2.png
[20160904115535611]: /images/20220717/0ba04b8cc9c44010a5b3af9a6c892fef.png
[20160904113959013]: /images/20220717/7f7cc587e36442ce9669b3d1c14caf31.png

发表评论取消回复

表情：

评论列表（有 0 条评论，356人围观）

还没有评论，来说两句吧...

相关阅读

相关哈夫曼树和哈夫曼编码

哈夫曼树和哈夫曼编码 include <stdio.h> include <string.h> define N 50 //叶子结点数 de

深藏阁楼爱情的钟/ 2023年03月12日 12:15/ 0 赞/ 116 阅读

相关浅析哈夫曼树和哈夫曼编码

在浅析哈夫曼树之前，先来了解几个关于树的概念 1、什么是路劲在树中，从一个点到另一个点所经过的点被称为这两个点之间的路劲。 ![watermark_type_ZmFuZ

太过爱你忘了你带给我的痛/ 2023年01月23日 14:51/ 0 赞/ 102 阅读

相关哈夫曼树与哈夫曼编码

哈夫曼树与哈夫曼编码哈夫曼树如何构建哈夫曼树构建哈夫曼树的实现哈夫曼编码完整代码哈夫曼树哈夫曼树是一类带

柔光的暖阳◎/ 2022年10月26日 01:21/ 0 赞/ 361 阅读

相关哈夫曼树、哈夫曼编码详解

哈夫曼树介绍 hello，大家好，我是bigsai。本以为哈夫曼树、哈夫曼编码很难，结果很容易嘛！哈夫曼树、哈夫曼编码很多人可能听过，但是可能并没有认真学习了解，今天

╰+哭是因爲堅強的太久メ/ 2022年10月07日 08:54/ 0 赞/ 377 阅读

相关 641-哈夫曼树和哈夫曼编码

哈夫曼树理论最佳判定树，最优二叉树 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_te

╰+攻爆jí腚メ/ 2022年09月12日 12:43/ 0 赞/ 288 阅读

相关哈夫曼树与哈夫曼编码

在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如 JPEG中就应用

曾经终败给现在/ 2022年07月30日 19:21/ 0 赞/ 390 阅读

相关哈夫曼树和哈夫曼编码

哈夫曼树给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径

快来打我*/ 2022年07月18日 01:23/ 0 赞/ 357 阅读

相关哈夫曼树与哈夫曼编码

参考 \[url\]http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html\[/url\] \[url

落日映苍穹つ/ 2022年04月11日 05:49/ 0 赞/ 327 阅读

相关哈夫曼树与哈夫曼编码

优质文档值得推荐 [哈夫曼（huffman）树和哈夫曼编码][huffman] [huffman]: https://www.cnblogs.com/kubixueshe

╰+攻爆jí腚メ/ 2022年03月14日 08:56/ 0 赞/ 404 阅读

相关哈夫曼树和哈夫曼编码

当树中的节点被赋予一个表示某种意义的数值，我们称之为该节点的权。从树的根节点到任意节点的路径长度(经过的边数)与该节点上权值的乘积称为该节点的带权路径长度。树中所有叶节点的带权

Dear 丶/ 2021年09月15日 02:50/ 0 赞/ 534 阅读