12哈夫曼树及其应用

第六章（续）哈夫曼树及其应用设有10000个学生某门课程的考试成绩的分布如下表所示：一、问题的提出分数0~5960~6970~7980~8990~100学生比例数0.050.150.400.300.10学生成绩数据分布情况表*问题：现在要编写程序依次根据每个学生的成绩打印出该学生的成绩等级。分数0~5960~6970~7980~8990~100学生比例数0.050.150.400.300.10学生成绩数据分布情况表方法1：a60打印bad“yesa70no打印passyesa80no打印generalyesa90no打印goodyes打印excellentno5%的学生15%的学生40%的学生30%的学生10%的学生共做31500次比较读取一个学生成绩→a循环一万次i=1i=10000N结束i=i+1分数0~5960~6970~7980~8990~100学生比例数0.050.150.400.300.10学生成绩数据分布情况表方法2：a80打印badyesa90noyesnoa70yesnoa60yesno打印“good打印excellent打印pass打印general5%的学生15%的学生40%的学生30%的学生10%的学生读取一个学生成绩→a循环一万次i=1i=10000N结束分数0~5960~6970~7980~8990~100学生比例数0.050.150.400.300.10学生成绩数据分布情况表方法2：a80打印badyesa90noyesnoa70yesnoa60yesno打印“good打印excellent打印pass打印general5%的学生15%的学生40%的学生30%的学生10%的学生共做22000次比较读取一个学生成绩→a循环一万次i=1i=10000N结束思考：如何找到一棵最优的判断树使得编写出来的程序的运行时间是最高效的？1.哈夫曼树的有关概念①结点的路径长度：从根结点沿某条路径到某结点途中所经历的弧的条数称为该结点的路径长度。二、哈夫曼树及其应用②树的路径长度：从根结点到每一个叶子结点的路径长度之和。④树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和称为树的带权路径长度。③结点的带权路径长度：某结点的路径长度与该结点上的权值的乘积称为该结点的带权路径长度。1.哈夫曼树的有关概念二、哈夫曼树及其应用实例：已知某二叉树的四个叶子结点a,b,c,d分别带权7，5，2，4，则可构造出有如下几种不同形式的二叉树：aaa777b5b5c2d4c2d4b5c2d4树的带权路径长度为：WPL=2*7+2*5+2*2+2*4=36树的带权路径长度为：WPL=2*4+3*7+3*5+1*2=46树的带权路径长度为：WPL=1*7+2*5+3*2+3*4=351.哈夫曼树的有关概念二、哈夫曼树及其应用⑤哈夫曼树的定义：设有n个叶子结点的二叉树，其第i个叶子结点的权值为wi(i=1,2,3,...n),且第i个叶子结点的路径长度为li,则使WPL=∑wi*li最小的二叉树称为“最优二叉树”或称为“哈夫曼树”。i=1nn2.哈夫曼树的求解过程二、哈夫曼树及其应用①问题：已知n个叶子的权值为{w1,w2,...wn}，构造一棵最优二叉树。2.哈夫曼树的求解过程二、哈夫曼树及其应用②方法：步骤1:构造一个具有n棵二叉树的森林F={T1,T2,......,Tn}，其中Ti是只有一个根结点且根结点的权值为wi的二叉树。步骤2:在F中选取两棵其根结点的权值最小的二叉树，从F中删除这两棵树，并以这两棵二叉树为左右子树构造一棵新的二叉树添加到F中，该新的二叉树的根结点的权值为其左右孩子二叉树的根结点的权值之和。步骤3:判断F中是否只有唯一的一棵二叉树。若是，则求解过程结束；否则，转步骤2。2.哈夫曼树的求解过程二、哈夫曼树及其应用③实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e15152.哈夫曼树的求解过程二、哈夫曼树及其应用③实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e15152.哈夫曼树的求解过程二、哈夫曼树及其应用③实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e1515302.哈夫曼树的求解过程二、哈夫曼树及其应用③实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e151530602.哈夫曼树的求解过程二、哈夫曼树及其应用③实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e151530601003.哈夫曼编码二、哈夫曼树及其应用①等长编码：以英文字符编码为例，一般英文字符编码是采用7位二进制数编码（ASCII码）。7位二进制数可以为27个不同的英文字符编码。下面为讨论问题简单起见，假设被编码的字符集中只有4个（即22个）不同字符，故只要两位二进制数即可完成编码。设这4个不同的字符为A，B，C，D，则可进行等长编码如下：3.哈夫曼编码二、哈夫曼树及其应用①等长编码：设这4个不同的字符为A，B，C，D，则可进行等长编码如下：3.哈夫曼编码二、哈夫曼树及其应用①等长编码：设这4个不同的字符为A，B，C，D，则可进行等长编码如下：A:00B:01C:10D:11则对于电文“ABACCDA”的二进制电码为：00010010101100总长为14位译码时，两位一分进行译码，可唯一得到电文：ABACCDA。3.哈夫曼编码二、哈夫曼树及其应用②压缩编码：即采用不等长的编码方案，将“高频字符”的编码设计得尽可能短一些，把最长的编码留给“低频字符”。例如：对于刚才的4个字符的编码问题，可以按如下不等长编码方案进行编码：A:0B:00C:1D:01问题：译码时可能出现多意性，即译码不唯一：则对于电文“ABACCDA”的二进制电码为：000011010总长为9位3.哈夫曼编码二、哈夫曼树及其应用②压缩编码：例如：对于刚才的4个字符的编码问题，可以按如下不等长编码方案进行编码：A:0B:00C:1D:01问题：译码时可能出现多意性，即译码不唯一：则对于电文“ABACCDA”的二进制电码为：000011010总长为9位3.哈夫曼编码二、哈夫曼树及其应用②压缩编码：例如：对于刚才的4个字符的编码问题，可以按如下不等长编码方案进行编码：A:0B:00C:1D:01问题：译码时可能出现多意性，即译码不唯一。则对于电文“ABACCDA”的二进制电码为：000011010总长为9位如000011010中的前4个0的译码会有如下几种不同译码：0000→AAAA；0000→ABA；0000→BB思考：如何解决这一问题？问题的关键在于编码是否为无前缀编码。3.哈夫曼编码二、哈夫曼树及其应用③无前缀压缩编码（既哈夫曼编码）：*思想：利用哈夫曼树设计出来的不等长的编码方案一定是无前缀的。*方法：步骤1：将各字符按照其“出现频率”的统计数字安排一个“权值”并作为“叶子”，然后求出相应的哈夫曼树；步骤2：树中各结点到其左孩子的边上的权值设为0、到其右孩子的边上的权值设为1（即所谓左0右1）；步骤3：从根开始到“叶子”所经历的边上的数值的序列即为该“叶子”所对应的字符的编码。三、实例已知某通信用电文仅由A、B、C、D这4个字符构成，其出现的频率分别为：8、4、6、2，请给出它们的哈夫曼编码，要求写出相应的哈夫曼树。解：根据哈夫曼算法，求得哈夫曼树如下：208122664BDAC010101从根开始到叶子得各字符的哈夫曼编码如下：A:0B:100C:11D:101则对于电文“ABACCDA”的二进制电码为：0100011111010总长为13位三、实例补充内容：用一维数组存放单链表——静态链表李赵孙周郑吴王钱A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李赵孙周郑吴王钱A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李赵8孙周郑吴王钱A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李赵8孙周郑吴王钱3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李赵8孙1周郑吴王钱3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周郑吴王钱3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑吴王钱3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑吴5王钱3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王钱3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱3A0123456789在“孙”的前面插入一个“史”：三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱3史A0123456789在“孙”的前面插入一个“史”：三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱3史A0123456789在“孙”的前面插入一个“史”：三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱3史3A0123456789在“孙”的前面插入一个“史”：三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱3史3A0123456789在“孙”的前面插入一个“史”：三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱3史3A0123456789在“孙”的前面插入一个“史”：三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱9史3A0123456789在“孙”的前面插入一个“史”：删除“周”时表的变化：2李4赵8孙1周6郑7吴5王0钱9史3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱9史3A0123456789在“孙”的前面插入一个“史”：删除“周”时表的变化：2李4赵8孙1周6郑7吴5王0钱9史3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱9史3A0123456789在“孙”的前面插入一个“史”：删除“周”时表的变化：2李4赵8孙1周6郑7吴5王0钱9史3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱9史3A0123456789在“孙”的前面插入一个“史”：删除“周”时表的变化：2李6赵8孙1周6郑7吴5王0钱9史3A0123456789三、实例补充内容：用一维数组存放单链表——静态链表2李4赵8孙1周6郑7吴5王0钱3A01234567892李4赵8孙1周6郑7吴5王0钱9史3A0123456789在“孙”的前面插入一个“史”：删除“周”时表的变化：2李6赵8孙1周6郑7吴5王0钱9史3A012