数据结构课ppt霍夫曼树

2012-12-12
25
V1 V2
V3 V4
V1
V3
V2
V4
在有向图中，<V1，V3>表示从V1到V3的一条弧。
V1为弧尾或初始点，V3为弧头或终端点。
在无向图中，(V1，V3)表示V1和V3之间的一条边。
2012-12-12
26
G=( V, E )
V1 V2 V3 V4
顶点集合V={V1 ， V2 ， V3 ， V4 }
• 传送电文时，希望尽可能地缩短电文长 度。 • 一半算法是：对每个字符设计长度不等 的编码，且让电文中出现次数较多的字 符尽可能采用短的编码。
• 需传送的电文为“ABACCDA” 。 • 设：A:0 B : 00 C : 1 D : 01 • 则：要传送的电文为：000011010
出现译码问题
2012-12-12
2.6.2 图的存储结构
（1）图的连接矩阵表示法 （2）图的邻接表示法
2012-12-12
30
图的连接矩阵表示法
V1 V2 V3 V4 V1 0 0 1 0
V1
V3
V2
V3 V2 V4 V4
0
0 1
0
0 0
0
0 0
1
1 0
V1 V2 V3 V4 V1 V1 V3 V2 V3 V2 V4
2012-12-12
0 1 1 1
1 0 0 1
1 0 0 0
1 1 0 0
V4
31
邻接矩阵表示法对求顶点的度很方便。 在无向图中： 顶点的度数=矩阵中对应该顶点的行或列中非 零元素的个数。 在有向图中：
顶点的出度=矩阵中对应该顶点的行中非零元 素的个数。 顶点的入度=矩阵中对应该顶点的列中非零元 素的个数。
2012-12-12
27
• • • • • • •
对于无向图，边的数目e的取值范围是： 0~1/2*n(n-1) 有1/2*n(n-1)条边的无向图称为完全图。 对于有向图，弧的数目e的取值范围是： 0~n(n-1) 有n(n-1)条弧的有向图称为有向完全图。 有很少边或弧的图称为稀疏图；反之称为稠密 图。
2012-12-12
13
• 若要设计长短不等的编码，则必须是任 一个字符的编码都不是另一个字符的编 码的前缀，这种码称作前缀编码。 • 可以使用二叉树来设计二进制的前缀编 码。
2012-12-12
14
• 设计电文总长最短的二进制前缀编码即 以n种字符出现的频率作权，设计一个哈 夫曼树的问题。 • 哈夫曼编码-----利用哈夫曼树构造通讯中 的电文编码（前缀码）。
PL=0+1+1+2+2+2+2=10
2012-12-12
3
树的路径长度用PL表示。
1 1 2 4 5 6 3 4 7 6 PL=0+1+1+2+2+2+2=10 7 PL=0+1+1+2+2+3+3=12 5 2 C
2012-12-12
4
结点带权的路径长度： 从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度： 树中叶子结点带权路径长度之和。
28.有n个叶子结点的哈夫曼树，其结点总数为2n-1
2012-12-12
37
26. 设电文中出现的字符 为A, B, C, D, E，每个字 母在电文中出现的次数分 别为 9, 7 , 3, 5,11，按哈 夫曼得出C的编码是：
0 27
55
1 28
B
E
0
11
1
0 17 1
8
0 C的编码是1100 3 C 5 D 1
28
权：与图的边或弧相关的数。 网：带权的图。 顶点的度：依附于该顶点的边数或弧数。 出度：（仅对有向图）以该顶点为尾的弧数。 入度：（仅对有向图）以该顶点为头的弧数。 路径：顶点A与顶点C之间存在一条路径。路 径上边或弧的数目称为该路径的路径长度。
3 2 5
A
1
B D
C
6
2012-12-12
29
9 A
2012-12-12
1
3 2
B D
5
C
6
V表示顶点的非空有限集合。
VR表示两个顶点之间关系的集合。
2012-12-12
24
有向图
图
无向图
若<v,w>属于VR，则<v,w>表示从v到w的一条 弧，且称v为弧尾，w为弧头。此时的图称为 有向图。 若<v,w>属于VR，必有<w,v>，即VR是对称的， 则以无序对(v,w)代替这两个有序对，表示v 和w之间的一条边。此时的图称为有向图。
2012-12-12
15
例2：要传输的电文是{CAS；CAT；SAT；AT}
要传输的字符集是 D={C，A，S，T， ；}
每个字符出现的频率是W={ 2，4， 2，3， 3 }
各字符编码是 方法：
T ； A
C
S
0
14
1
00 01 10 110 111
6 8 （1）用{ 2，4， 2，3， 3 }作为叶子结点的权值生成一棵哈 上述电文编码： 0 1 0 1 夫曼树，并将对应权值wi的叶子结点注明对应的字符； 11010111011101000011111000011000 3 3 4 4 （2）约定左分支表示字符“0”，右分支表示字符‘1’ 1 T ; A 0 注意：编码的总长度恰好为哈夫曼树的带权路径长。 （3）从叶子结点开始，顺着双亲反推上去，直到根结点，路 2 径上的‘0’或‘1’连接的序列就是结点对应的字符的二进制 2 C S 编码的逆序。
a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36
2012-12-12
5
树的带权路径长度记作：
WPL
k 1 其中：Wk为树中每个叶子结点的权；
WK LK
n
L k为每个叶子结点到根的路径长度。
a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36
WPL最小的二叉树就称作最优二叉树或哈夫曼树 。
2012-12-12
6
哈夫曼树 （最优树）
加权路径长度最小的二叉树就 是哈夫曼树。
公式：
WPL
k 1
WK LK
n
a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36
c 4 d
2
7 a 5 b
a b 7 5 WPL=7*3+5*3+2*1+4*2=46
用有值图可以表示两座城市之间的距离、车费、或 班次数目。 表示城市之间建立的通讯网络 可以描述化学结构式。
图中两点之间的最短距离问题。
2012-12-12
35
作业： P77 第26题、第28题
第30题（1）、（2）、(3) 第31题（1）、（2）、（3）
2012-12-12
36
26. 1100
数据，仅需进 行22000次比 再将每一比较框的两次比较改为一 较。
80≤a<90 60≤a<70
次，可得到（c)判定树。
a<60
(b)
(c)
2012-12-12
3、哈夫曼树的构造
10
例：给定权值{7，5，2，4}，构造哈夫曼树。
7 5
6
方法： 7 5 2 4 c d （1）由原始数据生成森林； a b c d (2) 在森林中选取两棵根结点权值最小的和次小的二 (b) (a) 叉树作为左右子树构造一棵新的二叉树，其根结点的 18 权值为左右子树根结点权值之和。规定左子树根结点 的权值小于右子树根结点的权值。 11 7 11 7 a （3）将新的二叉树加入到森林F中，去除原两棵权值 最小的树； b b （4）重复2、3步骤，直至F中只剩一棵树为止。 5 5 c d c (c) (d) 2
图的邻接表表示法：即对图中每个顶点建立一个单链表，第i个 单链表中的结点表示依附于该顶点Vi的边（或弧）
1 3 ∧ 4 ∧ 4 ∧ 1 ∧
V1
V3
2 3
V2
V4
4
V1
V3
1 2 3
2 1 1 ∧
3 4 ∧
4 ∧
V2
V4
4
1
2 ∧
2012-12-12
34
2.6.3 图的应用
图的应用非常广泛，例如：
用图可以表示一座城市的交通联系的情况；
18
0 0 23 0 11 0 1 1
1 1 1 1 1 2 3 4 5 6 7 8
HC
0110 10 1110 1111
1
29
0
014 0532012-12-12
7
8
110 0 0 0111 0 10
19
6.8 树的计数
• 称二叉树T和T'相似是指:二者都为空树或者 二者均不为空树,且它们的左右子树分别相似. • 称二叉树T和T‘等价是指:二者不仅相似，而 且所有对应结点上的数据元素均相同. • 对给定的二叉树,其先序遍历、中序遍历和 后序遍历都是唯一的。反过来是否唯一呢？ • 结论是任意前序和中序遍历确定后，这棵 二叉树也就唯一确定了。
2012-12-12
6 d 4
11
• 例一： • 假设需传送的电文为“ABACCDA”，只有四个字符， 则用2位字符串即可以分辨。 • 设：A:00 B : 01 C : 10 D : 11 • 则：要传送的电文为：00010010101100 • 接收端用二位一分进行译码。