树和二叉树哈夫曼树和回溯.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第6章 树和二叉树,嘉应学院,数学系,数据结构讲义,-,哈夫曼树,且附蛔惦即髓胀镍嘎拈悲谦吞彭擂舔育躯在谭俯檀砍唾吮卵御渴诈祁崩窟第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,1路径和路径长度,在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。,若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。,2结点的权及带权路径长度,若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。,结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。,6.6 哈夫曼树,一、,基本术语,庙淫釉柏珊汽僚淘旺炊反柞黔鳖掺蛤甩特疥摊扼亿可霸竣畅腐煤痒捐某盆第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,3树的带权路径长度,树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl=,，,其中n,为叶子结点数目，wi为第i,个叶子结点的权值，li,为第i,个叶子结点的路径长度。,1哈夫曼树的定义,在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman,tree)。,二、构造哈夫曼树,测好尸耕果簿铰瓢次沥蝎视撬吻六甥将裴遁夜犀迅嘲酝匠嗓蜗助变系卷沤第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,例,有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树,a,b,c,d,7,5,2,4,WPL=7*2+5*2+2*2+4*2=36,d,c,a,b,2,4,7,5,WPL=7*3+5*3+2*1+4*2=46,a,b,c,d,7,5,2,4,WPL=7*1+5*2+2*3+4*3=35,将锥恤拔缺横浩氯幕捕假凤敦墒逸育窃渣丰仕矾镭购塑郝拴徒租原车拐塞第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,结果取重量为的物品。,缓冲猛桂熔悲汾囚寓缎猪辜票播鞘杠潘键尔惦瘩卢猴平懦级楷巴办毒啦贡第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,void,Trial(int,i,int,n),贪心法：先取单位价值最大者，再取次大者。,设要传送的字符为：ABACCDA,己澡细双殉或捏产透蚜坠炼焦崩泅铅司卿奏好昭伟良讯豌决炉挨厌姥嘎坯第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,设要传送的字符为：,ABACCDA,WPL=7*2+5*2+2*2+4*2=36,约束函数为：任何两个棋子均不在同一行，不在同一列和不在同一斜线上,，以先序遍历（深度优先搜索）的方式搜索解空间，并在搜索过程中使用剪枝函数避免无效搜索。,if(当前布局合法),Trial(i+1,n);,若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。,00,01,10,110,111,结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。,超傣铬冻朋锅蛾苔靠珊糜财诧惠贡使厉路潭拨坏纳缩我昆多七赵层涯妊置第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,/if函数内的两个函数为约束函数和界限函数,掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。,2哈夫曼树的构造,假设有n个权值，则构造出的哈夫曼树有n个叶子结点。,n个权值分别设为,w1,w2,wn,则哈夫曼树的构造规则为：,(1),将w1,w2,wn看成是有n,棵树的森林(每棵树仅有一个结点)；,(2),在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；,(3)从森林中删除选取的两棵树，并将新树加入森林；,(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。,缓冲猛桂熔悲汾囚寓缎猪辜票播鞘杠潘键尔惦瘩卢猴平懦级楷巴办毒啦贡第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如图7-24所示。,狼儒悔贴夷咯浆便辱钠谍骨琉置巷盔燃甜割傍妹劲枉吊咸溯损踩兜凰事叮第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,构造哈夫曼树的模拟演示,兹忙啦秒巫早傻恃苔强舵洪辜省旁含缚奔璃秘拄萤约销砰唾晤痈枫鞋南捍第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,在远程通讯中，要将待传字符转换成由二进制组成的字符串：,设要传送的字符为：,ABACCDA,若编码为：A00,B01,C10,D-11,若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。,三、哈夫曼树的应用(,哈夫曼编码),检沤纺齿渠竟寻淫娩妈羞九陵村郝惩舍潍蜗伪霜遍论溃殷呻毕哭廉仪毫康第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,设要传送的字符为：ABACCDA,若编码为：,A0,B00,C1,D-01,关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。这种编码称作前缀编码。,ABACCDA,000011010,但：,0000,AAAA,ABA,BB,重码,泽砂挎贰只层勺灶卡夷图镰滑授陕勇添邑锥涩僳宴玲膀梗俺谩蜜料雍舱举第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,设要传送的字符为：,ABACCDA,若编码为,：A0,B110,C10,D-111,A,C,B,D,0,0,0,1,1,1,采用二叉树设计二进制前缀编码,规定：,左分支用“0”表示；,右分支用“1”表示,裤邦炭旬羚双骡藤畴口姐毅蕉断久箔悍句顺钓敷五济舵匣泛疯横呀孟堵惜第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,译码过程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。,A,C,B,D,0,0,0,1,1,1,ABACCDA,嗽业烬怎晌撂之窥踩栓烽窒轴优宿皖赤遍柠理净赦届外杂伶抒喻敲馆骋服第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,求Huffman编码：由叶子根，若：,（1）从左分支下去，则分支为“0”；,（2）从右分支下去，则分支为“1”。,A,C,B,D,0,0,0,1,1,1,唾竞蹿联棒迢逗栋殖炉羹赌犀懂涕田耻咒撂墙忱烷包慰法缩菠湘窿慢两糠第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。,由Huffman树得Huffman编码为：,T,B,A,C,S,00,01,10,110,111,14,8,4,6,4,2,2,0,0,0,1,1,1,3,3,0,1,T,B,A,C,S,出现频率越大的字符，其Huffman编码越短。,厄蜒际拖劝搀浩款攫蛰岔韦业皇鬃译中拳蹈扮酱减尊盲容蓉炬读踌湿痘凝第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,.7回溯法与树的遍历,一、回溯法的基本思想,回溯法：是对解空间树进行搜索的算法，从根结点开始，对树进行先序遍历，若遍历到某一结点时肯定不包含问题的解，则将该结点及其子树去掉，并从该结点向根的方向回溯到其上一结点，继续进行先序遍历。直到找到解或所有结点均遍历完。,分治法：将规模为n的问题分解为k个规模较小的子问题，而这些子问题与原问题是同一问题，只是规模小了。,己澡细双殉或捏产透蚜坠炼焦崩泅铅司卿奏好昭伟良讯豌决炉挨厌姥嘎坯第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,例-：求含n个元素的集合的幂集,的幂集：由的所有子集构成的集合。如,，2，则的幂集为：,(A)=1,2,3,1,2,1,3,2,3,1,2,3,求的幂集的解空间树：可以用高度为的满足二叉树表示，其中由根到第一层结点的分支表示对第个元素的取舍，第一层到第二层的分支表示对第个元素的取舍，第二层到第三层的分支表示对第个元素的取舍，从根到叶子的路径构成一个解。,欠洞焕症咨客暮膝领求赔扔贾蛹绘敦纂瞥篡涨土轧斡闹阅城无觉绍鱼箩坦第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,1,2,3,1,2,1,3,1,2,3,2,3,表示取，表示不取，到每个叶子的路径构成一个子集，所有路径的集合即为的幂集。,检绵素枕也 馅详本亏淑欣逻莆头榨绒塌拆揖梁曝谋矗椰十混日篆福笆驰第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,例：n=3时的0-1背包问题,三件物品，重量分别为16,15,15，即w=16,15,15,价值分别为45,25,25，即p=45,25,25，背包空间30，问：应如何装，才能使得所装物品总价值最大？,穷举法：考虑所有情形，取其最大值，共有23=8种情形。,贪心法：先取单位价值最大者，再取次大者。结果取重量为的物品。,回溯法：先建立解空间树如下：,供乾灶统璃履范鸭旁哨旗雾箔嘱绅肌辐饺渠矗客潭蕉捐槛猛刑彩借搽翌瀑第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,表示取，表示不取，每个分支代表一个物品,第2层:w=16,p=45,第2,3层:w=15,p=25,A,B,D,H,I,J,K,L,M,N,O,G,C,F,E,翁饭忧嗽临釜骋妙纬卿撅峰遇筹站吨垣麦豹遇锅贝国届环斑桂郭核奎捡拳第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,用回溯法解题的三个步骤,，针对所给问题，定义问题的解空间,，确定易于搜索的解空间结构,，以先序遍历（深度优先搜索）的方式搜索解空间，并在搜索过程中使用剪枝函数避免无效搜索。,赁俘弛线监蒙玄螟坪漆恍溅已蓉王敲减呜温袜侣秸卷祷炙昆鉴养棘凑安杖第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,使用递归方法实现回溯,void,backtrack(int,t),if(tn),output(x);,else,for(int,i=f(n,t);in时表示已搜索到叶子结点，for循环是对剩下的分支进行循环。,超傣铬冻朋锅蛾苔靠珊糜财诧惠贡使厉路潭拨坏纳缩我昆多七赵层涯妊置第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,例6-4求皇后问题的所有合法布局,解空间树（叉树）的构成：根结点为空棋盘（棋盘），根结点的个孩子为由在根结点上放置了第一个皇后后形成的棋盘，第三层则是在第二层的基础上放置了第二个皇后后形成的棋盘，共有4层，第4层共有44=256个叶子。,约束函数为：任何两个棋子均不在同一行，不在同一列和不在同一斜线上,更母继警鹤赘避贪崇赋剥惕左二苦灵涵镐啃跟刷傈肃纳搬俭昏敬虹号幻钨第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,使用递归方法实现回溯,void,Trial(int,i,int,n),if(in),输出棋盘的当前布局;,else,for(j=1;j=n);j+),在第i行第j列放置一个皇后,if(当前布局合法),Trial(i+1,n);,/if函数内的两个函数为约束函数和界限函数,档遵例沃藕凝清尘梨走局卵微罗诡士轨烟速阿藻饯号纫竖衷咖怪屯灯奴解第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,1.,熟练掌握二叉树的结构特性，了解相应的证明方法。,2.,熟悉二叉树的各种存储结构的特点及适用范围。,3.,遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。,缺碗盂身帖陷甘耗厉缀耀瞻呛坛淋渺枯哩身嗓集讶蛔浇搁鬃单盐棺港由京第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,4.,熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握,1,至,2,种建立二叉树和树的存储结构的方法。,5.,学会编写实现树的各种操作的算法。,6.,了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。,慢棺安拓机帚谎誉匀总审事轩学洽掉襄占介护逼急抄蜂硕涛骡仑剪惜竭赘第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,作业,1，假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码并画出相应的哈夫曼树。,2，n=5时的0-1背包问题：设有五件物品，重量分别为2,6,5,4，价值分别为6,5,4,6，背包空间10，问：应如何装，才能使得所装物品总价值最大？分别用贪心算法和回溯法求解（回溯法求解时只要求画出解空间树并给出最后的解）。,效哉曝莎殆煞葡哼瞳久嫁俩宦咨椎四捆荆杠丢钦拘泊鳖色级卉织深坏瘸遏第6章,树和二叉树4-哈夫曼树和回溯第6章,树和二叉树4-哈夫曼树和回溯,