lecture24(根树及其应用).ppt
1,离散数学Lecture 25主讲：陈义明信息科学技术学院,2/22,信息科学技术学院,有向树,如果一个有向图在不考虑边的方向时是一棵树，那么，这个图称为有向树。,3/22,信息科学技术学院,学习内容,1 根树及其分类2 最优树与哈夫曼算法3 最佳前缀码,4/22,信息科学技术学院,学习目标,理解根树及其相关概念。掌握最优树的定义及哈夫曼算法。掌握最佳前缀码的定义及求法。,5/22,信息科学技术学院,根树的定义,根树:有一个顶点入度为0,其余的入度均为1的非平凡的有向树。树根:有向树中入度为0的顶点树叶:有向树中入度为1,出度为0的顶点内点:有向树中入度为1,出度大于0的顶点分支点:树根与内点的总称,6/22,信息科学技术学院,根树的定义,顶点v的层数:从树根到v的通路长度，记作 l()树高:有向树中顶点的最大层数。记作h(),7/22,信息科学技术学院,实例,右图中 a是树根 b,e,f,h,i是树叶 c,d,g是内点 a,c,d,g是分支点 a为0层;1层有b,c;2层有d,e,f;3层有g,h;4层有i.树高为4,8/22,信息科学技术学院,家族树,设v为根树的一个顶点且不是树根,称v及其所有后代的导出子图为以v为根的根子树。将根树每一层上的顶点规定次序后称作有序树。,把根树看作一棵家族树:若顶点a邻接到顶点b,则称b是a的儿子,a是b的父亲。若b和c为同一个顶点的儿子,则称b和c是兄弟。若ab且a可达b,则称a是b的祖先,b是a的后代。,9/22,信息科学技术学院,根树的分类,r元树:根树的每个分支点至多有r个儿子r元正则树:根树的每个分支点恰有r个儿子r元完全正则树:所有树叶层数相同的r元正则树r元有序树:有序的r元树r元正则有序树:有序的r元正则树r元完全正则有序树:有序的r元完全正则树,10/22,信息科学技术学院,最优2元树,定义7.10 设2元树T有t片树叶v1,v2,vt,树叶的权分别为w1,w2,wt,称 为T的权,记作W(T),其中l(vi)是vi的层数.在所有有t片树叶,带权w1,w2,wt 的 2元树中,权最小的2元树称为最优2元树。,11/22,信息科学技术学院,求最优2元树的算法,哈夫曼(Huffman)算法给定实数w1,w2,wt 作t片树叶,分别以w1,w2,wt为权 在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支点,以这2个顶点为儿子,其权等于这2个儿子的权之和 重复,直到只有1个入度为0 的顶点为止 W(T)等于所有分支点的权之和。,12/22,信息科学技术学院,实例,例1 求以1,3,4,5,6为权的最优2元树,并计算它的权解,W(T)=4+8+11+19=42,13/22,信息科学技术学院,实例,14/22,信息科学技术学院,通信编码,从编码通信的过程来看，编码要满足什么要求？,使总编码串最短。,要能正确地译码。,设H，E，L，O使用编码 0,10,010,1010 即 H=0,E=10,L=010,O=1010,则HELLO=0100100101010，能否正确译码？,15/22,信息科学技术学院,最佳前缀码,定义7.11 设=12n-1n是长度为n的符号串,12k称作的长度为k的前缀,k=1,2,n1.若非空字符串1,2,m中任何两个互不为前缀,则称1,2,m为前缀码只出现两个符号(如0与1)的前缀码称作2元前缀码例如 0,10,110,1111,10,01,001,110 是2元前缀码 0,10,010,1010 不是前缀码,16/22,信息科学技术学院,用2元树产生2元前缀码的方法,对每个分支点,若关联2条边,则给左边标0,右边标1;若只关联1条边,则可以给它标0(看作左边),也可以标1(看作右边).将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处,所得的字符串构成一个前缀码.,例如,前缀码 00,11,011,0100,17/22,信息科学技术学院,通信编码,从编码通信的过程来看，编码要满足什么要求？,使总编码串最短。,要能正确地译码。,设H，E，L，O使用编码00,0100,011,11，则HELLO的编码长度为多少？,18/22,信息科学技术学院,实例,例2 在通信中,设八进制数字出现的频率(%)如下:0:25,1:20,2:15,3:10,4:10,5:10,6:5,7:5采用2元前缀码,求传输数字最少的2元前缀码(称作最佳前缀码),并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3)的码字传输需要多少个二进制数字?解 用Huffman算法求以频率(乘以100)为权的最优2元树.这里w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.,19/22,信息科学技术学院,实例(续),编码:0-01 1-112-0013-1004-1015-00016-000007-00001,传100个按比例出现的八进制数字需W(T)=285个二进制数字,用等长码(长为3)需要用 300个数字.,5.6 树-根树,例题 汉字“一地在要工上是中国同和的有”出现频率依次为“2,3,5,7,11,13,17,19,23,29,31,37,41”，为这些汉字设计编码。译出“1000101110100101111”对应的汉字。,5.6 树-根树,原则：左小右大、组合优先、左0右1、不足补0 编码：一1010111、地1010110、在101010、要10100、工0100、上0101、是1011、中1110、国1111、同011、和100、的110、有00,5.6 树-根树,原则：左小右大、组合优先、左0右1、不足补0 译码：1000101110100101111，每次从根结点开始，100(和)0101(上)，110(的)，100(和)，1011(是)，110(不足补0，凑成110，译为“的”),此处右边5下方的2，3应画在左边，它违反了组合优先原则,23/22,信息科学技术学院,小结,1 根树及其分类2 最优树与哈夫曼算法3 最佳前缀码,24/22,信息科学技术学院,作业,P147 3,25/22,信息科学技术学院,Thank you for listening!,
