1
7.6 Huffman树及其应用
一,Huffman树
二,Huffman编码
最优二叉树Huffman树
Huffman编码
带权路径
长度最短
的树
不等长编码
是通信
中最经
典的压
缩编码
2
一,Huffman树 （最优二叉树）
路 径,
路径长度,
二叉树的路径长
度,
二叉树的带权路
径长度,
Huffman树,
由一结点到另一结点间的分支所构成。
路径上的分支数目。
从 二叉 树根到 每一结点 的路径长度
之和。
从 二叉 树根结点到所有叶子结点的路径长度与
相应叶子结点权值的乘积（ WPL）
若干术语：
d e
b
a
c
f g
即树中所有 叶子结点 的带权路径长度之和
带权路径长度最小的树。
例如,a→e 的路径长度＝
树长度＝
2
10
Huffman常译为 赫夫曼、霍夫曼、哈夫曼等
3
树的带权路径长度
如何计算？ WPL = ?wklk k=1
n
a b dc
7 5 2 4
(a)
c
d
a b
2
4
57
(b)
b
d
a
c
7
5
2 4
(c)
经典之例：
WPL= WPL= WPL=
Huffman树是 WPL 最小的树
树中所有叶子结
点的带权路径长
度之和
36 46 35
4
1,构造 Huffman树的基本思想：
例,设有 4个字符 d,i,a,n，出现的频度分别为 7,5,2,4，
怎样编码才能使它们组成的报文在网络中传得最快？
法 1,等长编码 （如二进制编码）
令 d=00,i=01,a=10,n=11，则：
WPL1＝ 2bit× (7＋ 5＋ 2＋ 4）＝ 36
法 2,不等长编码 （如 Huffman编码）
令 d=0;i=10,a=110,n=111，则：
明确：要实现 Huffman编码，就要先构造 Huffman树
讨论,Huffman树有什么用？
权值大的结点用短路径，权值小的结点用长路径。
WPL最小的树
频度高的信息
用短码，反之
用长码，传输
效率肯定高！
WPL2=1bit× 7＋ 2bit× 5+3bit× (2+4)=35
最小冗余编码、信息高效传输
5
2,构造 Huffman树的步骤（即 Huffman算法）：
(1) 由给定的 n 个权值 { w1,w2,…,wn }构成 n棵二叉树的集合 F =
{ T1,T2,…,Tn } （即森林）,其中每棵二叉树 Ti 中 只有一个
带权为 wi 的根结点，其左右子树均空。
(2) 在 F 中选取 两棵根结点权值最小的树 做为左右子树构造一棵
新的二叉树，且让新二叉树根结点的权值 等于 其左右子树的
根结点 权值之和 。
(3) 在 F 中删去这两棵树，同时将新得到的二叉树加入 F中 。
(4) 重复 (2) 和 (3),直到 F 只含一棵树为止。这棵树便是 Huffman
树。
怎样证明它就是 WPL最小的最优二叉树？ 参考, 信源编码,
Huffman树的特点：没有度为 1的结点。
6
step1,对权值进行合并、删除与替换
—— 在权值集合 {7,5,2,4}中，总是合并 当前值最小 的两个权
具体操作步骤：
a,初始
方框表示外结点（叶子，字符）
圆框表示内结点
（合并后的权值）
b,合并 {2} {4}
c,合并 {5} {6} d,合并 {7} {11}
7
step2,按左, 0”右, 1” 对 Huffman树的所有分支编
号
d
a
i
n
1
1
10
0
0
Huffman编码结果,d=0,i=10,a=110,n=111
WPL=1bit× 7＋ 2bit× 5+3bit(2+4)=35（小于等长码的 WPL=36）
特征：每一码不会是另一码的前缀，译码时可惟一复原
Huffman编码也称为 前缀码
—— 将 Huffman树 与 Huffman编码 挂钩
8
二,Huffman编码
（ 1） 由于 Huffman树的 WPL最小,说明编码所
需要的 比特数最少 。
（ 4） Huffman编码时是从叶子走到根；而译码时又要从根走
到叶子，因此每个结点需要增开 双亲 指针分量（连同结点 权值
共要开 5个分量）
（ 5） 用计算机实现时，顺序和链式两种存储结构都要用到。
分析 Huffman树和编码的特点：
霍夫曼 编码的基本思想是 ——
出现概率大的信息用短码，概率小的用长码,最小冗余
这种编码已广泛应
用于网络通信中。（ 2） Huffman树 肯定没有度为 1的结点；
（ 3） 一棵有 n 0个叶子结点的 Huffman树，共有 2n0-1个结点；
（因为 n=n0+n1+n2=2n0-1)
9
如何编程实现 Huffman编码？
建议 1,Huffman树中结点的结构可设计成 5分量形式：
char weight parent lchild rchild
将整个 Huffman树的 结点 存储在一个数组 HT[1..n..m]中 ;
各叶子结点的 编码 存储在另一, 复合, 数组 HC[1..n]中。
建议 2,Huffman树的 存储结构可采用 顺序存储 结构：
10
typedef struct{
unsigned int weight； //权值分量（可放大取整）
unsigned int parent,lchild,rchild； //双亲和孩子分量
}HTNode,*HuffmanTree； //用动态数组存储 Huffman树
typedef char**HuffmanCode； //动态数组存储 Huffman编码表
Huffman树和 Huffman树编码的存储表示：
0
0
0
r
092
0019
007
lpw
3
2
1
双亲
*HuffmanTree或 HT向量
HT[3].parent=9
指针型指针
11
如何编程实现 Huffman编码？ 参见教材 P147
先构造 Huffman树 HT,再求出 N个字符的 Huffman编码 HC。
Void HuffmanCoding(HuffmanTree &HT,HuffmanCode
&HC,int *w,int n){
if (n<=1)return;
m=2*n-1; //n 0个叶子的 HuffmanTree共有 2n0-1个结点；
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0单元未用
*w存放 n个字符的权值
for(p=HT,i=1; i<=n; ++i,++p,++w)*p={*w,0,0,0}; //给前 n0个单元
初始化
for(； i<=m; ++i,++p)*p ={0,0,0,0}; //对叶子之后的存储单元清零
for(i=n+1;i<=m; ++i){ //建 Huffman树 (从 叶子后开始存内结点 )
Select(HT,i-1,s1,s2); //在 HT[1…i -1]选择 parent为 0且 weight最小 的
两个结点，其序号分别为 S1和 s2（ 教材未给出此函数源码）
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+ HT[s2].weight;}
12
(续前 )再求出 n个字符的 Huffman编码 HC
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配 n个字符
编码的头指针向量（一维数组）
cd=(char*) malloc(n*sizeof(char)); //分配求编码的工作空间 (n)
cd[n-1]=“\0”; //编码结束符（从 cd[0]~cd[n-1]为合法空间）
for(i=1;i<=n;++i){ //逐个字符求 Huffman编码
start=n-1; //编码结束符位置
for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)//从叶子到
根逆向求编码
if(HT[f].lchild==c) cd[--start]=“0”;
else cd[--start]=“1”;
HC[i]=(char*)malloc((n-start)*sizeof(char));//为第 i个字
符编码分配空间
strcpy(HC[i],&cd[start]); //从 cd复制编码串到 HC
}
free(cd); //释放工作空间
}//HuffmanCoding
13
Huffman编码举例
解,先将概率 放大 100倍,以方便构造哈夫曼树。
放大后的权值集合 w={ 7,19,2,6,32,3,21,10 }，
按哈夫曼树构造规则 （合并、删除、替换）,可得到哈夫曼树。
例 1【 严题集 6.26③】, 假设用于通信的电文仅由 8个字母 {a,b,
c,d,e,f,g,h} 构成，它们在电文中出现的概率分别为 { 0.07,0.19,
0.02,0.06,0.32,0.03,0.21,0.10 }，试为这 8个字母设计哈夫曼 编
码。如果用 0～ 7的二进制编码方案又如何？ 【 类同 P148例 2】
14
107
17
000—
000—
000—
000—
000—-
0
0
0
0
0
0
0
0
r
0010
0021
003
0032
006
002
0019
007
lpw
13
12
10
11
9
8
7
6
5
4
3
2
1
11
6
w={ 7,19,2,6,32,3,21,10 }在机内存储形式为,
2 3
5
28
2119
4032
60
100
b
c
ad
e
g
f
h
请注意：哈夫曼
树样式不惟一！
√
√
5
9
9
√
√
11
10
10
4 9
17
28
√
√
√
√
√
√
40
√
√
60100
双亲 左右孩子
3 6
15
107
1711
6
2 3
5
28
2119
4032
60
100
b
c
ad
e
g
f
h
对应的哈夫曼编码：
符 编码 频率
a 0.07
b 0.19
c 0.02
d 0.06
e 0.32
f 0.03
g 0.21
h 0.10
符 编码 频率
a 0.07
b 0.19
c 0.02
d 0.06
e 0.32
f 0.03
g 0.21
h 0.10
0010
10
00000
0001
01
00001
11
0011
000
001
010
011
100
101
110
111
0
0
0
0
0
0
0
1
1
1
1
11
1
Huffman码的 WPL＝ 2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03)
=1.44+0.92+0.25=2.61
3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 二进制等长码的 WPL＝
按左 0右 1标注
16
另
一
种
表
示
：
17
小结：哈夫曼树及其应用
1.Huffman算法的思路：
—— 权值大的结点用短路径，权值小的结点
用长路径。
2.构造 Huffman树的步骤：
—— 对权值的合并、删除与替换
3,Huffman编码规则,左, 0” 右, 1”
—— 又称为 前缀码、最小冗余编码、紧致码 等等，
它是数据压缩学的基础。
18
上机实验说明,设字符集为 26个英文字母，其出现频
度如下表所示。
注：若在规定时间内圆满实现，平时成绩将以满分计。
51481156357203251频度
zyxwvut字符
11611882380频度
p
21
f
q
15
g
r
47
h
sonmlkj字符
5710332221364186频度
iedcba空格字符
要求,先建 Huffman树，再利用此树对任一字符串文
件进行编码和译码 ——即设计一个 Huffman编 /译码器
19
本 章 小 结
1,定义和性质
2,存储结构
3,遍历
4,线索化
顺序结构
链式结构
二叉链表
三叉链表
先序线索树
中序线索树
后序线索树
树
二叉树森林
Huffman编码
1:2,性质有 3+2条
先
序
遍
历
中
序
遍
历
遍历
存储结构 遍历
孩子 —兄弟 先序遍历 后序遍历
线索树
Huffman树
应
用
中序遍历
后序遍历
先序遍历
层次遍历
第 7章结束
7.6 Huffman树及其应用
一,Huffman树
二,Huffman编码
最优二叉树Huffman树
Huffman编码
带权路径
长度最短
的树
不等长编码
是通信
中最经
典的压
缩编码
2
一,Huffman树 （最优二叉树）
路 径,
路径长度,
二叉树的路径长
度,
二叉树的带权路
径长度,
Huffman树,
由一结点到另一结点间的分支所构成。
路径上的分支数目。
从 二叉 树根到 每一结点 的路径长度
之和。
从 二叉 树根结点到所有叶子结点的路径长度与
相应叶子结点权值的乘积（ WPL）
若干术语：
d e
b
a
c
f g
即树中所有 叶子结点 的带权路径长度之和
带权路径长度最小的树。
例如,a→e 的路径长度＝
树长度＝
2
10
Huffman常译为 赫夫曼、霍夫曼、哈夫曼等
3
树的带权路径长度
如何计算？ WPL = ?wklk k=1
n
a b dc
7 5 2 4
(a)
c
d
a b
2
4
57
(b)
b
d
a
c
7
5
2 4
(c)
经典之例：
WPL= WPL= WPL=
Huffman树是 WPL 最小的树
树中所有叶子结
点的带权路径长
度之和
36 46 35
4
1,构造 Huffman树的基本思想：
例,设有 4个字符 d,i,a,n，出现的频度分别为 7,5,2,4，
怎样编码才能使它们组成的报文在网络中传得最快？
法 1,等长编码 （如二进制编码）
令 d=00,i=01,a=10,n=11，则：
WPL1＝ 2bit× (7＋ 5＋ 2＋ 4）＝ 36
法 2,不等长编码 （如 Huffman编码）
令 d=0;i=10,a=110,n=111，则：
明确：要实现 Huffman编码，就要先构造 Huffman树
讨论,Huffman树有什么用？
权值大的结点用短路径，权值小的结点用长路径。
WPL最小的树
频度高的信息
用短码，反之
用长码，传输
效率肯定高！
WPL2=1bit× 7＋ 2bit× 5+3bit× (2+4)=35
最小冗余编码、信息高效传输
5
2,构造 Huffman树的步骤（即 Huffman算法）：
(1) 由给定的 n 个权值 { w1,w2,…,wn }构成 n棵二叉树的集合 F =
{ T1,T2,…,Tn } （即森林）,其中每棵二叉树 Ti 中 只有一个
带权为 wi 的根结点，其左右子树均空。
(2) 在 F 中选取 两棵根结点权值最小的树 做为左右子树构造一棵
新的二叉树，且让新二叉树根结点的权值 等于 其左右子树的
根结点 权值之和 。
(3) 在 F 中删去这两棵树，同时将新得到的二叉树加入 F中 。
(4) 重复 (2) 和 (3),直到 F 只含一棵树为止。这棵树便是 Huffman
树。
怎样证明它就是 WPL最小的最优二叉树？ 参考, 信源编码,
Huffman树的特点：没有度为 1的结点。
6
step1,对权值进行合并、删除与替换
—— 在权值集合 {7,5,2,4}中，总是合并 当前值最小 的两个权
具体操作步骤：
a,初始
方框表示外结点（叶子，字符）
圆框表示内结点
（合并后的权值）
b,合并 {2} {4}
c,合并 {5} {6} d,合并 {7} {11}
7
step2,按左, 0”右, 1” 对 Huffman树的所有分支编
号
d
a
i
n
1
1
10
0
0
Huffman编码结果,d=0,i=10,a=110,n=111
WPL=1bit× 7＋ 2bit× 5+3bit(2+4)=35（小于等长码的 WPL=36）
特征：每一码不会是另一码的前缀，译码时可惟一复原
Huffman编码也称为 前缀码
—— 将 Huffman树 与 Huffman编码 挂钩
8
二,Huffman编码
（ 1） 由于 Huffman树的 WPL最小,说明编码所
需要的 比特数最少 。
（ 4） Huffman编码时是从叶子走到根；而译码时又要从根走
到叶子，因此每个结点需要增开 双亲 指针分量（连同结点 权值
共要开 5个分量）
（ 5） 用计算机实现时，顺序和链式两种存储结构都要用到。
分析 Huffman树和编码的特点：
霍夫曼 编码的基本思想是 ——
出现概率大的信息用短码，概率小的用长码,最小冗余
这种编码已广泛应
用于网络通信中。（ 2） Huffman树 肯定没有度为 1的结点；
（ 3） 一棵有 n 0个叶子结点的 Huffman树，共有 2n0-1个结点；
（因为 n=n0+n1+n2=2n0-1)
9
如何编程实现 Huffman编码？
建议 1,Huffman树中结点的结构可设计成 5分量形式：
char weight parent lchild rchild
将整个 Huffman树的 结点 存储在一个数组 HT[1..n..m]中 ;
各叶子结点的 编码 存储在另一, 复合, 数组 HC[1..n]中。
建议 2,Huffman树的 存储结构可采用 顺序存储 结构：
10
typedef struct{
unsigned int weight； //权值分量（可放大取整）
unsigned int parent,lchild,rchild； //双亲和孩子分量
}HTNode,*HuffmanTree； //用动态数组存储 Huffman树
typedef char**HuffmanCode； //动态数组存储 Huffman编码表
Huffman树和 Huffman树编码的存储表示：
0
0
0
r
092
0019
007
lpw
3
2
1
双亲
*HuffmanTree或 HT向量
HT[3].parent=9
指针型指针
11
如何编程实现 Huffman编码？ 参见教材 P147
先构造 Huffman树 HT,再求出 N个字符的 Huffman编码 HC。
Void HuffmanCoding(HuffmanTree &HT,HuffmanCode
&HC,int *w,int n){
if (n<=1)return;
m=2*n-1; //n 0个叶子的 HuffmanTree共有 2n0-1个结点；
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0单元未用
*w存放 n个字符的权值
for(p=HT,i=1; i<=n; ++i,++p,++w)*p={*w,0,0,0}; //给前 n0个单元
初始化
for(； i<=m; ++i,++p)*p ={0,0,0,0}; //对叶子之后的存储单元清零
for(i=n+1;i<=m; ++i){ //建 Huffman树 (从 叶子后开始存内结点 )
Select(HT,i-1,s1,s2); //在 HT[1…i -1]选择 parent为 0且 weight最小 的
两个结点，其序号分别为 S1和 s2（ 教材未给出此函数源码）
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+ HT[s2].weight;}
12
(续前 )再求出 n个字符的 Huffman编码 HC
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配 n个字符
编码的头指针向量（一维数组）
cd=(char*) malloc(n*sizeof(char)); //分配求编码的工作空间 (n)
cd[n-1]=“\0”; //编码结束符（从 cd[0]~cd[n-1]为合法空间）
for(i=1;i<=n;++i){ //逐个字符求 Huffman编码
start=n-1; //编码结束符位置
for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)//从叶子到
根逆向求编码
if(HT[f].lchild==c) cd[--start]=“0”;
else cd[--start]=“1”;
HC[i]=(char*)malloc((n-start)*sizeof(char));//为第 i个字
符编码分配空间
strcpy(HC[i],&cd[start]); //从 cd复制编码串到 HC
}
free(cd); //释放工作空间
}//HuffmanCoding
13
Huffman编码举例
解,先将概率 放大 100倍,以方便构造哈夫曼树。
放大后的权值集合 w={ 7,19,2,6,32,3,21,10 }，
按哈夫曼树构造规则 （合并、删除、替换）,可得到哈夫曼树。
例 1【 严题集 6.26③】, 假设用于通信的电文仅由 8个字母 {a,b,
c,d,e,f,g,h} 构成，它们在电文中出现的概率分别为 { 0.07,0.19,
0.02,0.06,0.32,0.03,0.21,0.10 }，试为这 8个字母设计哈夫曼 编
码。如果用 0～ 7的二进制编码方案又如何？ 【 类同 P148例 2】
14
107
17
000—
000—
000—
000—
000—-
0
0
0
0
0
0
0
0
r
0010
0021
003
0032
006
002
0019
007
lpw
13
12
10
11
9
8
7
6
5
4
3
2
1
11
6
w={ 7,19,2,6,32,3,21,10 }在机内存储形式为,
2 3
5
28
2119
4032
60
100
b
c
ad
e
g
f
h
请注意：哈夫曼
树样式不惟一！
√
√
5
9
9
√
√
11
10
10
4 9
17
28
√
√
√
√
√
√
40
√
√
60100
双亲 左右孩子
3 6
15
107
1711
6
2 3
5
28
2119
4032
60
100
b
c
ad
e
g
f
h
对应的哈夫曼编码：
符 编码 频率
a 0.07
b 0.19
c 0.02
d 0.06
e 0.32
f 0.03
g 0.21
h 0.10
符 编码 频率
a 0.07
b 0.19
c 0.02
d 0.06
e 0.32
f 0.03
g 0.21
h 0.10
0010
10
00000
0001
01
00001
11
0011
000
001
010
011
100
101
110
111
0
0
0
0
0
0
0
1
1
1
1
11
1
Huffman码的 WPL＝ 2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03)
=1.44+0.92+0.25=2.61
3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 二进制等长码的 WPL＝
按左 0右 1标注
16
另
一
种
表
示
：
17
小结：哈夫曼树及其应用
1.Huffman算法的思路：
—— 权值大的结点用短路径，权值小的结点
用长路径。
2.构造 Huffman树的步骤：
—— 对权值的合并、删除与替换
3,Huffman编码规则,左, 0” 右, 1”
—— 又称为 前缀码、最小冗余编码、紧致码 等等，
它是数据压缩学的基础。
18
上机实验说明,设字符集为 26个英文字母，其出现频
度如下表所示。
注：若在规定时间内圆满实现，平时成绩将以满分计。
51481156357203251频度
zyxwvut字符
11611882380频度
p
21
f
q
15
g
r
47
h
sonmlkj字符
5710332221364186频度
iedcba空格字符
要求,先建 Huffman树，再利用此树对任一字符串文
件进行编码和译码 ——即设计一个 Huffman编 /译码器
19
本 章 小 结
1,定义和性质
2,存储结构
3,遍历
4,线索化
顺序结构
链式结构
二叉链表
三叉链表
先序线索树
中序线索树
后序线索树
树
二叉树森林
Huffman编码
1:2,性质有 3+2条
先
序
遍
历
中
序
遍
历
遍历
存储结构 遍历
孩子 —兄弟 先序遍历 后序遍历
线索树
Huffman树
应
用
中序遍历
后序遍历
先序遍历
层次遍历
第 7章结束
