离散数学图论树课件.pptx

1、 第十六章第十六章 树树一、一、无向树无向树1 1）定义：）定义：连通无回路连通无回路（初级回路或简单回路）的无向图称为无向树，或简称树（初级回路或简单回路）的无向图称为无向树，或简称树 常用常用T T表示树，平凡图称为平凡树表示树，平凡图称为平凡树 若无向图若无向图G G至少有两个连通分支，则称至少有两个连通分支，则称G G为为森林森林 在无向树中，在无向树中，悬挂顶点称为树叶悬挂顶点称为树叶，度数大于或等于，度数大于或等于2 2的顶点称为的顶点称为分支结点分支结点2 2）树的等价定义）树的等价定义 设设G GVE是是n n阶阶m m条边的无向图，条边的无向图，则下面各命题是等价的：则下面各

2、命题是等价的：(1)G(1)G是连通无回路（树）是连通无回路（树）可通过循环证明可通过循环证明 (2)G(2)G中任中任意两个顶点之间存在惟一的路径意两个顶点之间存在惟一的路径 （连通则存在路径，若不唯一，不同路径则构成回路）（连通则存在路径，若不唯一，不同路径则构成回路）(3)G (3)G中中无回路且无回路且 m=n-1m=n-1 有长大于等于有长大于等于2 2的回路都与唯一路径矛盾。的回路都与唯一路径矛盾。对结点进行归纳：对结点进行归纳：n=1n=1平凡图平凡图m=0=n-1m=0=n-1；设；设n=kn=k成立；成立；n=k+1n=k+1时时 两个结点有唯一的路，去掉则为两个连通分支（各

3、自满足假设）两个结点有唯一的路，去掉则为两个连通分支（各自满足假设）m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1 (4)G(4)G是是连通的且连通的且 m=n-1m=n-1 若不连通，对各个若不连通，对各个(s=2)(s=2)连通分支是树且有连通分支是树且有mi=ni-1 mi=ni-1 m=n-s s=2 m=n-s s=2 矛盾矛盾 (5)G(5)G中没有回路，但在任何两个不同的顶点之间中没有回路，但在任何两个不同的顶点之间加一条新边加一条新边，在所得图中得到，在所得图中得到惟一的一个含新边的惟一的一个

4、含新边的初级回路初级回路(6)G(6)G是连通的，但是连通的，但删去任何一条边删去任何一条边后，所得图后，所得图不连通不连通 G G连通：若存在二个结点无通路，则在二个结点添加边后不会出现回路连通：若存在二个结点无通路，则在二个结点添加边后不会出现回路3 3）树的性质）树的性质 对于给定的无向图对于给定的无向图树是树是边数最小的连通图边数最小的连通图（mn-1mn-1mn-1则有回路）则有回路）结点的度：结点的度：d(vi)=2m=d(vi)=2m=2(n-1)2(n-1)定理：设定理：设T T是是n n阶非平凡的无向树，则阶非平凡的无向树，则T T中至少有中至少有 片树叶片树叶 设：有设：有

5、x x片树叶，其余结点度数至少为片树叶，其余结点度数至少为2 2x+2(n-x)=2(n-1)x+2(n-x)=2(n-1)例：无向树例：无向树T T中度为中度为4 4、3 3、2 2的结点各一个，其余为树叶，树叶？的结点各一个，其余为树叶，树叶？4+3+2+k=2(3+k-1)4+3+2+k=2(3+k-1)4)4)阶数阶数n n比较小的所有非同构的无向树比较小的所有非同构的无向树 例例1 1：画出：画出6 6阶所有阶所有非同构的无向树非同构的无向树 m=n-1=5 m=n-1=5 从树的节点之和来分析：结点之和为从树的节点之和来分析：结点之和为1010分配给分配给6 6个结点个结点 1 1

