N
bad
pass
一. 概念
路径
6.5 赫夫曼树及其应用
从树中一个结点到另一个结点之间的分 支构成这两个结点间的路径；
路径长度 路径的分支数目称为路径长度；
树的路径长度
从树根到树中其余每个 结点的路径长度之和。
2 1A1
B
C
2
DE
6.5 赫夫曼树及其应用
一. 概念
结点的权 根据需要给结点所赋的值；
9
5
4 52 3
重复第3步
14
9
5
4 52 3
练习：构造以W=（5，4，7，2，5）为权的赫夫曼 树。
547 2 5
23
10
13
6 245 7 5
5 56
7
24
6
10
245 5 7
13
6
7
24
10 55
说明
最优二叉树的左右子树可以互换； 结点权值差别很大时，构成如图所示形状； 所有结点权值一样时，构成完全二叉树形状；
WPL=7+10+6+12=35
6.5 赫夫曼树及其应用
一. 概念
最优二叉树(Huffman树)
即假设有n个权值(w1 ,w2 , … , wn )，构造有一棵n个 叶子结点的二叉树，每个叶
子结点带权值wi 。则带权路 径长度WPL最小的二叉树称
为最优二叉树，又称为赫夫
曼树。
a7 b5 c 2 d4
else if(a<70) score=“pass”; else if(a<80) score=“general”; else if(a<90) score=“good”; else score=“excellent”;
a<60
Y
N
分数 0~59 60~69 70~79 80~89 90~100 比例 0.05 0.15 0.40 0.30 0.10
结点的带权路径长度
从根到该结点的路径长
度与该结点权值的乘积；
2
61 A 1 3
B
C
2
DE
5
2
6.5 赫夫曼树及其应用
一. 概念
树的带权 路径长度
树中所有叶子结点的带权路径 长度之和。记作:
n
WPL= wk lk k =1
其中， Wk代表第k个叶子的权值；
lk代表从根结点到第k个叶子的
路径长度。
2
a7 b5 c 2 d4
55 55
说明
最优二叉树结点数为叶子数的2倍减1。
证明： 由二叉树性质3得： n0=n2+1 故最优二叉树结点数=n0+n2=n0+n0-1=2n0-1
6.5 赫夫曼树及其应用
赫夫曼树的存储
weight parent lchild rchild
权值 双亲 左孩子 右孩子
typedef struct { int weight; int parent, lchild, rchild;
}HTNode, *HuffmanTree;
//动态分配数组存储赫夫曼树
赫夫曼树的构造算法
void HuffmanTree(HuffmanTree &HT, int * w, int n){ //w存放n个字符的权值，构造赫夫曼树HT if (n<=1) return; m=2* n-1; //m为赫夫曼树总结点数 HT=(HuffmanTree)malloc((m+1) * sizeof(HTNode)); for (p=HT+1, i=1; i<=n; ++i, ++p, ++w) * p={ * w, 0, 0, 0}; for (; i<=m; ++i, ++p) * p={ 0, 0, 0, 0}; for (i=n+1; i<=m; ++i) { //建赫夫曼树 //在HT[1..i-1] 选择parent为0且weight最小的两个结点，其
2．选取与合并：在F中选取两棵根结点权值最小的树作 为左、右子树，构造一棵新的二叉树，且置新二叉树 根的权值为左、右子树根结点权值之和；
3．删除与加入：从F中删除这两棵树，并将新树加入F； 4．重复 2、3，直到F中只含一棵树为止。这棵树就是所
求的赫夫曼树。
6.5 赫夫曼树及其应用
举例：W＝{2，4，5，3} 赫夫曼树的构造过程
序号分别为s1和s2。 Select(HT, i-1, 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;} }
6.5 赫夫曼树及其应用
一. 概念
最优二叉树的特点
1. 权值越大的叶子结点越靠近根结点，而权值 越小的叶子结点越远离根结点。
2. 只有度为0（叶子结点） 和度为2（分支结点）的 结点，不存在度为1的结 点。
a7 b5
2
c
d4
6.5 赫夫曼树及其应用
二.最优二叉树的构造
赫夫曼算法步骤：
1．初始化：根据给定的n个权值 ，构造n棵二叉树集合 F，其中每棵二叉树中只有一个带权为wi的根结点， 其左右子树均为空；
61 A 1 3
B
C
2
DE
5
2
6.5 赫夫曼树及其应用
一. 概念
树的带权路径长度
例：有3棵二叉树，都有4个叶子结点a、b、c、d，且带 相
同权值7、5、2、4，3棵树的带权路径长度分别为：
7
a
5
b
c
2
d4
WPL=14+10+4+8=36
2
c
4
d a7 b5
WPL=8+21+15+2=46
a7 b5 c 2 d4
数据结构
第六章 树和二叉树
6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用
6.5 赫夫曼树及其应用
编制一个将学生的百分制成绩转换成五分制 成绩的程序。其中若成绩低于60分，记为“bad”;
成绩介于60和69之间，记为“pass”;成绩介于70和79之间 的，记为“general”;成绩介于80和89之间的，记为 “good”;成绩高于90分的，记为“excellent”。 if (a<60) score=“bad”;
第1步：初始化
24 5 3
第2步：选取与合并 第3步：删除与加入
5 23 45 5
23
6.5 赫夫曼树及其应用
举例：W＝{2，4，5，3} 赫夫曼树的构造过程
重复第2步
45 5
23 9
重复第3步
45
9
5
4 52 3
6.5 赫夫曼树及其应用
举例：W＝{2，4，5，3} 赫夫曼树的构造过程
重复第2步
bad
a<70
Y
N
pass
a<80
Y
10000(1×0.05+2×0.15+3×0.4+4×0.4) =31500
N
general a<90
Y
N
good excellent
10000(2×0.4+2×0.3+2×0.1+3×0.2)
=22000
Y
a<60
Y
a<80
Y
N
a<70
N
a<90
Y
N
general good excellent