数据结构课ppt霍夫曼树课件

1、2022-1-2016.6哈夫曼树及其应用哈夫曼树及其应用1、哈夫曼树、哈夫曼树 树的路径长度的概念：树的路径长度的概念： 从一个结点到另一个结点之间的分支数从一个结点到另一个结点之间的分支数目称为这对结点之间的路径长度。目称为这对结点之间的路径长度。 树的路径长度是从树的根到每一结点的树的路径长度是从树的根到每一结点的路径长度之和。路径长度之和。 从树中一个结点到另一个结点之间的分从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。支构成这两个结点之间的路径。2022-1-2021 12 2453 367PL=0+1+1+2+2+2+2=10树的路径长度用树的路径长度用PLPL表示

2、。表示。2022-1-2031 12 2453 367PL=0+1+1+2+2+2+2=101 12 245C67PL=0+1+1+2+2+3+3=12树的路径长度用树的路径长度用PLPL表示。表示。2022-1-204 结点带权的路径长度：结点带权的路径长度： 从该结点到树根之间的路径长度与结点上权的乘积。从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树的带权路径长度： 树中树中叶子叶子结点带权路径长度之和。结点带权路径长度之和。 abcd7524WPL=7*2+5*2+2*2+4*2=362022-1-205树的带权路径长度记作：树的带权路径长度记作： 其中：其中：Wk为

3、树中每个叶子结点的权；为树中每个叶子结点的权； L k为每个叶子结点到根的路径长度。为每个叶子结点到根的路径长度。nkKLKWWPL1abcd7524WPL=7*2+5*2+2*2+4*2=36WPL最小的二叉树就称作最小的二叉树就称作最优二叉树或哈夫曼树最优二叉树或哈夫曼树 。2022-1-206abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35 哈夫曼树哈夫曼树 （最优树）（最优树）加权路径长度最小的二叉树就加权路径长度最小的二叉树就是哈夫曼树。是哈夫曼树。公式

4、：公式：nkKLKWWPL12022-1-2072、哈夫曼树的应用、哈夫曼树的应用判定树判定树在解决某些判定问题时，利用哈夫曼树可以得到最在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。佳判定算法。例例1 将学生百分成绩按分数段分级的程序。将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图（若学生成绩分布是均匀的，可用图（a)二叉树结构二叉树结构来实现。来实现。 a60 a70 a80 a90 不及格不及格中等中等良好良好优秀优秀及格及格YNYNYNYN(a)输入输入10000个个数据，则需进数据，则需进行行30000次比次比较。较。2022-1-208 a60 a70

5、a80 a90 不及格不及格中等中等良好良好优秀优秀及格及格YNYNYNYN(a)输入输入10000个个数据，则需进数据，则需进行行31500次比次比较。较。分数分数0596069707980899099比例比例0.050.150.40.30.10 学生成绩分布不是均匀的情况：学生成绩分布不是均匀的情况：2022-1-209分数分数0596069707980899099比例比例0.050.150.40.30.10 70a 80 a60 及格及格中等中等良好良好 80a90 60a70 不及格不及格优秀优秀YNYYYNNN(b) 不及格不及格Y a90 a80 a70 a60 优秀优秀中等中等及

6、格及格良好良好YNNN(c)YYY 学生成绩分布不是均匀的情况：学生成绩分布不是均匀的情况：以比例数为权构造一棵哈夫曼树，以比例数为权构造一棵哈夫曼树，如（如（b)判断树所示。判断树所示。再将每一比较框的两次比较改为一再将每一比较框的两次比较改为一次，可得到（次，可得到（c)判定树。判定树。输入输入10000个个数据，仅需进数据，仅需进行行22000次比次比较。较。2022-1-2010675cd(b)11b57cd(c)18a711cdb5624(d)abcd7524(a)3、哈夫曼树的构造、哈夫曼树的构造例：给定权值例：给定权值7，5，2，4，构造哈夫曼树。，构造哈夫曼树。方法：方法：（1

