离散数学及其应用第9章-树的基本理论与算法(上)课件.ppt

1、2022-8-5计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第9 9章章 树的基本理论与算法树的基本理论与算法（上）（上）2022-8-52022-8-5 根树的基本知识根树的基本知识2 2 特殊根树与算法特殊根树与算法3 3 无向树的基本知识无向树的基本知识1 1 树模型的应用树模型的应用4 4&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所4无向树的基本知识无向树的

2、基本知识2022-8-5计算机应用技术研究所计算机应用技术研究所5&无向树的基本知识无向树的基本知识J无向树的概念与性质无向树的概念与性质4无向图的生成树无向图的生成树4 最小生成树最小生成树2022-8-52022-8-5德德 国国法法 国国巴巴 西西哥伦比亚哥伦比亚阿根廷阿根廷比利时比利时荷荷 兰兰哥斯达黎加哥斯达黎加德国德国巴西巴西阿根廷阿根廷荷兰荷兰德国德国阿根廷阿根廷德国德国&树模型树模型1 1、连通无回路的无向图称、连通无回路的无向图称为为树树。2 2、树中悬挂结点称为、树中悬挂结点称为树叶树叶结点结点或或叶叶，其它结点称，其它结点称为为分支点分支点或或内点内点。&树模型树模型多个

3、树称为多个树称为森林森林123456789101512131114空树空树平凡图称为平凡图称为空树空树&树模型树模型a 图12345678b 图根根互为兄互为兄弟弟互为父子互为父子&树的层次性树的层次性2022-8-52022-8-5&树模型的定义树模型的定义【定义】连通无回路的无向图称为树，常用T表示树。2022-8-52022-8-5&树模型的定义树模型的定义树中没有环和平行边平行边，因此一定是简单图。简单图。定义中定义中“无回路无回路”在任何非平凡树中，都无度数为无度数为0的结点。定义中定义中“连通连通”【定义】树中悬挂结点称为树叶结点，简称为叶结点或叶，其他结点称为分支点或内点。【定义

4、】平凡图称为空树。所有连通分支均为树的无向图称为森林。2022-8-52022-8-5&例例 题题【例】判断图所示各个图模型是否为树或森林。【分析】直接利用树的定义进行判定2022-8-52022-8-5&例例 题题2022-8-52022-8-5&树的基本性质树的基本性质2022-8-52022-8-5&树的基本性质树的基本性质2022-8-52022-8-5&例例 题题【例】已知树T中有1个度为3的结点，2个度为2的结点，其余节点全是树叶，试求树叶数，并画出两个满足条件的非同构无向树。【分析】利用握手定理和m=n-1求解。【解】T的所有结点的度数分别为：1，1，1，2，2，3。2022-8

5、-5计算机应用技术研究所计算机应用技术研究所17&树的定义与性质树的定义与性质4无向树的概念与性质无向树的概念与性质J无向图的生成树无向图的生成树4 最小生成树最小生成树2022-8-52022-8-5&生成树的定义生成树的定义2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&生成树的存在性生成树的存在性2022-8-52022-8-5&生成树的存在性生成树的存在性2022-8-52022-8-5&生成树的构造生成树的构造2022-8-52022-8-5&例例 题题【例】分别用破圈法和避圈法求如图（a）所示的生成树。【分析

6、】分别用破圈法和避圈法依次进行即可。2022-8-52022-8-5破圈法破圈法&例例 题题2022-8-52022-8-5破圈法破圈法&例例 题题2022-8-52022-8-5避圈法避圈法&例例 题题2022-8-52022-8-5避圈法避圈法&例例 题题2022-8-52022-8-5&生成树的构造生成树的构造2022-8-52022-8-5&例例 题题【例】利用广度优先遍历算法求如图（a）所示的生成树。2022-8-52022-8-5&例例 题题【解】从任意结点开始，例如从a开始。2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52

