数据结构（闫会峰）：huffman

Huffman树及其应用
Huffman树
基本概念
– 两个结点间的路径
由一个结点到另一个结点之间的分支构成
– 路径长度
路径上的分支数目
– 树的路径长度
从树根到每个结点的路径长度之和
– 结点的带权路径长度
从该结点到树根之间的路径长度与结点上的权的乘积
– 树的带权路径长度
树中所有叶子结点的带权路径长度之和，记作 WPL
Huffman树
如
a b c d
7 5 2 4 c
d4 5
2
7
a b
a
b
b
7
5
4
c
2
WPL = 7*2 +5*2 + 2*2 +4*2 = 36
WPL = 4*2 +7*3 + 5*3 +2*1 = 46
WPL = 7*1 + 5*2 + 2*3 +4*3 = 35
Huffman树
Huffman树
– 又称赫夫曼树或最优二叉树
– 假设有 n个权值 {w1,w2,…w n}，试构造一棵有 n各叶子结点的二叉树，每个叶子结点带权为 wi，则其中 带权路径长度 WPL最小 的二叉树即为 Huffman树
– 权在不同应用中含义不同，如所占比例，出现概率等
Huffman树的应用
– 用于实现最佳判定算法，让概率最大的事件尽早被判定
– 用于通信编码，让概率大的字符对应的编码尽可能短
– 等等
Huffman树如：将百分制转换为五分制分数 0~59 60~69 70~79 80~89 90~100
比例数 5% 15% 40% 30% 10% 权已知：
可能的判定算法：
a<60
a<70
a<80
a<90
不及格及格中等良好 优良
70 a 80
80 a 90
60 a 70
a<60