7、）由原始数据生成森林；）由原始数据生成森林；(2) 在森林中选取两棵根结点权值在森林中选取两棵根结点权值最小的和次小的最小的和次小的二二叉树作为左右子树构造一棵新的二叉树，其根结点的叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。规定左子树根结点权值为左右子树根结点权值之和。规定左子树根结点的权值小于右子树根结点的权值。的权值小于右子树根结点的权值。（3）将新的二叉树加入到森林）将新的二叉树加入到森林F中，去除原两棵权值中，去除原两棵权值最小的树；最小的树；（4）重复）重复2、3步骤，直至步骤，直至F中只剩一棵树为止。中只剩一棵树为止。2022-1-2011 例一：

8、例一： 假设需传送的电文为假设需传送的电文为“ABACCDA”，只有四个字符，只有四个字符，则用则用2位字符串即可以分辨。位字符串即可以分辨。 设：设：A:00 B : 01 C : 10 D : 11 则：要传送的电文为：则：要传送的电文为：00010010101100 接收端用二位一分进行译码。接收端用二位一分进行译码。2022-1-2012 传送电文时，希望尽可能地缩短电文长度。 一半算法是：对每个字符设计长度不等的编码，且让电文中出现次数较多的字符尽可能采用短的编码。 需传送的电文为需传送的电文为“ABACCDA” 。 设：设：A:0 B : 00 C : 1 D : 01 则：要传送

9、的电文为：则：要传送的电文为：000011010出现译码问题出现译码问题2022-1-2013 若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种码称作前缀编码。 可以使用二叉树来设计二进制的前缀编码。2022-1-2014 设计电文总长最短的二进制前缀编码即设计电文总长最短的二进制前缀编码即以以n种字符出现的频率作权，设计一个哈种字符出现的频率作权，设计一个哈夫曼树的问题。夫曼树的问题。 哈夫曼编码哈夫曼编码-利用哈夫曼树构造通讯中利用哈夫曼树构造通讯中的电文编码（前缀码）。的电文编码（前缀码）。2022-1-2015146833442200001111T;A

10、CS各字符编码是各字符编码是 T ； A C S 00 01 10 110 111上述电文编码：上述电文编码：11010111011101000011111000011000方法：方法：（1）用）用 2，4， 2，3， 3 作为叶子结点的权值生成一棵哈作为叶子结点的权值生成一棵哈夫曼树，并将对应权值夫曼树，并将对应权值wi的叶子结点注明对应的字符；的叶子结点注明对应的字符；（2）约定左分支表示字符约定左分支表示字符“0”，右分支表示字符，右分支表示字符1（3）从叶子结点开始，顺着双亲反推上去，直到根结点，路）从叶子结点开始，顺着双亲反推上去，直到根结点，路径上的径上的0或或1连接的序列就是结点

11、对应的字符的二进制连接的序列就是结点对应的字符的二进制编码的编码的逆序逆序。例例2：要传输的电文是要传输的电文是CAS；CAT；SAT；AT要传输的字符集是要传输的字符集是 D=C，A，S，T， ；每个字符出现的频率是每个字符出现的频率是W= 2，4， 2，3， 3 注意：编码的总长度恰好为哈夫曼树的带权路径长。注意：编码的总长度恰好为哈夫曼树的带权路径长。2022-1-2016 已知某系统在通信联络中只可能出现8种字符，其概率分别为：0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11。试设计哈夫曼编码。529781423311A B C D E F G H2022

12、-1-20175297814233112022-1-2018532311178291400000001111110 1 1 012345678 1 01 1 1 01 1 1 1 1 1 00 00 1 1 10 1 0HC2022-1-20196.8 树的计数 称二叉树T和T相似是指:二者都为空树或者二者均不为空树,且它们的左右子树分别相似. 称二叉树T和T等价是指:二者不仅相似，而且所有对应结点上的数据元素均相同. 对给定的二叉树,其先序遍历、中序遍历和后序遍历都是唯一的。反过来是否唯一呢？ 结论是任意前序和中序遍历确定后，这棵二叉树也就唯一确定了。2022-1-2020例6-5 已知结点

13、的前序序列和中序序列，求整棵二叉树。 前序序列：A B C D E F G 中序序列：C B E D A F GACBEDFGABCDEFGABCFDEG2022-1-2021 给定一个前序序列，能否唯一确定一个二叉树？ 否。 n个结点的有多少不同形态的二叉树的数目？ 不同形态的二叉树的数目恰好是前序序列均为1，2，n的二叉树所能得到的中序序列的数目。 前序序列均为1，2，n所能得到的中序序列的数目恰为数列1，2，n按不同顺序进栈和出栈所能得到的排列的数目。 这个数目为: (1/（n+1）)*C2nn。2022-1-2022 n个结点的有多少不同形态的树的数目？ 已知：一棵树可转换成唯一的一棵

