树与生成树幻灯片.ppt

树与生成树第1页，共36页，编辑于2022年，星期六5.与树定义等价的几个命题与树定义等价的几个命题定理定理1给定图给定图T,以下关于树的定义是等价的以下关于树的定义是等价的.T无回路的连通图无回路的连通图.T无环且每对结点之间有一条且仅有一条路无环且每对结点之间有一条且仅有一条路.T无回路但在任一对不相邻的顶点间添加一条新边无回路但在任一对不相邻的顶点间添加一条新边e，则，则T+e包含唯一的回路包含唯一的回路.T连通的连通的,且每条边都是割边且每条边都是割边.T连通的且连通的且m=n-1.T无回路且无回路且m=n-1.证明证明:已知已知T是连通无回路图是连通无回路图,所以所以T中中无环。若无环。若T中存在两条不同的中存在两条不同的u-v路路P1和和P2，则存在，则存在P1的一条的一条边边e=xy，它不是，它不是P2的边，因此的边，因此(P1 P2)-e连通，连通，所以，所以，(P1 P2)-e存在一条存在一条x-y路路P，故，故P+e是是T的圈，矛盾。的圈，矛盾。第2页，共36页，编辑于2022年，星期六T无环且每对结点之间有一条且仅有一条路无环且每对结点之间有一条且仅有一条路.T无回路但在任一对不相邻的顶点间添加一条新边无回路但在任一对不相邻的顶点间添加一条新边e，则，则T+e包含唯一的回路包含唯一的回路.T连通的连通的,且每条边都是割边且每条边都是割边.:显然显然T无回路，否则对回路上的任一对顶点都无回路，否则对回路上的任一对顶点都至少存在两条路，与至少存在两条路，与矛盾。设矛盾。设u，v是是T中任意两个中任意两个不相邻的点，令不相邻的点，令e=uv，由，由，T中有一条唯一的中有一条唯一的u-v路，所以路，所以T+e中包含唯一的中包含唯一的回路。回路。:因为因为T无回路，所以无回路，所以T的每条边都是割边；若的每条边都是割边；若T不连通，设不连通，设T1，T2是是T的两个分支，设的两个分支，设u V(T1),v V(T2),则则uvE(T)，显然，显然T+uv不存在回路，与不存在回路，与矛矛盾。盾。第3页，共36页，编辑于2022年，星期六 T连通的连通的,且每条边都是割边且每条边都是割边.T连通的且连通的且m=n-1.:关于点数用归纳法证明。关于点数用归纳法证明。当当n=1或或2时，时，T是平凡图或是平凡图或K2，显然有，显然有m=n-1。假设假设n k时结论成立，往证时结论成立，往证n=k+1时成立。时成立。当当n=k+1时。取时。取T的一条边的一条边e，由，由，e是割边，是割边，所以所以T-e有两个分支有两个分支T1和和T2，因为因为|V(T1)|k,|V(T2)|k,所以，由归纳假设，有所以，由归纳假设，有|E(T1)|=|V(T1)|-1，|E(T2)|=|V(T2)|-1故故m=|E(T1)|+|E(T2)|+1 =|V(T1)|-1+|V(T2)|-1+1 =n-1。第4页，共36页，编辑于2022年，星期六 T连通的且连通的且m=n-1.T无回路且无回路且m=n-1.n:只需证明只需证明T无回路。对无回路。对T关于顶点关于顶点数归纳。数归纳。n当当n=1或或n=2时，显然成立。时，显然成立。n假设假设n k时结论成立，往证时结论成立，往证n=k+1时成时成立。立。n因为因为T连通，所以连通，所以(T)1，由，由m=n-1及及 d(v)=2m得，得，T中至少存在一点中至少存在一点u，使，使得得d(u)=1。考虑。考虑T=T-u，显然，显然T连通，连通，且且|E(T)|=|V(T)|-1，由归纳假设，由归纳假设，T无回路，所以无回路，所以T无回路。无回路。第5页，共36页，编辑于2022年，星期六 T无回路且无回路且m=n-1.T无回路的连通图无回路的连通图.:假设假设T不连通，设不连通，设T1,T2,Tk为为T的连通分支，则的连通分支，则k2。对任意的。对任意的Ti，Ti是无回路的连通图，所以是无回路的连通图，所以Ti是树，由是树，由得，得，|E(Ti)|=|V(Ti)|-1故故m=i=1k|E(Ti)|=i=1k|V(Ti)|-k =n-kn-1矛盾。矛盾。定理定理2：每一非平凡树至少有两片树叶。每一非平凡树至少有两片树叶。证明：设证明：设T是一非平凡树，则是一非平凡树，则m=n-1。因为因为T连通且非平凡，所以连通且非平凡，所以(T)(T)1 1。设设T T有有k k片树叶，则剩余的片树叶，则剩余的n-kn-k个顶点的度至少为个顶点的度至少为2 2。由。由 d(v)=2md(v)=2m得，得，k+2(n-k)k+2(n-k)m=2(n-1),m=2(n-1),所以所以 k k2 2。第6页，共36页，编辑于2022年，星期六二二.生成树生成树在图论的应用中在图论的应用中,找出一个连通图的所有不同的生成树找出一个连通图的所有不同的生成树,以以及找出最小生成树是很有意义的及找出最小生成树是很有意义的.1.定义定义:如果图如果图G的生成子图是树的生成子图是树,则称此树为则称此树为G的生成树的生成树.2.弦弦:图图G中中,不在其生成树里的边不在其生成树里的边,称作称作弦弦.所有弦的集合所有弦的集合,称为该生成称为该生成树的补树的补.定理定理2 连通图连通图G中至少有一棵生成树中至少有一棵生成树.证明证明:如果如果G中无回路中无回路,则则G本身就是树本身就是树.如果如果G中有回路中有回路,可以通过反复删去回路可以通过反复删去回路中的边中的边,使之既无回路使之既无回路,又连通又连通.就得到生成树就得到生成树.思考题思考题:设设G是有是有n个结点个结点,m条边的连通图条边的连通图,问要删去多少问要删去多少条边条边,才得到一棵生成树才得到一棵生成树?v1 v5v4 v2 v3第7页，共36页，编辑于2022年，星期六三三.赋权图的最小生成树赋权图的最小生成树1.定义定义:一棵生成树中的所有边的权之和称为该一棵生成树中的所有边的权之和称为该生成树的生成树的权权.具有最小权的生成树具有最小权的生成树,称为称为最小生成树最小生成树.最小生成树很有实际应用价值最小生成树很有实际应用价值.例如结点是城市名例如结点是城市名,边的权边的权表示两个城市间的距离表示两个城市间的距离,从一个城市出发走遍各个城市从一个城市出发走遍各个城市,如何选择最优的旅行路线如何选择最优的旅行路线.又如城市间的通信网络问题又如城市间的通信网络问题,如如何布线何布线,使得总的线路长度最短使得总的线路长度最短.例如例如:右图所示右图所示2.求最小生成树算法求最小生成树算法-Kruskal算法算法:(贪婪算法贪婪算法)v1 v5 v4v2 v3v8 v6v7 12213772486653443第8页，共36页，编辑于2022年，星期六Kruskal算法算法:设设G是有是有n个结点个结点,m条边条边(mn-1)的连通图的连通图.|S|=n-1,说明是树说明是树最后最后S=a1,a2,a3,an-1S=i=0 j=1将所有边按照权升序排序:e1,e2,e3,em|S|=n-1取ej使得使得S ej有回路有回路?j=j+1i=i+1ai=ejS=Saij=j+1输出S停YNYN第9页，共36页，编辑于2022年，星期六边按升序排序边按升序排序:边边(vi,vj)记成记成eij边权边权e28e34e23e38e17e24e45e57e16e78e56e35e46e67e58e12e181 1 2 2 2 3 3 3 4 4 4 5 6 6 7 7 8v1 v5 v4v2 v3v8 v6v7 12213772486653443v1 v5 v4v2 v3v8 v6v7 1212433第10页，共36页，编辑于2022年，星期六Prin算法算法(边割法边割法)n实质实质:在在n-1个边割集中个边割集中,取每个边割集的一条权最小取每个边割集的一条权最小的边的边,构成构成G的一个生成树的一个生成树.n定义：定义：nStep0.设设v为为V的任一顶点的任一顶点.令令S0=v,E0=,k=0.nStep1.若若Sk=V,结束结束.以以Sk为点集为点集,Ek为边集的图为边集的图即是即是G的最优树的最优树.否则转否则转Step2.nStep2.构造构造 ,若若 ,则则G不连通不连通,停停止止.否则否则,设设n n令令n置置k=k+1.返回返回Step1.第11页，共36页，编辑于2022年，星期六n例：求图例：求图G的最小生成树。的最小生成树。第12页，共36页，编辑于2022年，星期六破圈法破圈法n-Prin算法的对偶方法算法的对偶方法.最适合于在图最适合于在图上作业上作业.当图比较大时当图比较大时,还可以几个人同还可以几个人同时在各个局部作业时在各个局部作业.nStep0.令令G0=G.k=0.nStep1.若若Gk不含圈不含圈,转转Step2.若若Gk中中含有圈含有圈C.设设ek E(C),且且n令令Gk+1=Gk-ek,若若k=k+1,返回返回Step1.nStep2.结束结束.Gk为为G的最小树的最小树.第13页，共36页，编辑于2022年，星期六第14页，共36页，编辑于2022年，星期六结论：最小生成树不唯一。结论：最小生成树不唯一。本节要掌握本节要掌握树的树的6个定义个定义,会画生成树和会求最小生成树会画生成树和会求最小生成树.第15页，共36页，编辑于2022年，星期六8-10.根树及其应用下面讨论有向树下面讨论有向树,它的应用很广泛它的应用很广泛.在计算机科学中有如判在计算机科学中有如判定树、语法树、分类树、搜索树、目录树等等定树、语法树、分类树、搜索树、目录树等等.一一.有向树有向树1.定义定义:如果如果G是个有向图是个有向图,且若不考虑边的方向时且若不考虑边的方向时(即看成即看成无向图时无向图时),是一棵树是一棵树,则称则称G是有向树是有向树.例如例如:v1 v6v4 v2 v3 v5v2 v5 v4v1 v3v6 v4 第16页，共36页，编辑于2022年，星期六二二.根树根树:如果一棵有向树如果一棵有向树,恰有一个结点的入度为恰有一个结点的入度为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第17页，共36页，编辑于2022年，星期六三三.举例举例:a)语法树语法树b)算术表达式树算术表达式树(a+b)c)(de)句子句子 动词动词 冠词冠词 主语主语 谓语短语谓语短语 形容词形容词 名词名词 宾语宾语 The little boy saw apple The冠词冠词 名词名词+a b c e d第18页，共36页，编辑于2022年，星期六c)判定树判定树:有四枚金币有四枚金币a,b,c,d,已知道三个是真的已知道三个是真的,最多一最多一个是假的个是假的,它们的外表完全相同它们的外表完全相同,只是重量有点差别只是重量有点差别.给你给你一架天平找出假币一架天平找出假币.a:b a:c a:c a:ca轻轻 b重重 a:d c重重 c轻轻 b轻轻 a重重全真全真 d轻轻d重重=第19页，共36页，编辑于2022年，星期六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 开始结点开始结点目标结点目标结点.第20页，共36页，编辑于2022年，星期六五五.m叉树与完全叉树与完全m叉树叉树1.m叉树叉树:在根树中在根树中,如果每个结点的出度最大是如果每个结点的出度最大是m,则称则称 此树是此树是m叉树叉树.2.完全完全m叉树叉树:在根树中在根树中,如果每个结点的出度都是如果每个结点的出度都是m或者或者 等于等于0,则称此树是完全则称此树是完全m叉树叉树.3.正则正则m叉树叉树:在完全在完全m叉树中叉树中,如果所有树叶的层次相同如果所有树叶的层次相同,则称之为正则则称之为正则m叉树叉树.定理定理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第21页，共36页，编辑于2022年，星期六七七.m叉有序树转化成二叉树叉有序树转化成二叉树因为二叉树便于存贮因为二叉树便于存贮,也便于处理也便于处理,所以通常可以将多叉所以通常可以将多叉树化成二叉树树化成二叉树.方法是方法是:1.每个结点保留左儿子结点每个结点保留左儿子结点,剪掉右边其分支剪掉右边其分支.被剪掉被剪掉 的结点如下处理的结点如下处理(重新嫁接重新嫁接).2.同一个层次的结点同一个层次的结点,从左到右依次画出从左到右依次画出(被剪掉的结点被剪掉的结点 嫁接嫁接到它的到它的哥哥哥结点上哥结点上).r e c a b d g fh i j k lr a bc dh e f gi j k l第22页，共36页，编辑于2022年，星期六八八.遍历二叉树遍历二叉树 在二叉树的一些应用中在二叉树的一些应用中,常常要在树中查找具有某些常常要在树中查找具有某些特征的结点特征的结点,或者对所有结点逐一进行某种处理或者对所有结点逐一进行某种处理,这就提这就提出了遍历二叉树问题出了遍历二叉树问题.即按照一定规律巡访树中每个结点即按照一定规律巡访树中每个结点一次一次.由于二叉树是一个非线性结构由于二叉树是一个非线性结构,每个结点都可能在左右每个结点都可能在左右两棵子树上两棵子树上,为此要寻找一种规律为此要寻找一种规律,以便使二叉树上结点以便使二叉树上结点的信息排成一个线性队列上的信息排成一个线性队列上,从而便于遍历从而便于遍历.有三种遍历方式有三种遍历方式1.先序遍历先序遍历2.中序遍历中序遍历3.后序遍历后序遍历第23页，共36页，编辑于2022年，星期六1.先序遍历先序遍历访问根结点访问根结点.先序遍历左子树先序遍历左子树先序遍历右子树先序遍历右子树结果结果:32x2x3x2.中序遍历中序遍历 中序遍历左子树中序遍历左子树访问根结点访问根结点.中序遍历右子树中序遍历右子树结果结果:32x2x3x3.后序遍历后序遍历 后序遍历左子树后序遍历左子树后序遍历右子树后序遍历右子树访问根结点访问根结点.后序遍历后序遍历:32x2x3x+3 2 xx 2+x 3 第24页，共36页，编辑于2022年，星期六九九.最优树最优树(哈夫曼树哈夫曼树 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 d7523T1T2T3第25页，共36页，编辑于2022年，星期六2.带权树带权树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 d7523T1T2T3第26页，共36页，编辑于2022年，星期六3.最优树最优树:带权树中带权树中,权数最少的二叉树权数最少的二叉树.4.画最优树的算法画最优树的算法-哈夫曼算法哈夫曼算法:先将权按照升序排序先将权按照升序排序,设为设为w1w2w3wm.以以w1和和w2为儿子结点为儿子结点,构造它们的父结点构造它们的父结点,且其权为且其权为 w1+w2,并从权的序列中去掉并从权的序列中去掉w1和和w2。w1+w2再与其余权一起排序再与其余权一起排序,再从此队列中取出前面两个权再从此队列中取出前面两个权值为儿子结点值为儿子结点,同同的方法构造它们的父结点的方法构造它们的父结点.依此类推依此类推,直至最后直至最后.即得到最优树即得到最优树.例如例如,给定一组权给定一组权:2,3,5,7,11,13,17,19,23.构造一棵最优树构造一棵最优树.第27页，共36页，编辑于2022年，星期六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,58100第28页，共36页，编辑于2022年，星期六5.最优树的应用举例最优树的应用举例 用于程序设计用于程序设计 例如编写一个将百计分例如编写一个将百计分a转换成五计分的程序转换成五计分的程序,如果这样如果这样:if a60 then b=“不及格不及格”else if a70 then b=“及格及格”else if a80 then b=“中等中等”else if a90 then b=“良好良好”else b=“优秀优秀”a60a70a80a70分分)才得出结果才得出结果.那么如何设计这个程序才合理呢那么如何设计这个程序才合理呢?就是按最优树来设计就是按最优树来设计.第30页，共36页，编辑于2022年，星期六 分数分数:0-59 60-69 70-79 80-89 90-100比例比例(%):5 15 40 30 10设权序列为设权序列为:5,10,15,30,40 构造最优树构造最优树:为了使得判断框内只比较一次为了使得判断框内只比较一次,流程图可以改成下面框图流程图可以改成下面框图:51015304015306010060a7070a8080a90a60不及格及格中等良好优秀YYYYNNNN第31页，共36页，编辑于2022年，星期六在分数正态分布下在分数正态分布下,按照这个流程图按照这个流程图,编制程序编制程序,比较合理比较合理.前缀码前缀码(哈夫曼编码哈夫曼编码)a)问题的提出问题的提出:数据通讯时数据通讯时,需要将信息编码需要将信息编码,即用二进即用二进制符号串表示信息制符号串表示信息.例如要传送的报文为例如要传送的报文为:“ABACCDA”,只有只有4个基本符号个基本符号,a60a70a80a90不及格及格中等良好优秀YYYYNNNN第32页，共36页，编辑于2022年，星期六只要二位二进制符号就可以分辨只要二位二进制符号就可以分辨.设设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”,无法翻无法翻译译.第33页，共36页，编辑于2022年，星期六产生这个问题的原因是产生这个问题的原因是:有的符号的编码是另一个符号编有的符号的编码是另一个符号编码的前缀码的前缀.比如比如A的编码的编码“0”,是是B编码编码“00”的前缀的前缀.这样就这样就无法翻译报文无法翻译报文.直接促使我们设计前缀码直接促使我们设计前缀码.b)前缀码的定义前缀码的定义:一个符号的编码不是另一个符号编码的一个符号的编码不是另一个符号编码的前缀前缀.c)前缀码的设计前缀码的设计:每棵二叉树对应一组前缀码每棵二叉树对应一组前缀码.在在二叉树的边上二叉树的边上,将每个结点下面的将每个结点下面的两条边分别标上两条边分别标上0和和1,然后从根到然后从根到叶叶,把这个路径的边上所标的把这个路径的边上所标的0-1符符号串写下来号串写下来,就是这个叶结点对应的前缀码就是这个叶结点对应的前缀码.1010 01100 101100第34页，共36页，编辑于2022年，星期六反之反之,任何一组前缀码也对应一棵二叉树任何一组前缀码也对应一棵二叉树.例如有一组前缀码例如有一组前缀码1,01,001,000,因为中最长的编码因为中最长的编码000,有有3位位,可以画一棵高度为可以画一棵高度为3的二叉树的二叉树,如图如图:现在现在再回到前面的问题再回到前面的问题,对报文对报文“ABACCDA”设计编码设计编码.先计算各个符号在报文中出现的频率先计算各个符号在报文中出现的频率:A,B,C,D的频率分的频率分别是别是:43%,14%,29%,14%.分别表示成权分别表示成权(43,14,29,14)101100 11110000101001000第35页，共36页，编辑于2022年，星期六对权排序对权排序:14,14,29,43画最优树画最优树:编码是编码是:A,B,C,D 0,100,11,101.原报文原报文“ABACCDA”译文译文:“0100011111010”有有13位位.那么在接收端那么在接收端如何译码如何译码呢呢?就是将译文中符号从头读就是将译文中符号从头读,顺着这棵最优树顺着这棵最优树,反复从根到叶找前缀码反复从根到叶找前缀码.比如有如下报文比如有如下报文“01110110111100111100100”原文是原文是“AC D D C B C CAAB ”141429432857100000111A:0C:11B:100D:101第36页，共36页，编辑于2022年，星期六