《十章节树与有序树》由会员分享，可在线阅读，更多相关《十章节树与有序树（54页珍藏版）》请在金锄头文库上搜索。
1、第十章 树与有序树10.1 树的基本概念树的基本概念10.2 连通图的生成树和带权连通图的连通图的生成树和带权连通图的最小生成树最小生成树 10.3 有序树有序树10.4 前缀码和最优二分树前缀码和最优二分树 庚酪绑伊戒惟啮翱舌臂加撼亿眼酱菱嫌避绷敢耍渺醒瓣贼畔虹泥偷势狈赚十章节树与有序树十章节树与有序树1家谱PeterGodfriedBettyAlbertMaryMarivinDorisJudyHalDeniseGregory一般假定在孩子是按年龄排序的一般假定在孩子是按年龄排序的, 则这种树是有序的。则这种树是有序的。鬃鸯佬逻篆油邯赦领粗畅搭洛捻驳铱置辫桶航瓢辫蜡陨渊脱金脉宁解综乳十章节树
2、与有序树十章节树与有序树2语法树语法树“The big elephant ate the peanut”语法图解如下：语法图解如下：赫聂掺只澎左绷两些札侣转赢烘姓槛坪灭散劲刺忠言爷匹阴哇槛迫昨啥慢十章节树与有序树十章节树与有序树3有向树定义定义1 一个有向图，若去掉边的方向，所得无向图一个有向图，若去掉边的方向，所得无向图是一棵树，则称这个有向图为有向树。是一棵树，则称这个有向图为有向树。(a)(b)例例 两个有向树的例子。两个有向树的例子。今后只讨论今后只讨论(b)这样的所谓的这样的所谓的“根树根树”有一个根的树。有一个根的树。猫鹃易薯条摇刻郝华惰巳幅种坏八眶坐辫珐积喀佛谓弄遁梢层沪匀屑妓瞎
3、十章节树与有序树十章节树与有序树4根树根树设设T=(V,E)是一棵有向树，若仅有一个顶点的入度为是一棵有向树，若仅有一个顶点的入度为0，其余的顶点的入度均为其余的顶点的入度均为1，这样一棵有向树我们称为，这样一棵有向树我们称为根根树树。u入度为入度为0的顶点称为的顶点称为树根树根，u出度为出度为0的顶点称为的顶点称为树叶树叶，u出度不为出度不为0的顶点称为的顶点称为分枝点分枝点。 例例abcdeabcde狞捌老恫胁寇估愤北材旭鸦她诣弧索瑚诫画宿滤舔睫阎巩含咳赁垫淌汕造十章节树与有序树十章节树与有序树5例 画出4阶所有非同构的根树 树根树存行助议猴峨托序挟摇刹衫瞎时愤泣夕胡个肢哈冗搭同瞩邮臼带次
4、啼烩琴十章节树与有序树十章节树与有序树6例 画出5阶所有非同构的根树 树根树把亨脏抵栋疑遭诡哇桌坝游缘橱辞爆惹突蛀警范信摔砾勃悟煤韧砷吴堑络十章节树与有序树十章节树与有序树7父亲、儿子、祖先、后代、兄弟父亲、儿子、祖先、后代、兄弟设设T=(V,E)是一棵根树。是一棵根树。u如果如果e=(v,u) E，称，称v是是u的的父父亲亲， u是是v的的儿子儿子。u对对v1,v2V，若存在一条从，若存在一条从v1到到v2的通路，则称的通路，则称v1是是 v2的的祖先祖先，v2是是v1的的后代后代。u若若(v0，v1)，(v0，v2) E ，说说v1与与v2是是兄弟兄弟。a ab be ed di in n
5、m m奶烤芭旷那悦迭眨督漠驼硼冕试婪哀坯掘谎岂蚊三魔寞厢焕予产沼丫皖霉十章节树与有序树十章节树与有序树8子树设设T=(V,E)是一棵根树。是一棵根树。uv0V，v0是是 中一个分支点中一个分支点, 所谓所谓以以v0为根的子树为根的子树是指是指T的的一个子图一个子图T ，T 以以v0和和v0的的全部的后代为顶点，以从全部的后代为顶点，以从v0出发的所有通路经过的边为出发的所有通路经过的边为边。边。u以以v0的一个儿子为根的子树的一个儿子为根的子树称为称为v0的子树的子树。a ab be ed di in nm m酣见遗唤卵占彼坷颧怂竖粒泵皂隧纳泵配袱杂确辨系苫芽消庞戮苫招猛绍十章节树与有序树十章
6、节树与有序树9例例 试回答问题l哪个是树根哪个是树根? l哪些是树叶哪些是树叶? l哪个是哪个是e的父亲的父亲? l哪些是哪些是e的祖先的祖先? l哪些是哪些是e的儿子的儿子? l哪些是哪些是e的后代的后代? l哪些是哪些是e的兄弟的兄弟?l哪些是哪些是e的子树的子树? a ac cb be ed df fh hg gi il lk kj jn nm m匡汛权洼瓦棵赵既缎五轴烽仪甄烁爹勇轻菇沏哲鹊酷澳盖档茬笺搔匠叠治十章节树与有序树十章节树与有序树10有序树定义定义2 一棵根树，若每一个分枝点出发的边，一棵根树，若每一个分枝点出发的边， 分别标以整数分别标以整数1，2， ，k 。则称这样的根树
7、为有序树。则称这样的根树为有序树。有序树可以说是各子树从左到右是有次序的树有序树可以说是各子树从左到右是有次序的树句子句子主语主语谓语谓语形容词形容词冠词冠词名词名词The big elephant ate the peanut例例攀米周夫榨峡雏勘空藕出耶掺辈致迄双所甘磷够孩铸舌时献箩扣评魔渠载十章节树与有序树十章节树与有序树11例例需要说明的是，一棵有序树的每个分枝点出发的边的需要说明的是，一棵有序树的每个分枝点出发的边的标号并不是要求是连续的。一个分枝点出发的边，若标号并不是要求是连续的。一个分枝点出发的边，若被标上被标上i ，则称这条边是这个分枝点的，则称这条边是这个分枝点的 i子树子树
8、。如上图，一个分枝点出发的两条边被分别标上如上图，一个分枝点出发的两条边被分别标上1，3，我们说这个分枝点没有第我们说这个分枝点没有第2子树。子树。句子句子主语主语谓语谓语形容词形容词冠词冠词名词名词The elephant ate the peanut13民甥皇助蝶表神阀好年讫摸抬矿月锥酷弄竭赖葛孪勺奏邓械矛毕据沟博遍十章节树与有序树十章节树与有序树12m分树、正则分树、正则m分树分树如果一棵有序树的每个分枝点最多有如果一棵有序树的每个分枝点最多有 m个儿个儿子，称这棵有序树为子，称这棵有序树为 m分树分树。若一棵若一棵 m分树的每一个分枝点恰好有分树的每一个分枝点恰好有m 个个儿子，称这样
9、的儿子，称这样的 m分树为分树为正则正则m分树分树。蛛龙缉特旨卿琵疆尺吞盆胃圣豌啦冬朽酿丹郡投罕啪峙华灯街勾北脊劲蛾十章节树与有序树十章节树与有序树132分树分树: 左子树、右子树左子树、右子树对于对于2分树，它的每一个分枝点的第一个子树和第二分树，它的每一个分枝点的第一个子树和第二子树又分别叫子树又分别叫左子树左子树和和右子树右子树。例例 单淘汰赛的正则单淘汰赛的正则2-分树分树 邓择孪驻衡途淖汤沉谰茬戏辆悬铜虽参暴扩针穿递养趟名叮锐团肃喇耍辑十章节树与有序树十章节树与有序树14定理定理9 一棵正则一棵正则m分树的分枝点的个数为分树的分枝点的个数为i，树叶的个数，树叶的个数为为t，则有，则有
10、 (m-1)i=t-1证明：总共有证明：总共有 i个分枝点，每个分枝点有个分枝点，每个分枝点有 m个儿子，个儿子，故总的儿子数目为故总的儿子数目为 mi 。而所有的儿子包括全。而所有的儿子包括全部顶点减去一个根，即为部顶点减去一个根，即为 i+t-1，所以有：，所以有：mi=i+t-1即为即为 （m-1)i=t-1。薄海炮政累跟拳啃让描洲闯屋梨赎川稀蕊枢则北三砷斡祸啪旁赌缨货烦桔十章节树与有序树十章节树与有序树15例5 用带用带4个插座的接线板，连接个插座的接线板，连接19个灯到一个总插座上，个灯到一个总插座上，问至少需要多少块接线板。问至少需要多少块接线板。 解：任何一个连接方法都是一棵解：
11、任何一个连接方法都是一棵4分树，分树， 按定理按定理9中公式，有中公式，有 (4-1)i 191, 所以所以 i6沫囤恼样论碗杯琵殷妈弘欧逊召傀曙瑶卵劝颁藏仰心界募本椭句蛆位确磐十章节树与有序树十章节树与有序树16树形图的高度、顶点的路长树形图的高度、顶点的路长在一棵树形图中，在一棵树形图中，n一个顶点的路长规定为从树根到这个顶点的通路一个顶点的路长规定为从树根到这个顶点的通路的长。的长。n一棵树形图的高度即为该树中最长路的长度。一棵树形图的高度即为该树中最长路的长度。在一棵树形图中从树根到每一个顶点有且仅有唯一的在一棵树形图中从树根到每一个顶点有且仅有唯一的一条通路。一条通路。拄榨剩裤益肃州
12、捞猿唱致春辱者挎搭蹦著良诚钥隆逾硒沤咳妒呢相栗充极十章节树与有序树十章节树与有序树17高为高为h的正则的正则m分树分树 至少有至少有m+(m-1)(h-1)片树叶片树叶，最多有最多有mh片树叶。片树叶。锐勺送壁簇奋元盔住旦锯寿衣电也莱傲竣膊攻鸿贾后酸幌渊堑硒筏汤郊亡十章节树与有序树十章节树与有序树18例 求证一棵正则一棵正则2分树必有奇数个顶点。分树必有奇数个顶点。证明证明: 假设一棵正则假设一棵正则2分树有分树有 i个分枝点、个分枝点、t个树叶。个树叶。每个分枝点有每个分枝点有 2个儿子，故总的儿子数目为个儿子，故总的儿子数目为 2i 。而所有的儿子包括全部顶点减去一个根，所。而所有的儿子包
13、括全部顶点减去一个根，所以有：以有：2i=i+t-1即为即为i=t-1。从而全部顶点数目为从而全部顶点数目为 i+t=(t-1)+t=2t-1显然显然, 它是一个奇数，结论得证明。它是一个奇数，结论得证明。俘日棠异惟奄咯浸侍履豢褥撬眩闽厅捌亢涵嘱泉嘉刊弄虽黍心沈卷趾硼今十章节树与有序树十章节树与有序树19例 设一棵正则一棵正则2分树的顶点个数为分树的顶点个数为n, 则它的树叶个数为：则它的树叶个数为：罕班桂述风屋屈耕囊讣汐壤绽彦犯杏馈岿笑蝇裹嘿侍经虹疯眉携漆汪傍跳十章节树与有序树十章节树与有序树20例 有8枚硬币，其中恰有1枚是假币，假币比真币重。试用一架天平称出假币，使称量的次数尽可能地少。
14、 辗怪呛短扫膘癣饰奏滤拨爆范楷肌淳豪噬龟啤清登骸荚案约霉殷帆苛婴帝十章节树与有序树十章节树与有序树21例有8枚硬币，其中可能有1枚是假币（但假币不多于1枚），假币与真币重量不等。试用一架天平来称量，3次称出假币或断言假币不存在，请用根树表示你的称量策略。 皱叛蕉勾端依哲也诊川搭瑶玛弓看丛切卵码逢扳担吭终钩捆乍漠釉舱撰轩十章节树与有序树十章节树与有序树22例例 数学表达式的二分树数学表达式的二分树(二叉树二叉树)以二叉树表示数学表达式的递归定义：以二叉树表示数学表达式的递归定义：若表达式若表达式=(第一表达式第一表达式)(运算符运算符)(第二表达式第二表达式), 则则 以左子树表示第一表达式以左
15、子树表示第一表达式 以右子树表示第二表达式以右子树表示第二表达式 根结点的数据库存放运算符根结点的数据库存放运算符+ +* */ /c cd da ab b(a*b)+(c/d)+ + +d d+ +c ca ab b(a+b)+c)+d抉驱抬鸵闹尾赚郎藻借柜遁窝允夺鹃瓮从普扣篆靖人叶烙绢闹刃所覆都卷十章节树与有序树十章节树与有序树23第十章 树与有序树10.1 树的基本概念树的基本概念10.2 连通图的生成树和带权连通图的连通图的生成树和带权连通图的最小生成树最小生成树 10.3 有序树有序树10.4 前缀码和最优二分树前缀码和最优二分树 娇腿妨汰煽睬遂趋厌映膝妊准洒蛙萧映栓嫌旷没临砖漏窄图
16、岗督潭莉屉傀十章节树与有序树十章节树与有序树24英文的编码通信英文的编码通信英文的编码通信中，考察用英文的编码通信中，考察用0和和1来表示英文字母的问来表示英文字母的问题，因为字母表中的题，因为字母表中的26个字母必须用个字母必须用0和和1组成的序列组成的序列来表示，故它们可以用长度为来表示，故它们可以用长度为5位位(因因 242625)的序列的序列表示出来。表示出来。要传递一条信息，我们只要传递用来表示消息而组成要传递一条信息，我们只要传递用来表示消息而组成字母序列的一个字母序列的一个0、1字符串即可。在接收端，把这一字符串即可。在接收端，把这一0、1字符串分为长度为字符串分为长度为5位的序
17、列，而这些序列对应的位的序列，而这些序列对应的字母就可以识别出来。字母就可以识别出来。挪磐笛醇件绦娶捧延仲孕驶迸局葱夺由察掐稚笆椎愚蒜萄安须常母伶墩鹅十章节树与有序树十章节树与有序树25英文字母使用频数英文字母使用频数校炔珍今朴翘氖颗锑屹谬药渐豢频惶罕莉毕锡钒然杠抹窑蓖酥硷堆阴痢涣十章节树与有序树十章节树与有序树26数串划分问题数串划分问题当用各种不同长度的序列来表示字母时，在接收端，当用各种不同长度的序列来表示字母时，在接收端，就存在如何把一个就存在如何把一个0、1的数串划分为对应字母序列的数串划分为对应字母序列的问题？的问题？例如，如果例如，如果 00=e 01=t 0001=w 那么那么
18、 0001=?含妨币酱泽揽咀鱼诺乱缝吴艺桃神撇液癌涟崩孙祈洱米僧敬砰短鞠猛蓄僻十章节树与有序树十章节树与有序树27前缀码前缀码序列序列 a1a2am 是序列是序列 b1b2bmbm+1bn的的前缀前缀，如果，如果 a1a2am=b1b2bm。对于序列的一个集合来说，若这个集合中的任何序列对于序列的一个集合来说，若这个集合中的任何序列都不是另一个序列的前缀，则这个集合称为都不是另一个序列的前缀，则这个集合称为前缀码前缀码。例例 000, 001, 01, 10, 11 是一个前缀码是一个前缀码 1, 00, 01, 000, 0001 不是一个前缀码不是一个前缀码 0001=00+01?0001
19、=000+1?0001=0001?级漏脐好番崖国朋超酉昧瑟凑往苏尿何鸣拍榜誉鄙枕钙众库乍泣锹住部僳十章节树与有序树十章节树与有序树282分树分树 前缀码前缀码由任何一棵由任何一棵2分树可以得到一个前缀码，且对应一分树可以得到一个前缀码，且对应一个前缀码也一定存在一棵相应的个前缀码也一定存在一棵相应的2-分树。分树。 例例 10, 001, 010, 011,110 为一个前缀码。为一个前缀码。屈宠沦姐矗认即都嚼拽额猿砸桨俊性记漾吞置亨泅哩赡枫虽沮麻濒痒贡吉十章节树与有序树十章节树与有序树29前缀码前缀码 2分树分树例例 前缀码前缀码01,10,001,110 所对应的一棵所对应的一棵2分树。分
20、树。001 110 10 01 (b) 000 00 1 010 011 100 101 110 111 0 0 0 0 00 0 0 0 1 1 1 1 11 10 1 1 1 0 01 (a) 辅拂康企口邢埂物狱纵建封枝责龋川就嗣渝作奠芥宣扭怠被杠袭酉挚间郝十章节树与有序树十章节树与有序树30字符串 前缀码中的码字例例: 已知前缀码如下图已知前缀码如下图试划分下述字符串试划分下述字符串: 11001000110010001110娩甸寂寨筑乓退誉膨腾嘴愉淘闷芜嗜琵酣谚替掺即掣可塞鲜拜据亚查杂拷十章节树与有序树十章节树与有序树31一段英文所用的字符串的平均长度一段英文所用的字符串的平均长度假设
21、在假设在N个英文字母组成的短文中，英文第个英文字母组成的短文中，英文第 i个字母个字母出现的频率是出现的频率是 wi次，而第次，而第 i个字母用个字母用Li长的长的0和和1序列序列来表示，则来表示，则N个英文字母组成的一段英文所用的字符个英文字母组成的一段英文所用的字符串的平均长度为串的平均长度为 浆卒胳堕迭篇培伤鼎响叶丽少谷塌岩宁狱很轨希护彻窗馅锐妥联抬蒂歧吵十章节树与有序树十章节树与有序树322分树的分树的叶子叶子权权假如我们有一组权假如我们有一组权w w1 1,w,w2 2, ,w,wn n。不失一般性，。不失一般性，设设 0w 0w1 1ww2 2 w wn n一棵有一棵有n n片叶子
22、的片叶子的2 2分树，如果分配给它的叶分树，如果分配给它的叶子的权分别为子的权分别为w w1 1,w,w2 2, ,w,wn n，则这棵则这棵2 2分树称为分树称为叶子权为叶子权为 w w1 1,w,w2 2, ,w,wn n的的2 2分树。分树。担窃限费瑶梆漳忻莽嫂烬哮崎撼嫩攻蜘应收粳廓扮曝犊鸿次逮爷亨祝魁按十章节树与有序树十章节树与有序树332 2分树分树T T的权的权W(T)W(T)定义叶子权为定义叶子权为 w w1 1,w,w2 2, ,w,wn n的的2 2分树的权分树的权W(T)W(T)为为: : W(T) = W(T) = wwi iL(wL(wi i) )，其中其中L(wL(w
23、i i) ) 是具有权为是具有权为w wi i的叶子的路长。的叶子的路长。嘻羽描跳萄史郑军腮真溺整告旋橇褪稠摆司严脖县桔付肌朗焙塔谤涉咒铰十章节树与有序树十章节树与有序树34例例 构造构造权值分别权值分别为为7,5,2,4的的二叉树二叉树abcd75247*2+5*2+2*2+4*2=367*3+5*3+2*1+4*2=46abcd75247*1+5*2+2*3+4*3=35dcab2475味懂拌唤乘寺致少抛俗站宽怠晴双爬腥歇娄冈酞截强稗迹改遍捞蚜阿队三十章节树与有序树十章节树与有序树35最优树最优树在叶子权为在叶子权为w1,w2,wn的所有的所有2分树中，具有最小分树中，具有最小权的一棵权的
24、一棵2分树，称为分树，称为最优树最优树。12+14+33=5960例例粤旁乓滴粳绎朱胳柞赁园沪桌滑膊勘寐史型搓藻镑迂芒闯贝滁崇餐撇湖敛十章节树与有序树十章节树与有序树36霍夫曼(Huffman D.A)算法 指导思想指导思想: 把求带把求带n个权的最优树变为求带个权的最优树变为求带n-1个权的个权的最优树。最优树。外沮谍靶堰伪睹肚腋榜当承忽房增捧豁烦刽赢酚救铬轻籍浸子痹锐蕉朽区十章节树与有序树十章节树与有序树37命题命题1存在一棵带权存在一棵带权w1,w2,wn的最优的最优2分树，而且带权分树，而且带权w1和和w2的二片叶子是兄弟。的二片叶子是兄弟。a awx wya aw1 w2叼恿符伏掘授
25、修幻嘉瓣怯藻诬悄呸窖质幻胺牧致拳陨旺泣跃熟劫寨窃快龄十章节树与有序树十章节树与有序树38命题1的证明显然带权显然带权w1,w2,wn的最优的最优2分树一定存在。设分树一定存在。设T是一棵这样是一棵这样的的2分树。分树。a是是T中通路最长的分支点。中通路最长的分支点。a的两个儿子的两个儿子a1和和a2分分别带权别带权wx和和wy。由于由于T是最优的，所以每一个分枝点都有两个儿子，否则这个是最优的，所以每一个分枝点都有两个儿子，否则这个分枝点可以去掉，让它的儿子代替它，仍是一个带权的分枝点可以去掉，让它的儿子代替它，仍是一个带权的2分分树，但树的权减少了。树，但树的权减少了。设设wxwy，则有，则
26、有w1wx，w2wy。让。让a1带权带权w1，让带权，让带权w1的叶子的叶子带权带权wx，a2带权带权w2，带权，带权w2的叶子带权的叶子带权wy，我们得到一棵新的，我们得到一棵新的带权带权w1,w2,wn的的2分树，设为分树，设为T。显然，。显然， L(wx)L(w1)，L(wy) L(w2)，所以，所以，W(T)W(T)。由于是最优的，所以。由于是最优的，所以W(T)=W(T)，而，而T是是一棵带权最优一棵带权最优2分树且带权分树且带权w1与与w2的两片叶子是兄弟。的两片叶子是兄弟。暖拭盔建总卸蚤欣盂兄廷旬赤莉竖织怎辱厦擒阮健撰税礁淑醉中夹衡奈溃十章节树与有序树十章节树与有序树39命题1的
27、意义从一棵带权最优二分树，一定可以得到一棵带权最小从一棵带权最优二分树，一定可以得到一棵带权最小的两片叶子是兄弟的最优树。所以，可以设的两片叶子是兄弟的最优树。所以，可以设T是一棵是一棵带权带权w1,w2,wn的最优树，且带权的最优树，且带权w1和和w2的两片叶的两片叶子是兄弟。子是兄弟。把带权把带权w1和和w2的两片叶子去掉，让他们的父亲变成一的两片叶子去掉，让他们的父亲变成一片叶子带权片叶子带权w1+w2，这时我们得到一棵带权，这时我们得到一棵带权w1+w2 w3,w4,wn的的2分树，记为分树，记为 T。显然有显然有 W(T)=W(T)-w1-w2。权权w1+w2的路长少了的路长少了1宿
28、肌锭埔辈征损洱追牌嫉鼎诈潞大诞澜祭嗅赘汰天豫兴净谈闸涛酶敞然腊十章节树与有序树十章节树与有序树40命题2 设设T是一棵带权是一棵带权w1+w2 w3,wn的最优树，将带的最优树，将带权权w1+w2的叶子变为分枝点，让它的两个儿子分的叶子变为分枝点，让它的两个儿子分别带权别带权w1和和w2得一棵带权得一棵带权w1,w2,w3,wn的的2分树，记为分树，记为T。 T也是最优树。也是最优树。a aw1 w2a aw1+w2察哪蓬方汗瘫拿刁湖灶扼菲穷言洒嗜淘潍潘砸橙纵荚撰闯汹举装全箱踪死十章节树与有序树十章节树与有序树41命题2的证明 由已知由已知, 显然有显然有 W(T)=W(T)+ w1+w2。若
29、若T不是最优树，设不是最优树，设T*是一棵带权是一棵带权w1,w2,wn的最优的最优树且树且W(T*)W(T), 且带权且带权w1和和w2的两片叶子是兄弟。的两片叶子是兄弟。从从T*可以得到一个带权可以得到一个带权w1+w2 w3,wn 的的2分树分树T*，且有，且有W(T*)=W(T*)-w1-w2。因为因为T是带权是带权w1+w2 w3,wn的最优树，所以的最优树，所以W(T)W(T*)=W(T*)-w1-w2 于是，有：于是，有：W(T)=W(T)+w1+w2W(T*)这与假设这与假设W(T*)W(T)矛盾。矛盾说明矛盾。矛盾说明T是最优树。是最优树。然满趣筋称嚏友长彦燎触搏谱萌食盘踢长
30、常魔引劈痈华辩夜芳刚孤溃碰遏十章节树与有序树十章节树与有序树42例例 求带权求带权2,3,5,7,10最优最优2分树。分树。分析分析：等于构造：等于构造5，5，7，10的最优树；的最优树； 等于构造等于构造7，10，10的最优树；的最优树； 等于构造等于构造10，17的最优树。的最优树。腋钡隶诸概女抹菇黄旷蓟簧卵袖韧霹熊篡抚漱膝膘艇碑氮彤藕谱重西狗告十章节树与有序树十章节树与有序树43哈夫曼树的构造步骤哈夫曼树的构造步骤1) 根据给定的根据给定的n个权值个权值 ，构造，构造n棵只有一个根结点的棵只有一个根结点的二叉树，二叉树， n个权值分别是这些二叉树根结点的权。个权值分别是这些二叉树根结点的
31、权。设设F是由这是由这n棵二叉树构成的集合。棵二叉树构成的集合。2) 在在F中选取两棵根结点树值最小的树作为左、右子中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和。左、右子树根结点权值之和。3) 从从F中删除这两颗树，并将新树加入中删除这两颗树，并将新树加入F。4) 重复重复 2) 和和3)，直到，直到F中只含一颗树为止。中只含一颗树为止。屹紧仲扯推春刮伺眠茄团烙灿售肩沃呀债彤兑靶凯督轿阅林赦资冯惺账政十章节树与有序树十章节树与有序树44例例 w=5, 29, 7, 8, 14, 23, 3
32、, 11，求哈夫曼树，求哈夫曼树51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100捎励庞衫忙梅缀捐繁眺急辕纪助煎侵魄密尤彰桐匙歌敏捆鸿汀颂群颧漆拌十章节树与有序树十章节树与有序树45例例 最优判定问题最优判定问题等级分数段比例ABCDE059606970798089901000.050.150.400.300.10a60a90a80a70EYNDYNCYN
33、BYNA70a80a60CYNBYNDYNEYNA80a9060a70BACDE2755154030105*1+15*2+40*3+30*4+10*4=275EADBC20540301551040*1+30*2+15*3+5*4+10*4=205哈夫曼树哈夫曼树瞒首墟娱沽范蠢赵专殴妙阎停摆向啸簿椿初赤吠排惺净涧澄惰惠唱谊毯琢十章节树与有序树十章节树与有序树46例子例子例例 某通讯系统只使用某通讯系统只使用8种字符种字符a、b、c、d、e、f、g、h，其，其使用频率分别为使用频率分别为0.05,0.29,0.07,0.08, 0.14,0.23, 0.03,0.11。构造以字符使用频率作为权值的
34、哈夫曼树。将权值取为整构造以字符使用频率作为权值的哈夫曼树。将权值取为整数数w=(5,29,7,8,14,23,3,11)，按哈夫曼算法构造的一棵哈夫，按哈夫曼算法构造的一棵哈夫曼树如下：曼树如下：对应字符的编码对应字符的编码a: 0110a: 0110b: 10b: 10c: 1110c: 1110d: 1111d: 1111e: 110e: 110f: 00f: 00g: 0111g: 0111h: 010h: 0101）构造以）构造以 a、b、c、d、e、f、g、h为叶子结点的二叉树；为叶子结点的二叉树；2）将该二叉树所有左分枝标记）将该二叉树所有左分枝标记1，所有右分枝标记，所有右分枝
35、标记0；3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；292919195858424210010015158 8 7 7 3 3 5 5 8 8 1111232314142929abecdfhg女峨皋漏醉病皇突舒讳暇泳蓖服本嘱冒燕恢侧叁媒嘶巨局待赘品吼午绿贬十章节树与有序树十章节树与有序树47哈夫曼编码平均码长与平均压缩率哈夫曼编码平均码长与平均压缩率a: 0110b: 10c: 1110d: 1111e: 110f: 00g: 0111h: 010平均码长=4*(5%+7%+8%+3%) +3*(14%+11%) +2*(29
36、%+23%) =2.71292919195858424210010015158 8 7 7 3 3 5 5 8 8 1111232314142929abecdfhg若用这三位二进制数(07)对这8个字母进行等长编码, 等长编码的长度为3。于是，哈夫曼编码的平均压缩为： 2.7131-=1-90.3%=9.7%影默千砖速挫胸社从晌俘远勤潦芯腐枕酪味不脾寂堕肋浮渗姓闽够琵稍幻十章节树与有序树十章节树与有序树48例给定权为给定权为 1，4，9，16，25，36，49，64，87，100。构造一棵带权最优构造一棵带权最优3-分树分树(三叉树三叉树)。解解:14916253649648710014551
37、40251?岿选藩尊旅员艘岔烽轨嘶脚枷幌栓桑网状杖毛板滤示逛镐象酵爽忍酸严概十章节树与有序树十章节树与有序树49例给定权为给定权为 1，4，9，16，25，36，49，64，87，100。构造一棵带权最优构造一棵带权最优3-分树分树(三叉树三叉树)。解解:014916253649648753091200100391挑羚硼娱猾销恤廷赫稽婚斯贵忍完灰魔烷椅仿眩谴隋汇瓦梁付殆凡霓股毙十章节树与有序树十章节树与有序树50构造一棵最优 t叉树（1）首先找出）首先找出 t个最小的权值，然后对这个最小的权值，然后对这t个权值构造个权值构造出一个出一个t叉树，并对该叉树，并对该t叉树的树根置权值为叉树的树根置
38、权值为t个最个最小权值之和。依此类推，由构造过程可知，除根小权值之和。依此类推，由构造过程可知，除根外其它分支点恰有外其它分支点恰有t个儿子。个儿子。（2）如果构造出来的树跟恰好有）如果构造出来的树跟恰好有 t个儿子，那么这棵个儿子，那么这棵树就是最优树就是最优t叉树。如果构造出来的树根的儿子叉树。如果构造出来的树根的儿子数目数目kt ，那么在原来的权值中添加，那么在原来的权值中添加 (t-k) 个个0，按照步骤按照步骤(1)重新构造重新构造 t叉树，它能保证每个分叉树，它能保证每个分支点都有支点都有t 个儿子，这是最优个儿子，这是最优 t叉树。叉树。押羚尔店盔蹈肺埔泅通劲技蛛青紫雌皑咳辉畦妮
39、踊绸毋三晨塌殿之厦客旭十章节树与有序树十章节树与有序树51Huffman coding In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable length code table for encoding a source symbol (such as a character in a file) where th
40、e variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper A Method for the Construction of
41、Minimum-Redundancy Codes. Huffman became a member of the MIT faculty upon graduation and was later the founding member of the Computer Science Department at the University of California, Santa Cruz, now a part of the Baskin School of Engineering.戌韩疮工君沏矗釜彬猖领胎照庐捅茎绚美绒翘庭帚可跳蔗窖漓馈背对拴槐十章节树与有序树十章节树与有序树5210.1510.17作业作业21妊舀膨哪嘿浩选市乙乏疡丧赏黄氓无侮丑欺咖氟轨啤钉胚税佣借翌哩仟缘十章节树与有序树十章节树与有序树53树是否平面图？如果是，面数是多少？树是否平面图？如果是，面数是多少？课堂练习课堂练习沿丧蚤斩惮音蕊蜜几翼举我亮扮方茅玻蛀精甸吞伴舅钉柬慰供曳勋日尾憋十章节树与有序树十章节树与有序树54