7、022-8-50(-)0(-)1(a)1(a)1(a)1(a)2(c)2(c)2(b)2(b)3(e)3(e)3(e)3(e)3(e)3(e)4(d)4(d)4(h)4(h)b ba ac cd dg gj ji if fe eh h0(-)0(-)1(a)1(a)1(a)1(a)2(c)2(c)2(b)2(b)3(e)3(e)3(f)3(f)3(e)3(e)4(h)4(h)4(h)4(h)b ba ac cd dg gj ji if fe eh h&构造过程构造过程2022-8-5计算机应用技术研究所计算机应用技术研究所35&树的定义与性质树的定义与性质4 无向树的概念与性质无向树的概念与性

8、质4 无向图的生成树无向图的生成树J 最小生成树最小生成树2022-8-52022-8-5 无向图的生成树不唯一。同样地，赋权图的无向图的生成树不唯一。同样地，赋权图的最小生成树也不一定是唯一的。最小生成树也不一定是唯一的。&最小生成树最小生成树2022-8-52022-8-5&应用实例应用实例 要在要在 n n 个小区间建个小区间建立能源网，如何在保证立能源网，如何在保证 n n 个小区连通的前提下个小区连通的前提下最节省经费最节省经费?ABCDEF101015121287665即要使得生成树各边权值之和最小。即要使得生成树各边权值之和最小。2022-8-52022-8-5&普莱姆算法求解普

9、莱姆算法求解算法思想：算法思想：每次选择符合下列条件的边：每次选择符合下列条件的边：一端已入选，另一端未入选的权一端已入选，另一端未入选的权值最小的边。值最小的边。2022-8-52022-8-5要点：要点：从任意结点开始，每次从任意结点开始，每次增加增加一条一条最小权边最小权边构成一棵构成一棵新树新树。&算法描述算法描述ABCDEF101015121287665解：AB,C,D,E,F(A,B)/10(A,C)/12(A,E)/15设把A作为初始入选顶点：,B第1条边：(B,C)/7(B,D)/5(B,F)/6ABCDEF101015121287665解：A,BC,D,E,F(A,C)/12

10、；(A,E)/15；(B,C)/7(B,D)/5；(B,F)/6,D第2条边：；(D,F)/6ABCDEF101015121287665解：A,B,DC,E,F(A,C)/12；(A,E)/15；(B,C)/7(B,F)/6；(D,F)/6；,F第3条边：(F,C)/8；(F,E)/10；ABCDEF101015121287665解：A,B,D,FC,E(A,C)/12；(A,E)/15；(B,C)/7(F,C)/8；(F,E)/10；第4条边：,C(C,E)/12ABCDEF101015121287665解：A,B,D,F,CE(A,E)/15；(F,E)/10；(C,E)/12第5条边：,

11、E解：5ABCDEF10710ABCDEF1010151212876656注注：最小生成树不唯一，但权值之和相同。2022-8-52022-8-5&算法定理算法定理2022-8-52022-8-5&例例 题题【分析】根据普莱姆算法的步骤逐步构造。根据克鲁斯卡尔算法的基本思想，每次都选择和根据克鲁斯卡尔算法的基本思想，每次都选择和已选边不构成回路的权值最小的边已选边不构成回路的权值最小的边。ABDFCE105121512876610ABDFCE1057610&克鲁斯卡尔算法求解克鲁斯卡尔算法求解2022-8-52022-8-5要点：在与要点：在与已选取的边已选取的边不构成回路不构成回路的边中的边

12、中选取选取最小者最小者。&算法描述算法描述&算法求解算法求解2022-8-52022-8-5&算法定理算法定理2022-8-52022-8-5&例例 题题【解】依次取边如下：（C，D），（F，G），（C，G），（G，H），（A，C），（B，C），（H，I），（B，E）。具体过程如图(b)到(i)。2022-8-52022-8-5&例例 题题2022-8-52022-8-54 46 65 55 57 76 61 1f f9 92 23 3a ad db bc ci im mj jk ke eh hg g3 34 43 34 44 46 65 58 87 75 58 82 23 34 45 5k

