《9-2-树-离散数学-教学课件.ppt》由会员分享，可在线阅读，更多相关《9-2-树-离散数学-教学课件.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第9章 树 9.1无向树及生成树9.2根树及其应用根树n最优2元树n在所有有在所有有t片树叶片树叶,带权带权w1,w2,wt 的的 2元树元树中中,权最小的权最小的2元树。元树。nHuffman算法-求最优树的算法n在m元正则树中，其树叶数为t，分支点数为s，则 (m-1)s=t-1Huffman算法的推广算法n求一棵带权为1，2，3，4，5，6，7的最优3元树W(T)=(1+2+3)2+(4+5+6)2+71=49 1 2 3 4 5 67这是三元正则树这是三元正则树n求一棵带权为1，2，3，4，5，6，7，8的最优3元树W(T)=(1+2+3)3+(7+8)2+(4+5+6)2+=78 1
2、 2 3 4 5 6 7 8这不是三元正则树这不是三元正则树？Huffman算法的推广算法Huffman算法的推广算法nm元正则树的分支点数s与树叶数t之间满足(m-1)s=t-1n求m元最优树时应分两种情况讨论n(t-1)/(m-1)为整数时，为整数时，说明所求树说明所求树T为为m元正则元正则树，树，可仿可仿Huffman算法求最优算法求最优m元树。元树。n(t-1)/(m-1)的余数为的余数为k时，时，1 k m-2，说明所说明所求树是非正则的，求树是非正则的，n此时将此时将k+1个较小的权对应的树叶个较小的权对应的树叶 作为兄弟放在最高层次上，然后仿作为兄弟放在最高层次上，然后仿 Huf
3、fman算法求最优算法求最优m元树即可元树即可。二元树的应用1n由于树在计算机内存中可通过多重链表来表示，n各链表结点所占内存单元的个数依赖于该结点的儿子数，n若一个结点有若一个结点有 n 个儿子，一般要用个儿子，一般要用(n+1)个单元表示该结点，个单元表示该结点，（n个单元用来指出该结点的各儿子的位置），结点一般表示为：个单元用来指出该结点的各儿子的位置），结点一般表示为：n链表结点的单元个数链表结点的单元个数若若固定得较大固定得较大按需分配按需分配会浪费较多空间或使算法复杂。n所以，树的存储表示大都先转化成二元树。数据数据儿子儿子1儿子儿子2儿子儿子n 二元树的应用1n二元树可以表示任何
4、一棵有序根树n方法如下：从根结点开始，从根结点开始，保留保留父亲和最左边儿子的连线父亲和最左边儿子的连线，取消取消和其他儿子的连线，兄弟之间用从左到右的有向边连和其他儿子的连线，兄弟之间用从左到右的有向边连接。接。二元树的应用2n在通信中常用二进制串表示英文字母。最少用多少位二进制数就能表示26个英文字母呢？n用定长二进制数表示英文字母：n因为因为16=24 26 32=25，所以要用，所以要用5位表示。位表示。n用不定长二进制数表示英文字母：n若规定，可用若规定，可用1bit表示英文字母，也可用表示英文字母，也可用2 bit表示英文字母。若表示英文字母。若1位和两位不足以表示位和两位不足以表
5、示26个英文字母，可用个英文字母，可用3 bit。再不够，用。再不够，用4 bit。n至少需要多少位二进制数？设需要i 位二进制数，于是，下列的不等式成立：26 21222i =2i+12 解之，得解之，得i 4n故用长度不超过4位的二进制数足以表示26个英文字母。二元树的应用2n在英文中有些字母使用频率较高，另一些字母使用频率较低。n为了减少通信中传递的信息量，人们希望用位数较少的二进制数表示频繁使用的字符，用位数较多的二进制数表示不常使用的字符。n这样就会大大缩短信息串的总长度。但是也产生了一个问题。接收者如何将0、1组成的长串，准确无误地分割成字母对应的0、1序列呢？n例如：若用例如：若
6、用00表示表示e，用，用01表示表示t，用，用0001表示表示q。当接。当接收员接收到收员接收到0001时，就无法区分这是时，就无法区分这是et，还是，还是q。为了。为了解决这个问题，引入解决这个问题，引入前缀码前缀码的概念。的概念。前缀码n一棵一棵2 2元树产生一个二元前缀码元树产生一个二元前缀码:n对每个分支点对每个分支点,若关联若关联2条边条边,则给则给左边标左边标0,右边标右边标1;n若若只只关关联联1条条边边,则则可可以以给给它它标标0(看看作作左左边边),也也可可以以标标1(看作右边看作右边).n将将从从树树根根到到每每一一片片树树叶叶的的通通路路上上标标的的数数字字组组成成的的字
7、字符符串记在树叶处串记在树叶处,所得的字符串构成一个前缀码所得的字符串构成一个前缀码.右图的树叶都互为前缀码右图的树叶都互为前缀码由任意一个前缀码求对应一个二元树n设1,01,000是一前缀码，画出对应一个二元树n解：画出一个高为画出一个高为3的的正则二元树正则二元树，给各边标记，给各边标记0或或1，每，每一个结点对应一个一个结点对应一个0、1序列，如果某个序列，如果某个0、1序列是前缀码序列是前缀码的元素，则标记该结点。的元素，则标记该结点。n将已标记结点的所有后代和该结点的射出边全部删除，再将已标记结点的所有后代和该结点的射出边全部删除，再删除未加标记的树叶，得到要求的二元树删除未加标记的
8、树叶，得到要求的二元树。最佳前缀码例 在通信中，设八进制数字出现的频率如下：采用2元前缀码,求传输数字最少的2元前缀码(称作最佳前缀码),并求传输10n(n2)个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3)的码字传输需要多少个二进制数字?解解:用用Huffman算法求以频率算法求以频率(乘以乘以100)为权的最优为权的最优 2元树元树.这里这里 w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.数码数码01234567出现频率出现频率(%)25201510101055n最佳前缀码数码频率(%)编码码长02501212011221
9、5001331010034101013510000146500000575000015二元树的应用4波兰符号法与逆波兰符号法 n行行遍遍(周周游游)根根树树T:对对T 的的每每个个顶顶点点访访问问且且仅仅访访问问一次一次.n行遍行遍2元有序正则树的方式：元有序正则树的方式：中序行遍法中序行遍法:左子树、根、右子树左子树、根、右子树 b a(f d g)c e 前序行遍法前序行遍法:根、左子树、右子树根、左子树、右子树 a b(c(d f g)e)后序行遍法后序行遍法:左子树、右子树、根左子树、右子树、根 b(f g d)e c)a 带下划线的是带下划线的是(子子)树根树根,一对括号内是一棵子树
10、一对括号内是一棵子树 波兰符号法与逆波兰符号法n用用2元有序正则树表示算式元有序正则树表示算式:n最高层次运算放在树根上最高层次运算放在树根上,n依次将运算符放在根子树的根上依次将运算符放在根子树的根上,数放在树叶上数放在树叶上,n规定规定被除数被除数、被减数被减数放在放在左子树树叶左子树树叶上上.例如例如,右图表示算式右图表示算式(b+(c+d)a)(e f)(g+h)(i j)波兰符号法n波兰符号法波兰符号法(前缀符号法前缀符号法):n按按前前序序行行遍遍法法访访问问表表示示算算式式的的2元元有有序序正正则则树树,其结果不加括号其结果不加括号,n规规定定每每个个运运算算符符号号与与其其后后
11、面面紧紧邻邻两两个个数数进进行行运运算算.右树的访问结果为右树的访问结果为 b+c d a e f +g h i j 前序行遍法前序行遍法:根、左子树、右子树根、左子树、右子树逆波兰符号法n逆波兰符号法逆波兰符号法(后缀符号法后缀符号法):n按按后后序序行行遍遍法法访访问问,规规定定每每个个运运算算符符与与前前面面紧紧邻邻两数运算两数运算.右树的访问结果为右树的访问结果为 b c d+a e f g h+i j 后序行遍法后序行遍法:左子树、右子树、根左子树、右子树、根根树的应用n四元正则树四元正则树根树的应用决策树n设有7枚相同的硬币及一枚看起来相同但稍重一些的硬币。下面要用天平，以最少的称
12、量次数识别出假硬币。n图中图中1,2-3,4表示：表示：天平左边称硬币天平左边称硬币1、2，右边称硬币右边称硬币3、4。n当天平右边下降时，当天平右边下降时，沿右边的子树继续称重，沿右边的子树继续称重，否则沿左边的子树继续。否则沿左边的子树继续。是否存在不同的方法，是否存在不同的方法，使它能在更小的称量次数使它能在更小的称量次数 下找出假硬币？下找出假硬币？1,2,3,4-5,6,7,81,2-3,45,6-7,81-23-45-67-81 2 3 4 5 6 7 8此方案要找出假硬币，需要此方案要找出假硬币，需要3次称重次称重根树的应用决策树n设有7枚相同的硬币及一枚看起来相同但稍重一些的硬
13、币。下面要用天平，以最少的称量次数识别出假硬币。n由于天平一次称量有由于天平一次称量有3种可能结果，种可能结果，n所以可以构造出一棵根树，有所以可以构造出一棵根树，有3个儿子：个儿子：n其中，当天平平衡时，沿中间的孩子继续。其中，当天平平衡时，沿中间的孩子继续。1 2 3 4 5此方案要找出假硬此方案要找出假硬币，需要币，需要2次称重次称重6 7 81-34-56-81,2,3-4,5,6最优数据存储方案问题n如以下为4行DNA数据(长度=45)：R1=aggacggaaaacgggaataacggaggaggacttggcacggcattaR2=cggatggaaaactggaataacgg
14、aggaggagttggcacggaattaR3=cgatcggaaaaggcgaataacggacgaagacttgggacgacattaR4=atgacggaaaacgggtaaaacggaggaggatttggcacggactta每个数据作为一顶点构成完全图，每个数据作为一顶点构成完全图，各顶点之间以各数据差异的位数作权值。各顶点之间以各数据差异的位数作权值。n存储问题实际上只需要存储一个数据，以及由该完全图的一个生成树所对应的差异元素。n最最优树对应于最优的存储方案。优树对应于最优的存储方案。R1R3R4R261097136设T是n(n3)阶无向树，T*为T的对偶图n证明：T是简单图是
15、简单图T是二部图是二部图T是平面图是平面图T不不是欧拉图是欧拉图T不不是哈密顿图是哈密顿图T*是平面图是平面图T*是欧拉图是欧拉图T*是哈密顿图是哈密顿图T*不不是简单图是简单图T*不不是二部图是二部图设T是n(n3)阶无向树，T*为T的对偶图n证明：T不是欧拉图 T 是是 n(n3)阶无向树，阶无向树，由定理由定理9.2知，知，T至少有至少有2片树叶，片树叶，它们都是奇数度的顶点它们都是奇数度的顶点所以，由所以，由定理定理8.4知，知，T不是欧拉图。不是欧拉图。T不是哈密顿图不是哈密顿图 T 是是n(n3)阶无向树，阶无向树，它的每条边都是割点，不满足哈密顿图的它的每条边都是割点，不满足哈密
16、顿图的必要条件，必要条件，p(G V)|V|所以，由所以，由定理定理8.6知，知，T不是哈密顿图不是哈密顿图设T是n(n3)阶无向树，T*为T的对偶图n证明：T*是平面图T*只有一个顶点，只有一个顶点，T*上所有的环均过该顶点，上所有的环均过该顶点，这些环是可以不相交的这些环是可以不相交的所以，所以，T*是平面图。是平面图。T*是欧拉图是欧拉图 T*只有一个顶点，只有一个顶点，T*上所有的环均过该顶点，上所有的环均过该顶点，T*无奇度数的顶点存在，无奇度数的顶点存在，所以，由所以，由定理定理8.4知，知，T*是欧拉图是欧拉图。T*是哈密顿图是哈密顿图 T*只有一个顶点，只有一个顶点，T*上所有的环均过该顶点，上所有的环均过该顶点，T*的每个环均是一条哈密顿回路的每个环均是一条哈密顿回路所以，所以，T*是哈密顿图。是哈密顿图。设T是n(n3)阶无向树，T*为T的对偶图n证明：T*不是简单图 T*有环有环所以，由所以，由简单图的定义简单图的定义知，知，T*不是简单图不是简单图。T*不是二部图不是二部图T*只有一个顶点，只有一个顶点，T*上所有的环均过该顶点，上所有的环均过该顶点，而环是奇数长度的回路而环是奇数长度的回路所以，由所以，由定理定理8.1知，知，T*不是二部图不是二部图作业21P204：9，10，11，12，13