6、 1 1 1 5 1 1 1 1 1 5 1 1 1 1 2 4 1 1 1 1 2 4 1 1 1 1 3 3 1 1 1 1 3 3 1 1 1 2 2 3 1 1 1 2 2 3 1 1 2 2 2 2 1 1 2 2 2 2例例2 2：7 7阶无向树中有阶无向树中有3 3片树叶和片树叶和1 1个个3 3度顶点，其余度顶点，其余3 3个顶点的度数均无个顶点的度数均无1 1和和3 3试试画出满足要求的所有非同构的无向树画出满足要求的所有非同构的无向树 解答：从树的节点之和来分析：解答：从树的节点之和来分析：7 7阶无向阶无向树的边数树的边数m=m=（），），于是于是d(vi)d(vi)12

7、123 33+d(v5)+d(v6)+d(v7)3+d(v5)+d(v6)+d(v7)1 1 1 2 2 2 3 1 1 1 2 2 2 3 加入加入2 2，2 2，2 2 如何组成结点的度数序列使之不同构如何组成结点的度数序列使之不同构 主要分析：主要分析：度为度为3 3的结点的结点v v与其三个邻接点的关系与其三个邻接点的关系 邻接关系不同就能得到不同构的树邻接关系不同就能得到不同构的树三个三个邻接邻接点度数：点度数：1 1 2 1 2 2 2 2 21 1 2 1 2 2 2 2 24 4）任何无向任何无向连通连通图图G G，都，都存在生成树存在生成树 无无向连通图向连通图G G的生成的

8、生成树是树是不不唯一的唯一的3 3、生成树的应用、生成树的应用 要建要建6 6个工厂，修建连接的通路（见图），为使个工厂，修建连接的通路（见图），为使5 5处都有路相通，至少处都有路相通，至少要建几条路？如何铺设？要建几条路？如何铺设？由于由于n=6 n=6 所以建所以建5 5条路即可条路即可 4 4、无向图、无向图G G的生成树的确定：的生成树的确定：二种方法：二种方法：1 1、破圈法破圈法：每次去掉回路中的一条边，：每次去掉回路中的一条边，去掉总数为去掉总数为 m-n+1 m-n+1 条弦条弦 2 2、避圈法避圈法：由一个结点开始选一条边，：由一个结点开始选一条边，逐渐添加与边关联的结点（

9、只要不构成回路即可）逐渐添加与边关联的结点（只要不构成回路即可）直到所有结点被添加，直到所有结点被添加，(挑选挑选n-1n-1条边）条边）3 3、带权图的最小生成树、带权图的最小生成树 (1)(1)定义定义5 5 设无向连通带权图设无向连通带权图G GV W，T T是是G G的一棵生成树的一棵生成树 T T的各边权之和称为的各边权之和称为T T的的权权，记作，记作W(T)W(T)；G G的所有生成树中的所有生成树中权最小的生成树权最小的生成树称为称为G G的的最小生成树最小生成树。(2)(2)最小生成树的求法（这里介绍避圈法最小生成树的求法（这里介绍避圈法KruskalKruskal算法算法)

10、设设n n阶无向连通带权圈阶无向连通带权圈G GV E,W 有有m m条边，条边，不妨设不妨设G G中没有环中没有环(否则，可以将所有的环先删去否则，可以将所有的环先删去)，将，将m m条边按权从小到条边按权从小到大顺序排列，设为大顺序排列，设为e1,e2e1,e2，,em,em；取取e1e1在在T T中，然后依次检查中，然后依次检查e2e2，e3e3，em.em.若若ej(j2)ej(j2)与已在与已在T T中的边中的边 不能构成回路，则取不能构成回路，则取ejej在在T T中，否则弃去中，否则弃去ejej；算法停止时得到的算法停止时得到的T T为为G G的最小生成树。的最小生成树。避圈法避