14、没有右子树的二叉树。 结论：具有n个结点有不同形态的树的数目和具有n-1个结点互不相似的二叉树的数目相同。2022-1-20232.6.1 图的基本概念图的基本概念2.6 图图BACD63215顶点顶点: :图中的数据元素图中的数据元素V V表示表示顶顶点的非空有限集合。点的非空有限集合。VRVR表示两个表示两个顶顶点之间关系的集合。点之间关系的集合。2022-1-2024若若属于属于VRVR，则，则表示从表示从v v到到w w的一条的一条弧，且称弧，且称v v为弧尾，为弧尾，w w为弧头。此时的图称为为弧头。此时的图称为有向图。有向图。图图有向图有向图无向图无向图若若属于属于VRVR，必有，

15、必有，即，即VRVR是对称的，是对称的，则以无序对则以无序对(v,w)(v,w)代替这两个有序对，表示代替这两个有序对，表示v v和和w w之间的一条边。此时的图称为有向图。之间的一条边。此时的图称为有向图。2022-1-2025在有向图中，在有向图中，V 表示从表示从V V1 1到到V V3 3的一条弧。的一条弧。 V V1 1为弧尾或初始点，为弧尾或初始点，V V3 3为弧头或终端点。为弧头或终端点。在无向图中，在无向图中，(V(V1 1，V V3 3) )表示表示V V1 1和和V V3 3之间的一条边之间的一条边。V1V3V2V4V1V3V2V42022-1-2026V1V3V2V4V

16、1V3V2V4顶点集合V=V1 ， V2 ， V3 ， V4 弧的集合G=, , , 顶点集合V=V1 ， V2 ， V3 ， V4 边的集合E=(V1, V3), (V1, V2), (V1, V4),(V2, V4)G=( V, E )(V1, V3)与 (V3, V1)表示同一条边2022-1-2027 对于无向图，边的数目e的取值范围是： 01/2*n(n-1) 有1/2*n(n-1)条边的无向图称为完全图。 对于有向图，弧的数目e的取值范围是： 0n(n-1) 有n(n-1)条弧的有向图称为有向完全图。 有很少边或弧的图称为稀疏图；反之称为稠密图。2022-1-2028BACD632

17、15权：与图的边或弧相关的数。权：与图的边或弧相关的数。网：带权的图。网：带权的图。顶点的度：依附于该顶点的边数或弧数。顶点的度：依附于该顶点的边数或弧数。出度：（仅对有向图）以该顶点为尾的弧数。出度：（仅对有向图）以该顶点为尾的弧数。入度：（仅对有向图）以该顶点为头的弧数。入度：（仅对有向图）以该顶点为头的弧数。路径：顶点路径：顶点A A与顶点与顶点C C之间存在一条路径。路之间存在一条路径。路径上边或弧的数目称为该路径的路径长度。径上边或弧的数目称为该路径的路径长度。2022-1-2029 （1）图的连接矩阵表示法）图的连接矩阵表示法 （2）图的邻接表示法）图的邻接表示法2.6.2 图的存

18、储结构图的存储结构2022-1-2030V1V3V2V4V1V3V2V4 V1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0图的连接矩阵表示法图的连接矩阵表示法2022-1-2031邻接矩阵表示法对求顶点的度很方便。邻接矩阵表示法对求顶点的度很方便。在无向图中：在无向图中：顶点的度数顶点的度数= =矩阵中对应该顶点的行矩阵中对应该顶点的行或或列中非列中非零元素的个数。零元素的个数。在有向图中：在有向图中：顶点的出度顶点的出度

19、= =矩阵中对应该顶点的矩阵中对应该顶点的行行中非零元中非零元素的个数。素的个数。顶点的入度顶点的入度= =矩阵中对应该顶点的矩阵中对应该顶点的列列中非零元中非零元素的个数。素的个数。2022-1-2032V1V3V2V4V1V3V2V4 V1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0入度入度 出度出度1 11 11 11 12 12 10 10 1度数度数3 3 2 2 1 1 2 2 2022-1-2033V1V3V2V4 1 2 3 4 211134 42134 1