13、k1 1f fe ec ch h3 34 4a a3 3i i5 5d dm m2 2g g2 2b bj j4 4&例例 题题2022-8-52022-8-5A AB BC CD DE E3 35 54 47 79 96 62 28 87 79 9&应用实例应用实例2022-8-52022-8-5&应用实例应用实例2022-8-52022-8-5无向树的基本知识无向树的基本知识1 1特殊根树与算法特殊根树与算法3 3根树的基本知识根树的基本知识2 2 树模型的应用树模型的应用4 4&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所58根树的基本知识根树的基本知

14、识2022-8-5计算机应用技术研究所计算机应用技术研究所59&根树的基本知识根树的基本知识J 有向树与根树有向树与根树4 根树的基本算法根树的基本算法4 前缀码与最优树前缀码与最优树2022-8-52022-8-5&有向树有向树2022-8-52022-8-5&例例对于所示若干有向图，略去其所有边的方向，则由图(a)、（b）得到的无向图都是树，而由图（c）得到的无向图有回路，由图（d）得到的无向图为森林。因此，图（a）、（b）均是有向树，图（c）、（d）均不是有向树。2022-8-52022-8-5&根树的定义根树的定义2022-8-52022-8-5&根树的定义根树的定义2022-8-52

15、022-8-5&根根 树树2022-8-52022-8-5v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8v v9 9v v1010v v1111v v1212v v1313&例例 题题2022-8-52022-8-5&根树的倒置画法根树的倒置画法2022-8-52022-8-5&根树的层次关系根树的层次关系2022-8-52022-8-5&例例如图表示一个具体的树模型结构如图表示一个具体的树模型结构。2022-8-52022-8-5&根树的家族关系根树的家族关系2022-8-52022-8-5&根树的家族关系根树的家族关系12345678根根互

16、为兄互为兄弟弟互为父子互为父子2022-8-52022-8-5&例例【例】如图表示一个具体的树模型结构。2022-8-52022-8-5&例题例题【例】分别用 10 个不同的正整数2,4,5,7,8,10,12,13,15,16标记 10 个文件(称为键值).为方便检索，请将它们以根树结构存储起来，使得每一个顶点上存储的文件的。【解】所求根树如图所示。2022-8-52022-8-5&例题例题【例】有 8 枚硬币，其中恰有 1 枚假币，假币比真币重.试用一天平称出假币，使称量的次数尽可能少。【分析】用 1,2,3,4,5,6,7,8 给 8 枚硬币编号，从而利用根树的思想求解。2022-8-5

17、2022-8-5&有序树有序树2022-8-52022-8-5&有序树的定义有序树的定义2022-8-52022-8-5&k k元树与元树与k k元完全元完全树树2022-8-52022-8-5&k k元树的定义元树的定义2022-8-52022-8-5&k k元有序树的定义元有序树的定义2022-8-52022-8-5&子树的概念子树的概念2022-8-52022-8-5&子树的定义子树的定义2022-8-52022-8-5&例例 题题2022-8-52022-8-5&分支点与叶结点分支点与叶结点2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022

18、-8-52022-8-5&例题例题【例】已知有一棵含有已知有一棵含有 2010 2010 个结点的完全二元树，个结点的完全二元树，问总共有问总共有多少叶子结点？多少叶子结点？【分析】利用完全二元树的性质求解。【解】易知完全二元树的各层结点数依次为：1,2,4,8,16,32,64,128,显然可求得前 10 层的结点数为 1023，故第 11 层共有叶子为：2010-1023=987(片)。这 987 片叶子是从第 10 层的 INT(987/2)+1=494 个父亲结点那里映射出来的，换句话说，第 10 层尚有 512-494=18 个结点没有儿子，所以，这 18 个没有儿子的结点也是叶子，