11、圈法KruskalKruskal算法算法(n-1(n-1次次)1121241245(1)(2)(3)(4)破圈法破圈法(1)512436(3)1245(2)12435作业：作业：P319 P319 习题十六习题十六 1 1、2 2、3 3、4 4、5 5、131316.3 16.3 根树及其应用根树及其应用有向树：有向树：设设D D是是有向图，有向图，若若D D的基图是的基图是无向树无向树，则称则称D D为为有向树有向树.有向树中有向树中,根树最重要根树最重要,故只讨论根树故只讨论根树.一、根树一、根树 1 1、定义：设、定义：设T T是是n(n2)n(n2)阶有向树阶有向树,若若T T中中有

12、一个顶点的入有一个顶点的入度为度为0,0,其余顶点的入度均为其余顶点的入度均为1 1,则称则称T T为根树为根树。入度为入度为0 0的顶点称为的顶点称为树根树根（相当于（相当于文件系统的盘符文件系统的盘符）入度为入度为1 1出度为出度为0 0的顶点称为的顶点称为树叶树叶（具体文件）。（具体文件）。入度为入度为1 1出度不为出度不为0 0的顶点称为的顶点称为内点内点（文件夹），内（文件夹），内点和树根统称为点和树根统称为分支结点分支结点是否为根树是否为根树(a)(b)(c)(a)(b)(c)(no)(no)(yes)(no)(no)(yes)u从树根到从树根到T T的任意顶点的任意顶点v v的通

13、的通路路(路径路径)长度称为长度称为v v的层数的层数。v5v5的层数为的层数为 层。层。u层数最大顶点的层数称为层数最大顶点的层数称为树树高高将平凡树也称为根树。将平凡树也称为根树。u右右图中树高为（图中树高为（）。）。v1v2v3v4v5v6v7v8v9v10 在根树中，由于各有向边的方向是一在根树中，由于各有向边的方向是一致致的，的，所以画根树时可以省去各边上的所所以画根树时可以省去各边上的所有箭头，并将树根画在最上方有箭头，并将树根画在最上方2 2、根树中顶点的关系、根树中顶点的关系 定义：设定义：设T T为一棵非平凡的根树，为一棵非平凡的根树，vi,vjV(T),vi,vjV(T),

14、若若vivi可达可达vjvj,则称则称vivi为为vjvj的的祖先祖先,vjvj为为vivi的的后代后代；若若vivi邻接到邻接到vjvj(即即E(T)E(T)，称，称vivi为为vjvj的的父亲父亲,而而vjvj为为vivi的的儿子儿子若若vj,vkvj,vk的父亲相同，则称的父亲相同，则称vjvj与与vkvk是是兄兄弟弟v1v2v3v4v5v6v7v8v9v10v1v1为为v5v5的祖先的祖先,v5,v5为为v1v1的后代；的后代；v2v2为为v5v5的父亲的父亲,而而v5v5为为v2v2的儿子；的儿子；v4v4与与v5v5是兄弟是兄弟3 3、有序树、有序树 设设T T为根树，若将为根树，

15、若将T T中层数相同的顶点都标定次序，中层数相同的顶点都标定次序，则称则称T T为为有序树有序树 根据根树根据根树T T中每个分支点中每个分支点儿子数儿子数以及以及是否有序是否有序，可，可以将根树分成下列各类：以将根树分成下列各类：(1)(1)若若T T的每个分支点的每个分支点至多至多有有r r个儿子个儿子，则称，则称T T为为r r叉树叉树；又若又若r r叉树是有序的，则称它为叉树是有序的，则称它为r r叉叉有序树有序树 (2)(2)若若T T的每个分支点都的每个分支点都恰好恰好有有r r个儿子个儿子，则称，则称T T为为r r叉叉正正则树则树；又若又若T T是有序的，则称它为是有序的，则称

16、它为r r叉正则有序树叉正则有序树 (3)(3)若若T T是是r r叉正则树，且叉正则树，且每个树叶的层数均为树高每个树叶的层数均为树高，则，则称称T T为为r r叉叉完全完全正则树正则树，又若又若T T是有序的，则称它为是有序的，则称它为r r叉完全正则有序树叉完全正则有序树。v1v2v3v4v5v6v7v8v9v10二叉二叉有序有序树树v1v2v3v4v5v6v7 v8 v9 v10 v11 v12 v13 v14 v15二叉二叉完全完全正则正则有序有序树树四叉树四叉树(a)(b)(c)4 4、r r叉树的子树叉树的子树 定义：定义：设设T T为一棵根树，为一棵根树，v V(T)v V(T

17、)，称称v v及其后代的导出子图及其后代的导出子图TvTv为为T T的以的以v v为根的为根的根子树根子树 如：如：二二叉正则有序树的每个分支点的两个儿子导出叉正则有序树的每个分支点的两个儿子导出的根子树分别称为的根子树分别称为左子树左子树和和右子树右子树v1v2v3v4v5v6v7 v8 v9 v10 v11 v12 v13 v14 v15v2v4v5 v8 v9 v10 v11v3v6v7v12 v13 v14 v15左子树左子树右子树右子树二、根树的应用二、根树的应用1 1、最优、最优二二叉树定义：设叉树定义：设二二叉树叉树T T有有t t片树叶片树叶v1,v2,v1,v2,vt,vt,

18、权分别为权分别为w1,w2,w1,w2,wt,wt,称称 W(T)W(T)wi|(vi)wi|(vi)为为T T的权的权，其中其中|(vi)|(vi)是是vivi的层数（也可以是从根到该叶子的的层数（也可以是从根到该叶子的通路长度）通路长度）在所有有在所有有t t片树叶片树叶,带权带权w1,w2w1,w2，,wt,wt的的二二叉树中叉树中,总权值总权值W(T)W(T)最小的最小的二二叉树称为叉树称为最优最优二二叉树叉树 三棵带权三棵带权二二叉树叉树W(T1)W(T1)2 2（2+2)+32+2)+3*3+53+5*3+33+3*2 23838W(T2)W(T2)4(3+5)+34(3+5)+3

