离散数学教学课件-16树.pptVIP

例2.在通信中,0,1,2,?,7出现的频率如下: 0: 30％, 1: 20％, 2: 15％, 3: 10％, 4: 10％, 5: 5％, 6: 5％, 7: 5％. 求传输它们的最佳前缀码. 01传0 11传1 001传2 100传3 101传4 0001传5 00000传 6 00001传7 W(T)=10+15+30+60 +100+40+20=275 定义9.对于一棵根树的每个顶点都访问一次且仅一次称为行遍或周游一棵树. 对于2叉正则有序树有以下3种行遍方法: (1)中序行遍法 访问次序为:左子树,树根,右子树. (2)前序行遍法 访问次序为:树根,左子树,右子树. (3)后序行遍法 访问次序为:左子树,右子树,树根. 中序行遍法:((dce)bf)a(gih). 前序行遍法:a(b(cde)f)(igh). 后序行遍法:((dec)fb)(ghi)a. 利用2叉正则有序树可以表示四则运算的算式,然后根据不同的访问方法得到不同的算法. 用2叉正则有序树表示算式的方法如下: 参加运算的数都放在树叶上, 然后按照运算的顺序依次将运算符(+,-,?,?)放在分支点上, 每个分支点表示一个运算. 规定: 被除数, 被减数放在左边. 例3. (1)用2叉正则有序树表示下面算式: ((a＋(b*c))*d＋e)÷(f *g). (2)用3种行遍法访问(1)中根树,写出行遍结果. 解:(1)所得2叉正则有序树如图所示 (2) 中序行遍法访问结果为 (((a＋(b*c))*d)＋e)÷(f *g) 在上式中利用四则运算规则省去一些括号,得到原算式. 中序行遍法访问结果是还原算式. 对中缀表达式的计算，并非按运算符出现的自然顺序来执行运算，而是根据算符间的优先关系来确定运算的次序. 此外，还应顾及括号规则. 因此，要从中缀表达式直接产生目标代码一般比较麻烦.  波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示法. 这种表示法的特点是: 表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序，因而又称为无括号式. (2)前序行遍法访问结果为 ÷(＋(*(＋a(*bc))d)e)(*fg) 消去上式中的全部括号,得 ÷＋*＋a*bcde*fg 在上式中规定:从右到左每个运算符对它后面紧邻的两数进行运算. 在此种算法中,因为运算符在它的两个运算对象之前,因而称为前缀符号法(波兰符号法). (2)后序行遍法访问结果为 (((a(bc*)＋)d*)e＋)(fg*)÷ 消去上式中的全部括号,得 abc*＋d*e＋fg*÷ 在上式中规定:从左到右每个运算符对它前面紧邻的两数进行运算. 在此种算法中,因为运算符在它的两个运算对象之后,因而称为后缀符号法(逆波兰符号法). 因前缀表示不常用，故常将后缀表示就称为波兰表示。 * * 第十六章 树 16.1 无向树及其性质 16.2 生成树 16.3 根树及其应用 定义1. 连通无圈的无向图称为无向树, 简称树. 注: 平凡图称为平凡树. 定义2. 树中悬挂顶点称为树叶, 其余顶点称为分支点. 16.1 无向树及其性质 定理1. 设G是n点m边的图, 则下列各命题等价: (1) G是树; (2) G的每对顶点之间具有唯一路径; (3) G连通且n＝m+1; (4) G无圈且n＝m+1; (5) G连通且每条边均为割边; (6) G无圈且在不同顶点间添一条新边后产生惟一含新边的圈. 定理2.设T是n阶非平凡树,则T中至少有2片树叶. 星形图 路 例1. 画出所有5阶非同构的树. 解: 16.2 生成树 定义1. 若无向图G的生成子图T是树, 则称T是G的生成树. G-E(T)称为T的余树. (2)为(1)的一棵生成树T,(3)为T的余树. 注:余树不一定是树. G 定理1.无向图G有生成树当且仅当G连通. 推论1. n点m边无向连通图有m≥n-1. 推论2. 设G为n点m边无向连通图,T是G的生成树,T ?是T的余树,则T ?有m-n+1条边. 注: 生成树T中的边称为T的树枝; 余树中的边称为T的弦. G[{d,e,f}]是G的一棵生成树, 记为T. T+a产生圈ade; T+b产生圈dbf; T+c产生圈efc; 定理2.设T为无向连通图G中一棵生成树,e为T的任意一条弦,则T+e中包含一个由e和树枝构成的圈,而且不同的弦对应的圈也不同. 定义2.设T是n点m边无向连通图G的一棵生成树,e1,e2,?,em-n+