19、综上，这课完全二元树的叶子总数为：987+18=1005(片)。2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所88&根树的基本知识根树的基本知识4 有向树与根树有向树与根树J 根树的基本算法根树的基本算法4 前缀码与最优树前缀码与最优树2022-8-52022-8-5&根树的遍历根树的遍历2022-8-52022-8-5&二元树的遍历二元树的遍历2022-8-52022-8-5&二元树的遍历二元树的遍历2022-8-52022-8-5&二元树的遍历二元树的遍历&例例 题题&例例 题题【例】写出对图

20、中二元树使用三种遍历方法得到的结果【解】先根遍历：abdgehicfjkl；中根遍历次序为：gdbheiajflkc；后根遍历次序为：gdhiebjlkfca&例例 题题【解】该命题公式为中根遍历模式，故二元树表示如图所示&例例 题题【解】【例】算术表达式(a(b+c)d2)(a(bc)可以用图中的2元树来表示.其中*表示数乘运算，表示指数运算.分别用三种2元树。2022-8-52022-8-5&根树化为二元树根树化为二元树&例例 题题&例例 题题2022-8-52022-8-5&森林化为二元树森林化为二元树2022-8-52022-8-5将二元树转化为森林，要点是将二元树转化为森林，要点是“

21、先将根的右子树先将根的右子树变为新二元树变为新二元树，再将这些二元树还原为根树再将这些二元树还原为根树”。&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所102&根树的基本知识根树的基本知识4 有向树与根树有向树与根树4 根树的基本算法根树的基本算法J 前缀码与最优树前缀码与最优树2022-8-52022-8-5&编码的效率编码的效率2022-8-52022-8-5&问题的提出问题的提出2022-8-52022-8-5&前缀的概念前缀的概念2022-8-52022-8-5&前缀码的定义前缀码的定义2022-8-52022-8-5&用二元树构造前缀码用二元树构造前缀码2022

22、-8-52022-8-5&前缀码的构造算法前缀码的构造算法2022-8-52022-8-5&例例 题题【例例】求图所示二元树产生的前缀码。求图所示二元树产生的前缀码。【解解】000000，001001，0101，1010，11112022-8-52022-8-5&例例 题题【例例】求图中各个字符的前缀码。求图中各个字符的前缀码。【解解】各字符前缀码为：各字符前缀码为：A A：1 1；B B：0101；C C：001001；D:000D:0002022-8-52022-8-5&例例 题题【例例】前缀码前缀码00000000，00010001，001001，010010，011011，100100

23、，101101，1111对应的有序二元树如下图所示：对应的有序二元树如下图所示：v00110101001010100000001001010011100101112022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题如果收到一串数字：如果收到一串数字：1111，010010，011011，101101，011011，100100，001001，00000000，00010001，00000000，100100，001001，00000000，100100。Zhixingafangan执行执行A方案方案2022-8-52022-8-5&例例 题题2022-8-5

24、2022-8-5&最优树的概念最优树的概念2022-8-52022-8-5&最优树定理最优树定理2022-8-52022-8-5&霍夫曼算法霍夫曼算法2022-8-52022-8-5&霍夫曼算法描述霍夫曼算法描述2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题【例】求带权5、6、9、11、15的最优树。【解】全部过程如图（a）-（d）所示。2022-8-52022-8-5&例例 题题【例】已知在通信中，十进制数字出现的频率是：求传输它们的最佳前缀码，当用最佳前缀码传输 10000 个按上述频率出现的数字需要多少个二进制码？2022-8-52022-8-5&例例 题题构造一棵带权5,5,5,10,10,10,10,10,15,20 的最优二元树如图所示。所以最佳前缀码为：2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5&例例 题题2022-8-52022-8-5计算机应用技术研究所计算机应用技术研究所126126