19、*3+23+2*2+22+24747W(T3)W(T3)3 3*(3+3)+5(3+3)+5*2+2(2+2)2+2(2+2)3636 2.Huffman2.Huffman算法算法(在给定权值下在给定权值下,如何构造最如何构造最优优二二叉树叉树)给定实数给定实数(权值权值)：w1w1，w2w2，wtwt，按从小到大，按从小到大排序为排序为w1w2w1w2wt.wt.(1)(1)连接权为连接权为w1,w2w1,w2的两片树叶的两片树叶,得一个分支点得一个分支点,其权其权为为w1+w2w1+w2(2)(2)在在w1+w2w1+w2，w3w3，w4w4，wtwt中选出两个权最小的，中选出两个权最小的

20、，连接它们对应的顶点连接它们对应的顶点(不一定是树叶不一定是树叶)，得新分支点及，得新分支点及所带的权所带的权(3)(3)重复重复(2),(2),直到形成直到形成t-1t-1个分支点个分支点,t,t片树叶为止片树叶为止例：例：求求2 2，2 2，3 3，3 3，5 5的最优二叉树的最优二叉树例：例：求求2 2，2 2，3 3，3 3，5 5的最优二叉树的最优二叉树2 2 2 24 43 3 3 36 6(2)(2)3 3，3 3，4 4，5 5(1)(1)2 2，2 2，3 3，3 3，5 5(3)(3)4 4，5 5，6 69 95 5(4)6(4)6，9 915153 3 3 36 6最优

21、二叉树总的原则是：权值较大的叶子距根较近，最优二叉树总的原则是：权值较大的叶子距根较近，权值较小的可以距根较远权值较小的可以距根较远例：给定一组权值例：给定一组权值3 3，5 5，6 6，9 9，1111，1414，1616，1818构造构造相应的最优二叉树相应的最优二叉树3 3、前缀编码、前缀编码 在通信中，常用二进制编码表示符号在通信中，常用二进制编码表示符号 1 1）等长编码与不等长编码：）等长编码与不等长编码：不等长编码可以使总电文总长度较短不等长编码可以使总电文总长度较短 2 2）不等长编码中编码的问题：如何识别？）不等长编码中编码的问题：如何识别？3)3)前缀编码定义：设前缀编码定