不及格 优良及格中等良好
a<80
a<70 a<90
a<60
不及格 及格中等 良好 优良
Huffman树
构造 Huffman树的一般规律
– 1) 根据给定的 n个权值 {w1,w2,…w n}，构成 n棵二叉树的集合 F={T1,T2,…T n}，其中每棵二叉树 Ti中只有一个带权为 wi的根结点，其左右子树均空
– 2) 在 F中选取两棵根结点的权值 最小 的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和
– 3) 在 F中删除这两棵树，同时将新得到的二叉树加入 F中
– 重复 2)和 3)，直到 F中只含一棵树为止。此时得到的便是 Huffman树
Huffman树
如,已知事件 a,b,c,d对应的权值集合 w={7,5,2,4}，试设计对应 Huffman树
a b c d
7 5 2 4
step1 c d2 4
6
a b
7 5
step2
a
7
c d
2 4
6b5
11
step3
a
7
c d
2 4
6b5
11
step4
18
Huffman树
如,已知事件 a,b,c,d,e,f对应的权值集合 w={5,4,7,19,11,8}，
试设计对应 Huffman树
a b c d
5 4 7 19
step1
e f
11 8
a b
5 4
9
c d
7 19
e f
11 8
step2
a b
5 4
9
c
d
7
19 e
f
11
8
step3
15
a b
5 4
9 c
d
7
19
e f
11 8
step4
1520
a b
5 4
9
c
d
7
19
e
f11
8
step5
15
20 34
a b
5 4
9
c
d
7
19
e
f11
8
step6
15
20 34
54
Huffman树
如,已知某系统在通信联络中只可能出现八种字符，其概率分别为 5%,25%,7%,8%,14%,23%,3%,11%，试设计对应
Huffman树
3 5
8
7 8
1511
19
14
2923
42
25
54
96
或
3 5
87
15 8 11
19
14
29 23
42
25
54
96
★ 在人工构造 Huffman树的过程中，如果出现权值相同的情况，可能会出现不同的结构。但若通过算法进行构造，则 Huffman树唯一
Huffman树
前缀编码 (又称 Huffman编码 )
– 任一字符的编码都不是另一字符编码的前缀
– 如 a的编码为,0
b的编码为,100
k的编码为,101
e的编码为,11
Huffman树
使用 Huffman树实现前缀编码
– 基于,Huffman树是带权路径长度最短的二叉树
– 方法：以电文出现的 n个字符的频率作权,n个字符为叶，生成 Huffman树。
– 编码：由根开始，左子树分支对应编码 0，右子树分支对应编码 1，为每个叶结点找到由根出发为 0,1的序列即为该叶结点的前缀编码。
– 如下列二叉树，可得到各字符的二进制编码
a
e
b k
各字符的二进制编码为：
a,0,b,100,k,101,e,11
如电文 1000101110…
可译为,bakea…
0
0
0 1
1
1
Huffman树
如,某系统在通信联络中只可能出现八种字符 u,a,d,c,e,b,z,g，
其概率分别为 5%,29%,7%,8%,14%,23%,3%,11%，试设计对应 Huffman树并给出各字符的前缀编码
5 3
8
7 8
1511
19
14
2923
42
29
58
100
或
3 5
87
15 8 11
19
14
29 23
42
29
58
100
u
a
d c
e
b
z
g
a:10,b:00,c:1111,d:1110,
e:110,g:010,u:0111,z:0110
a:00,b:10,c:110,d:0110,
e:010,g:111,u:01111,z:01110
a
e
d
z u
c g
b
Huffman树
Huffman树的特征
– Huffman树中没有度为 1的结点
– 一棵有 n个叶子结点的 Huffman树共有 2n-1个结点 (分支结点共 n-1个 )
构造 Huffman树的算法设计
– 用大小为 2n-1的一维数组来存储 Huffman树中的所有结点
– 每个结点包含结点权值、左右子结点指针和父结点指针 (用于求编码 )
Huffman树
Huffman树的存储结构
Typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
一维树组空间在程序中动态申请后使用
构造 Huffman树的算法
void CreateHuffmanTree(HuffmanTree &HT,int *w,int n){
//w中存放了 n个权值，构造 Huffman树 HT
if (n<=1) return;
m = 2 * n – 1;
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
for (p=HT,i=1; i<=n; ++i,++p,++w) *p = {*w,0,0,0};
for (; i<=m; ++i,++p) *p = {0,0,0,0}; //初始化 HT
for (i=n+1; i<=m; ++i) {
//在 HT[1..i-1]中选择 parent为 0且权值最小的两个结点，序号分别为 s1和 s2
s1 = s2 = 1;
for (k=2; k<i-1; i++) {
if (HT[k]<HT[s1]) { s2= s1; s1 = k;} //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;
}
}
5 0 0 0
29 0 0 0
7 0 0 0
8 0 0 0
14 0 0 0
23 0 0 0
3 0 0 0
11 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 0
1
2
3
4
5
6
7
8
9
10
11
12
14
15
13
如,已知某系统在通信联络中只可能出现八种字符，其概率分别为 5%,29%,7%,8%,14%,23%,3%,11%，试设计对应
Huffman树初始化后
5 9 0 0
29 14 0 0
7 10 0 0
8 10 0 0
14 12 0 0
23 13 0 0
3 9 0 0
11 11 0 0
8 11 1 7
15 12 3 4
19 13 8 9
29 14 5 10
42 15 6 11
58 15 2 12
100 0 13 14
1
2
3
4
5
6
7
8
9
10
11
12
14
15
13
Huffman树
HT weightparentlchild
rchild HT weightparentlchildrchild用于编码时还可增加一字符域
5 3
8
7 8
1511
19
14
2923
42
29
58
100
u
a
d c
e
b
z
g
z
a
d
c
e
b
u
g
z
a
d
c
e
b
u
g
在 Huffman树 HT中，从叶子结点到根逆向求每个字符的 Huffman编码
typedef char** HuffmanCode; //动态分配数组存储 Huffman编码表
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n){
HC = (HuffmanCode)malloc((n+1)*sizeof(char *)); //n个字符编码的头指针向量
cd = (char *)malloc(n*sizeof(char)); //求编码的工作空间
cd[n-1] =,\0”; //编码结束符
for (i=1; i<=n; ++i) { //逐个字符求 Huffman编码，共 n个叶结点
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”;
HT[i] = (char*)malloc((n-start))*sizeof(char));//为第 I个字符编码分配空间
strcpy(HC[i],&cd[start]); //从 cd复制编码 (串 )到 HC
}
free(cd);
}
5 9 0 0
29 14 0 0
7 10 0 0
8 10 0 0
14 12 0 0
23 13 0 0
3 9 0 0
11 11 0 0
8 11 1 7
15 12 3 4
19 13 8 9
29 14 5 10
42 15 6 11
58 15 2 12
100 0 13 14
1
2
3
4
5
6
7
8
9
10
11
12
14
15
13
Huffman树
weight
parent
lchild
rchildHT HC
1
2
3
4
5
6
7
8
0 1 1 0
1 0
1 1 1 0
1 1 1 1
1 1 0
0 0
0 1 1 1
0 1 0
Huffman编码
5 3
8
7 8
1511
19
14
2923
42
29
58
100
u
a
d c
e
b
z
g
z
a
d
c
e
b
u
g
z
a
d
ce
bu
g
作业
电文中字符 a,b,c,d,e,f,g出现的概率分别为
27%,9%,12%,20%,25%,2%,5%，试设计对应 Huffman树并给出各字符的前缀编码