离散数学PPT课件-6根树及其应用.ppt

6.根树及其应用下面讨论有向树下面讨论有向树,它的应用很广泛它的应用很广泛.在计算机科学中有如在计算机科学中有如判判定树、语法树、分类树、搜索树、目录树等等定树、语法树、分类树、搜索树、目录树等等.一一.有向树有向树1.定义定义:如果如果G是个有向图是个有向图,且在不考虑边的方向时且在不考虑边的方向时(即看即看成成无向图时无向图时),是一棵树是一棵树,则称则称G是有向树是有向树.例如例如:v1 v6v4 v2 v3 v5v2 v5 v4v1 v3v6 v4 二二.根树根树:如果一棵有向树如果一棵有向树,恰有一个结点的入度为恰有一个结点的入度为0,其余其余所所有结点的入度均为有结点的入度均为1,则称此树为根树则称此树为根树.1.树根树根:入度为入度为0的结点的结点.2.叶叶:出度为出度为0的结点的结点.3.分支结点分支结点(内结点内结点):出度不为出度不为0的结点的结点.4.父结点与子结点父结点与子结点:如果如果是根树中是根树中 的一条边的一条边,则称则称vi是是vj的父结点的父结点,vj是是vi的子结点的子结点.5.祖先结点与后裔结点祖先结点与后裔结点:在根树中在根树中,如果从如果从vi到到vj有路有路,则称则称 vi是是vj的祖先结点的祖先结点,vj是是vi的后裔结点的后裔结点.6.根树结点的层次根树结点的层次:从根结点到某个结点的路径的长度从根结点到某个结点的路径的长度,称称为该结点的层次为该结点的层次.同一层次的结点称为同一层次的结点称为兄弟结点兄弟结点.7.树高树高:从树根到各个叶结点的路径中从树根到各个叶结点的路径中,最长路径的长度最长路径的长度,称为该树的高度称为该树的高度(树高树高).v1 v6v4 v2 v3 v5 v7三三.举例举例:a)语法树语法树b)算术表达式树算术表达式树(a+b)c)(de)句子句子 动词动词 冠词冠词 主语主语 谓语短语谓语短语 形容词形容词 名词名词 宾语宾语 The little boy saw apple The冠词冠词 名词名词+a b c e dc)判定树判定树:有四枚金币有四枚金币a,b,c,d,已知道三个是真的已知道三个是真的,最多一个最多一个是假的是假的,它们的外表完全相同它们的外表完全相同,只是重量有点差别只是重量有点差别.给你一给你一架天平找出假币架天平找出假币.a:b a:c a:c a:ca轻轻 b重重 a:d c重重 c轻轻 b轻轻 a重重全真全真 d轻轻d重重=d)搜索树搜索树:八数码游戏八数码游戏:搜索策略搜索策略:宽度优先宽度优先,深度优先深度优先,启发式搜索启发式搜索,.2 8 3 1 6 7 5 4 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 6 4 1 7 5 2 3 1 8 4 7 6 5 2 3 1 8 47 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 开始结点开始结点目标结点目标结点.四四.有序树有序树 如前面的算术表达式树如前面的算术表达式树,家谱树家谱树,都是有序树都是有序树,即同一层即同一层的结点是有次序的的结点是有次序的,如家谱树如家谱树,最左边是老大最左边是老大,其次是老二其次是老二,依此类推依此类推.定义定义:在有向树中在有向树中,如果规定了每一层上的结点的次序如果规定了每一层上的结点的次序,称称之为有序树之为有序树.算术表达式树算术表达式树:(a+b)c)(de)+a b c e d五五.m叉树与完全叉树与完全m叉树叉树1.m叉树叉树:在根树中在根树中,如果每个结点的出度最大是如果每个结点的出度最大是m,则称则称此此 树是树是m叉树叉树.2.完全完全m叉树叉树:在根树中在根树中,如果每个结点的出度都是如果每个结点的出度都是m或者或者 等于等于0,则称此树是完全则称此树是完全m叉树叉树.3.正则正则m叉树叉树:在完全在完全m叉树中叉树中,如果所有树叶的层次相同如果所有树叶的层次相同,则称之为正则则称之为正则m叉树叉树.定理定理8-10.1 T是棵完全是棵完全m叉树叉树,有有t个叶结点个叶结点,i个分支结点个分支结点,则则(m-1)i=t-1.证明证明:T的所有结点的出度总和为的所有结点的出度总和为 mi.入度总和入度总和(i-1)+t.故故 mi=i-1+t 所以所以(m-1)i=t-1v1 v6v4 v2 v3 v5v1 v6 v4 v2 v3 v5 v7v1 v4 v2 v3 v5六六.二叉树的存贮二叉树的存贮 二叉树便于在计算机内存贮二叉树便于在计算机内存贮,设有算术表达式设有算术表达式;(3(2x)+(x-2)(3+x)存贮时存贮时,每个结点含有三个信息每个结点含有三个信息:left-是左指针是左指针,指向左子结点指向左子结点.data-数据数据 right-右指针右指针,指向右子结点指向右子结点.+3 2 x x 2+x 3 left data right表达式的存贮树表达式的存贮树:(3(2x)+(x-2)(3+x)如果使用矩阵表示此树如果使用矩阵表示此树,需要需要1313的矩阵的矩阵,需要需要169单单元存贮空间元存贮空间,而且矩阵中有很多而且矩阵中有很多0.显然冗余太多显然冗余太多.我们用三个一维数组构成的序列表示这棵树我们用三个一维数组构成的序列表示这棵树:32xx23x head 0 表示无左表示无左(右右)子结点子结点只用了只用了42个存贮单元个存贮单元,可见节省内存可见节省内存.+3 2 x x 2+x 3 headleft(i)data(i)right(i)index i1234567891011121314head+32xx2+3x203408506700000000000091210111314七七.m叉有序树转化成二叉树叉有序树转化成二叉树因为二叉树便于存贮因为二叉树便于存贮,也便于处理也便于处理,所以通常可以将多叉所以通常可以将多叉树化成二叉树树化成二叉树.方法是方法是:1.每个结点保留左儿子结点每个结点保留左儿子结点,剪掉右边其它分支剪掉右边其它分支.被剪被剪掉掉的结点如下处理的结点如下处理.2.同一个层次的结点同一个层次的结点,从左到右依次画出从左到右依次画出.r e c a b d g fh i j k lr a bc dh e f gi j k l八八.遍历二叉树遍历二叉树 在二叉树的一些应用中在二叉树的一些应用中,常常要在树中查找具有某些常常要在树中查找具有某些特征的结点特征的结点,或者对所有结点逐一进行某种处理或者对所有结点逐一进行某种处理,这就提这就提出了遍历二叉树问题出了遍历二叉树问题.即按照一定规律巡访树中每个结点即按照一定规律巡访树中每个结点一次一次.由于二叉树是一个非线性结构由于二叉树是一个非线性结构,每个结点都可能在左右每个结点都可能在左右两棵子树上两棵子树上,为此要寻找一种规律为此要寻找一种规律,以便使二叉树上结点以便使二叉树上结点的信息排成一个线性队列上的信息排成一个线性队列上,从而便于遍历从而便于遍历.有三种遍历方式有三种遍历方式对应算术表达式树时：对应算术表达式树时：1.先序遍历先序遍历前缀符号法或波兰符号法前缀符号法或波兰符号法2.中序遍历中序遍历正常算术表达式正常算术表达式3.后序遍历后序遍历后缀符号法或逆波兰符号法后缀符号法或逆波兰符号法1.先序遍历先序遍历访问根结点访问根结点.先序遍历左子树先序遍历左子树先序遍历右子树先序遍历右子树结果结果:32x2x3x2.中序遍历中序遍历 中序遍历左子树中序遍历左子树访问根结点访问根结点.中序遍历右子树中序遍历右子树结果结果:32x2x3x3.后序遍历后序遍历 后序遍历左子树后序遍历左子树后序遍历右子树后序遍历右子树访问根结点访问根结点.后序遍历后序遍历:32x2x3x+3 2 xx 2+x 3 练习：练习：P198 例例9.4 P204 9.11九九.最优树最优树(哈夫曼树哈夫曼树 Huffman)二叉树的一个重要应用就是最优树二叉树的一个重要应用就是最优树.1.带权二叉树的定义带权二叉树的定义:设有一组权值设有一组权值:w1,w2,w3,wm,不不仿设仿设w1w2w3wm,设有一棵二叉树有设有一棵二叉树有m片叶子片叶子,分别带有权值分别带有权值w1,w2,w3,wm,称此树为带权二叉树称此树为带权二叉树.例如例如:下边是有叶结点下边是有叶结点a,b,c,d,分别带有权分别带有权7,5,2,3的二叉树的二叉树:c a b d7523 ca bd 7523 c a b d7523T1T2T32.带权树带权树T的权的权W(T):W(T)=其中其中L(wi)是标有权是标有权wi的叶结点的从根到该叶结点的路长的叶结点的从根到该叶结点的路长.上例中上例中:W(T1)=72522232=34 W(T2)=32735321=44 W(T3)=71522333=32由此看出由此看出W(T3)是比较小的是比较小的.wiL(wi)i=1m c a b d7523 ca bd 7523 c a b d7523T1T2T33.最优树最优树:带权树中带权树中,权数最少的二叉树权数最少的二叉树.4.画最优树的算法画最优树的算法-哈夫曼算法哈夫曼算法:先将权按照升序排序先将权按照升序排序,设为设为w1w2w3wm.以以w1和和w2为儿子结点为儿子结点,构造它们的父结点构造它们的父结点,且其权为且其权为 w1+w2 w1+w2再与其余权一起排序再与其余权一起排序,再从此队列中取出前面两再从此队列中取出前面两个权值为儿子结点个权值为儿子结点,同同的方法构造它们的父结点的方法构造它们的父结点.依此类推依此类推,直至最后直至最后.即得到最优树即得到最优树.例如例如,给定一组权给定一组权:2,3,5,7,11,13,17,19,23.构造一棵最构造一棵最优树优树.2357111317192310042582434171055,5,7,11,13,17,19,232,3,5,7,11,13,17,19,237,10,11,13,17,19,2311,13,17,17,19,2317,17,19,23,2419,23,24,3424,34,4242,581005.最优树的应用举例最优树的应用举例 用于程序设计用于程序设计 例如编写一个将百计分例如编写一个将百计分a转换成五计分的程序转换成五计分的程序,如果这样如果这样:if a60 then b=“不及格不及格”else if x70 then b=“及格及格”else if a80 then b=“中等中等”else if a90 then b=“良好良好”else b=“优秀优秀”a60a70a80a70分分)才得出结果才得出结果.那么如何设计这个程序才合理呢那么如何设计这个程序才合理呢?就是按最优树来设计就是按最优树来设计.分数分数:0-59 60-69 70-79 80-89 90-100 比例比例(%):5 15 40 30 10设权序列为设权序列为:5,10,15,30,40 构造最优树构造最优树:为了使得判断框内只比较一次为了使得判断框内只比较一次,流程图可以改成下面框图流程图可以改成下面框图:51015304015306010060a7070a8080a90a60不及格及格中等良好优秀YYYYNNNN在分数正态分布下在分数正态分布下,按照这个流程图按照这个流程图,编制程序编制程序,比较合理比较合理.前缀码前缀码(哈夫曼编码哈夫曼编码)a)问题的提出问题的提出:数据通讯时数据通讯时,需要将信息编码需要将信息编码,即用二进即用二进制制符号串表示信息符号串表示信息.例如要传送的报文为例如要传送的报文为:“ABACCDA”,只有只有4个基本符号个基本符号,a60a70a80a90不及格及格中等良好优秀YYYYNNNN只要二位二进制符号就可以分辨只要二位二进制符号就可以分辨.设设A,B,C,D的编码分别的编码分别是是“00,01,10,11”.这样上述报文这样上述报文“ABACCDA”可翻译成可翻译成“00010010101100”,译文含有译文含有14个符号个符号.这种编码各个符号的编码是等长等这种编码各个符号的编码是等长等.当然这样的编码在当然这样的编码在报文的接收端容易译码报文的接收端容易译码.但是在发送报文时但是在发送报文时,总是希望报文最短总是希望报文最短,节约开支节约开支.所以所以等长的编码不是最优的等长的编码不是最优的,因为在报文中各个符号出现的频因为在报文中各个符号出现的频率是不同的率是不同的.所以考虑用不等长的编码所以考虑用不等长的编码,应该使得在报文应该使得在报文中出现频率最高的符号编码最短中出现频率最高的符号编码最短.比如比如A,B,C,D的编码分别为的编码分别为:0,00,1,01.这样此报文的译这样此报文的译文为文为:“000011010”,译文的长度是短了译文的长度是短了,只有只有9个符号个符号,但是但是在报文的接收端如何翻译成原文呢在报文的接收端如何翻译成原文呢?比如译文中的比如译文中的“0000”是是“AAAA”还是还是“BB”,还是还是“”ABA”,无法翻译无法翻译.产生这个问题的原因是产生这个问题的原因是:有的符号的编码是另一个符号编有的符号的编码是另一个符号编码的前缀码的前缀.比如比如A的编码的编码“0”,是是B编码编码“00”的前缀的前缀.这这样就样就无法翻译报文无法翻译报文.直接促使我们设计前缀码直接促使我们设计前缀码.b)前缀码的定义前缀码的定义:一个符号的编码不是另一个符号编码的一个符号的编码不是另一个符号编码的前缀前缀.c)前缀码的设计前缀码的设计:每棵二叉树对应一组前缀码每棵二叉树对应一组前缀码.在在二叉树的边上二叉树的边上,将每个结点下面的将每个结点下面的两条边分别标上两条边分别标上0和和1,然后从根到然后从根到叶叶,把这个路径的边上所标的把这个路径的边上所标的0-1符符号串写下来号串写下来,就是这个叶结点对应的前缀码就是这个叶结点对应的前缀码.1010 01100 101100反之反之,任何一组前缀码也对应一棵二叉树任何一组前缀码也对应一棵二叉树.例如有一组前缀码例如有一组前缀码1,01,001,000,因为中最长的编码因为中最长的编码000,有有3位位,可以画一棵高度为可以画一棵高度为3的二叉树的二叉树,如图如图:现在现在再回到前面的问题再回到前面的问题,对报文对报文“ABACCDA”设计编码设计编码.先计算各个符号在报文中出现的频率先计算各个符号在报文中出现的频率:A,B,C,D的频率分的频率分别是别是:43%,14%,29%,14%.分别表示成权分别表示成权(43,14,29,14)101100 11110000101001000对权排序对权排序:14,14,29,43画最优树画最优树:编码是编码是:A,B,C,D 0,100,11,101.原报文原报文“ABACCDA”译文译文:“0100011111010”有有13位位.那么在接收端那么在接收端如何译码如何译码呢呢?就是将译文中符号从头读就是将译文中符号从头读,顺着这棵最优树顺着这棵最优树,反复从根到叶找前缀码反复从根到叶找前缀码.比如有如下报文比如有如下报文“01110110111100111100100”原文是原文是“AC D D C B C CAAB ”作业作业 P204(9),(10),(13),(14)141429432857100000111A:0C:11B:100D:101