22、义：设a a1 1a a2 2，a an-1n-1a an n为长为为长为n n的符号串，的符号串，称其子串称其子串a a1 1,a,a1 1a a2 2,，a a1 1a a2 2a an-1n-1分别为该符号串的分别为该符号串的 长度为长度为1 1，2 2，n-1n-1的前缀的前缀 设设A Abb1 1，b b2 2，b bm m 为一个符号串集合，若对于任意的为一个符号串集合，若对于任意的b bi i，b bj jA(i j)A(i j)b bi i与与b bj j互不为前缀互不为前缀，则称，则称A A为为前缀码前缀码 若符号串若符号串b bi i(i(i1 1，2 2，m)m)中只出现

23、中只出现0 0，1 1两个符号，则两个符号，则称称A A为为二元前缀码二元前缀码 1 1，1 10 0，10101 1，01010101，1011010 0，01000100，010001001 1 不是前缀码不是前缀码 11，0000，011011，01010101，0100101001，01000 01000 为前缀码为前缀码 1 1，0101，1 11111，1 1100100，01011111 不是前缀码不是前缀码1,10,01,101,0101a,b,c ,d ,e2 2）利用二叉树产生二元前缀码）利用二叉树产生二元前缀码 规定二叉树的左子树的边为规定二叉树的左子树的边为0 0，右子

24、树的边为，右子树的边为1 1 则将从根到叶子结点的通路中边的序列即为叶子则将从根到叶子结点的通路中边的序列即为叶子的的二元前缀编码二元前缀编码111110000abcdea:00b:010c:011d:10e:111 通信中，每个字符出现的频率不同，如何使得通信中，每个字符出现的频率不同，如何使得传输效率最高？传输效率最高？等长的编码一定不是最好的，考虑利用二元前缀码。等长的编码一定不是最好的，考虑利用二元前缀码。3 3）最优二元前缀码最优二元前缀码 给定所需编码的字符的频率给定所需编码的字符的频率,构造字符的二元前缀构造字符的二元前缀编码，使其总电文长度为最短称为最优二元前缀编码，使其总电文

25、长度为最短称为最优二元前缀码。码。先利用哈夫曼算法，生成先利用哈夫曼算法，生成最优二叉树最优二叉树；再得到最优二元前缀码再得到最优二元前缀码例：传输例：传输100100个八进制的数字，其出现的频率分别为：个八进制的数字，其出现的频率分别为：0-25%0-25%，1-20%1-20%，2-15%2-15%，3-10%3-10%，4-10%4-10%，5-10%5-10%，6-5%6-5%，7-5%7-5%。用用最优二元前缀码传输需要多少二进制数字？最优二元前缀码传输需要多少二进制数字？用等长用等长码传输需要多少二进制数字？码传输需要多少二进制数字？先得到先得到最优二元前缀码最优二元前缀码利用哈夫

26、曼算法，利用哈夫曼算法，生成最优二叉树，生成最优二叉树，以频率为权值，以频率为权值，5,5,10,10,10,15,20,255,5,10,10,10,15,20,256,7,3,4,5,2,1,06,7,3,4,5,2,1,06 67 73 4 5 2 13 4 5 2 10 05,5,10,10,10,15,20,255,5,10,10,10,15,20,256,7,3,4,5,2,1,06,7,3,4,5,2,1,0编码：编码：6-00006-0000；7-00017-0001；3-0013-001；4-0104-010；5-0115-011；2-1002-100；1-101,0-111

27、-101,0-116 67 73 4 5 2 13 4 5 2 10 0总权总权值值:（100100个字符的个字符的bitbit数）数）W(T)=(5+5)W(T)=(5+5)*4+(10+10+10+15+20)4+(10+10+10+15+20)*3+253+25*2=2852=285等长码：等长码：0-0000-000；1-0011-001；2-0102-010；3-0113-011；4-1004-100；5-1015-101；6-1106-110；7-111.7-111.总权值总权值:W2=3:W2=3*100=300100=3004 4、二叉树的周游（遍历）、二叉树的周游（遍历）二叉

28、树的周游：对于一棵二叉树的每一个结点都访问一次且二叉树的周游：对于一棵二叉树的每一个结点都访问一次且仅一次的操作仅一次的操作 1 1）做一条绕行整个二叉树的行走路线（不能穿过树枝）做一条绕行整个二叉树的行走路线（不能穿过树枝）2 2）按行走路线经过结点的位置（左边、下边、右边）按行走路线经过结点的位置（左边、下边、右边）得到周游的方法有三种：得到周游的方法有三种：中序遍历（路线经过结点下边时访问结点）中序遍历（路线经过结点下边时访问结点）访问的次序：左子树访问的次序：左子树根根右子树右子树前序遍历（路线经过结点左边时访问结点）前序遍历（路线经过结点左边时访问结点）访问的次序：访问的次序：根根左

29、子树右子树左子树右子树后序遍历（路线经过结点右边时访问结点）后序遍历（路线经过结点右边时访问结点）访问的次序：左子树右子树访问的次序：左子树右子树根根abcdefghijk中序遍历（次序：左中序遍历（次序：左根根右右)前序遍历（次序：前序遍历（次序：根根左右左右)后序遍历（次序：左右后序遍历（次序：左右根根)中序遍历中序遍历:c b e d g f c b e d g f a a I k h j I k h j前序遍历前序遍历:a b c d e f g h i k ja b c d e f g h i k j后序遍历后序遍历:c e g f d b k i j h ac e g f d b

30、k i j h a例：给定二叉树，写出三种访问例：给定二叉树，写出三种访问结点的序列结点的序列例：给定二叉树周游的二种周游例：给定二叉树周游的二种周游序列，画出该二叉树序列，画出该二叉树5 5、二叉排序树、二叉排序树 将一组需要排序的序列建立二叉排序树将一组需要排序的序列建立二叉排序树 建立（不断添加结点为其子树：建立（不断添加结点为其子树：比根结点小的为左子树比根结点小的为左子树 比根结点大的为右子树比根结点大的为右子树 利用周游得出排序结果（中序遍历）利用周游得出排序结果（中序遍历）例：二叉排序树例：二叉排序树20,3,4,9,25,36,7,12,1820,3,4,9,25,36,7,1

31、2,18先建成二叉排序树先建成二叉排序树:以第一个数为根，以第一个数为根，比根小在左，比根小在左，比根大在右比根大在右.20749325361218建成二叉排序树建成二叉排序树后后:中序遍历中序遍历(走下面走下面):):3,4,7,9,12,18,20,25,363,4,7,9,12,18,20,25,366 6、表达式的、表达式的(逆逆)波兰式生成波兰式生成 给定表达式：（给定表达式：（a a*(b+c)+d(b+c)+d*e e*f)/(g+(h-i)f)/(g+(h-i)*j)j)表达式是中序遍历表达式是中序遍历运算符运算符对象对象对象对象/*+*c+abf*degjh-i对应的对应的二

32、叉树二叉树/*+*c+abf*degjh-i后序遍历的结果后序遍历的结果:(a(bc+)(a(bc+)*)(d(ef)(d(ef*)*)+)(g(hi-)j)+)(g(hi-)j*)+)/)+)/逆波兰式逆波兰式 ：=abc+=abc+*defdef*+ghi-j+ghi-j*+/+/计算机在运算该表达计算机在运算该表达式式时仅时仅按照一个原按照一个原则：扫描到一个运则：扫描到一个运算符就将它前面二算符就将它前面二个数进行运算个数进行运算/*+*c+abf*degjh-i前序遍历的结果：前序遍历的结果：(+(+(*a(+bc)(a(+bc)(*d(d(*ef)(+g(ef)(+g(*(-hi)j)(-hi)j)=/+=/+*a+bca+bc*d d*ef+gef+g*-hij-hij运算原则运算原则：运算符入栈，当扫描到两个数就进行最上：运算符入栈，当扫描到两个数就进行最上面的运算符的运算面的运算符的运算