第4篇 图论之树

1、82-82-1 1第第1010章章 树树 树树是图论中的一个非常重要的概念，而在计算是图论中的一个非常重要的概念，而在计算机科学中有着非常广泛的应用，例如机科学中有着非常广泛的应用，例如现代计算机操现代计算机操作系统作系统均采用树形结构来组织文件和文件夹，本章均采用树形结构来组织文件和文件夹，本章介绍树的介绍树的基本知识和应用基本知识和应用。 在本章中，所谈到的图都假定是在本章中，所谈到的图都假定是简单图简单图；所谈；所谈到的回路均指到的回路均指简单回路简单回路或或基本回路基本回路。并且同一个图。并且同一个图形表示的回路形表示的回路( (简单的或基本的简单的或基本的) )，可能有不同的，可能有

2、不同的交交替序列替序列表示方法，但我们规定它们表示的是同一条表示方法，但我们规定它们表示的是同一条回路。回路。82-82-2 210.0 10.0 内容提要内容提要 1.1. 与树相关的概念：与树相关的概念： 树、森林、根树、根、叶、树、森林、根树、根、叶、分支点、生成树、最小生成树、分支点、生成树、最小生成树、k k元树、元树、k k元完元完全树子树、有序树、祖先与后代、父亲与儿子、全树子树、有序树、祖先与后代、父亲与儿子、最优树等；最优树等；2.2. 树的基本性质：树的基本性质：m = n-1m = n-1等；等；3.3. 树的算法：求生成树与最小生成树的算法、求树的算法：求生成树与最小生

3、成树的算法、求最优树的算法、二元树遍历的算法、根树与二最优树的算法、二元树遍历的算法、根树与二元树相互转化的算法等；元树相互转化的算法等；4.4. 树的应用。树的应用。82-82-3 310.1 10.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 与树相关基与树相关基本概念本概念2 2 树的性质树的性质3 3 树的基本算树的基本算法法 31 1 树的同构树的同构2 2 树的应用树的应用2树的算法树的算法 82-82-4 410.2 10.2 树树 10.2.1 10.2.1 树的定义与性质树的定义与性质例例10.2.110.2.1 2006 2006年德国世界杯

4、年德国世界杯8 8强的比赛结果图，强的比赛结果图，最后胜利的队捧得大力神杯。最后胜利的队捧得大力神杯。德德 国国阿根廷阿根廷意大利意大利乌克兰乌克兰英格兰英格兰葡萄牙葡萄牙巴巴 西西法法 国国德德 国国意大利意大利葡萄牙葡萄牙法法 国国意大利意大利法法 国国意大利意大利82-82-5 5定义定义10.2.110.2.1n连通而不含回路的无向图称为连通而不含回路的无向图称为无向树无向树(Undirected (Undirected Tree)Tree)，简称，简称树树(Tree)(Tree)，常用，常用T T表示树。表示树。n树中度数为树中度数为1 1的结点称为的结点称为叶叶(Leaf)(Lea

5、f)；度数大于；度数大于1 1的的结点称为结点称为分支点分支点(Branch Point)(Branch Point)或或内部结点内部结点(Interior Point)(Interior Point)。n每个连通分支都是树的无向图称为每个连通分支都是树的无向图称为森林森林(Forest)(Forest)。n平凡图称为平凡图称为平凡树平凡树(Trivial Tree)(Trivial Tree)。 树中树中没有没有环环和和平行边平行边，因此一定是，因此一定是简单图简单图 在任何非平凡树中，都在任何非平凡树中，都无度数为无度数为0 0的结点。的结点。82-82-6 6例例10.2.210.2.2

6、判断下图中的图哪些是树？为什么？判断下图中的图哪些是树？为什么？ (a)(a)(b)(b)(c)(c)(d)(d)分析分析 判断无向图是否是树，根据定义判断无向图是否是树，根据定义10.2.110.2.1，首，首先看它是否连通，然后看它是否有回路。先看它是否连通，然后看它是否有回路。解解 图图(a)(a)、(b)(b)都是连通，并且不含回路，因此是都是连通，并且不含回路，因此是树；图树；图(c)(c)不连通，因此不是树，但由于它不含回不连通，因此不是树，但由于它不含回路，因此是森林；图路，因此是森林；图(d)(d)虽然连通，但存在回路，虽然连通，但存在回路，因此不是树。因此不是树。82-82-

7、7 7树的性质树的性质 定理定理10.2.110.2.1 设无向图设无向图G = G = ，|V| = n|V| = n，|E| = m|E| = m，下列各命题是等价的：下列各命题是等价的： G G连通而不含回路连通而不含回路( (即即G G是树是树) )； G G中中无回路无回路，且，且m = n-1m = n-1； G G是是连通的连通的，且，且m = n-1m = n-1； G G中中无回路无回路，但在，但在G G中中任二结点之间增加一条新边，任二结点之间增加一条新边，就得到惟一的一条基本回路就得到惟一的一条基本回路； G G是是连通的连通的，但，但删除删除G G中任一条边后，便不连通

8、中任一条边后，便不连通；(n2)(n2) G G中中每一对结点之间有惟一一条基本通路每一对结点之间有惟一一条基本通路。(n2)(n2)82-82-8 8定理定理10.2.1 10.2.1 分析分析 直接证明这直接证明这6 6个命题两两等价工作量太大，一个命题两两等价工作量太大，一般采用循环论证的方法，即证明般采用循环论证的方法，即证明(1) (2) (3) (4) (5) (6) (1)(1) (2) (3) (4) (5) (6) (1)然后利用传递行，得到结论。然后利用传递行，得到结论。82-82-9 9定理定理10.2.1 10.2.1 证明证明 (1) (2)(1) (2)： 对对n

9、n作归纳。作归纳。n = 1n = 1时，时，m = 0m = 0，显然有，显然有m = n-m = n-1 1。假设。假设n = kn = k时命题成立，现证时命题成立，现证n = k+1n = k+1时也成立。时也成立。 由于由于G G连通而无回路，所以连通而无回路，所以G G中至少有一个度数中至少有一个度数为为1 1的结点的结点v v0 0，在，在G G中删去中删去v v0 0及其关联的边，便得到及其关联的边，便得到k k个结点的连通而无回路的图，由归纳假设知它有个结点的连通而无回路的图，由归纳假设知它有k-1k-1条边。再将结点条边。再将结点v v0 0及其关联的边加回得到原图及其关联

10、的边加回得到原图G G，所以所以G G中含有中含有k+1k+1个结点和个结点和k k条边，符合公式条边，符合公式m = n-1m = n-1。 所以，所以，G G中无回路，且中无回路，且m = n-1m = n-1。 G G连通而不含回路连通而不含回路( (即即G G是树是树) ) G G中中无回路无回路，且，且m = n-1m = n-1；82-82-1010(2) (3)(2) (3)： 证明只有一个连通分支。证明只有一个连通分支。 设设G G有有k k个连通分支个连通分支G G1 1，G G2 2，G Gk k，其结点数，其结点数分别为分别为n n1 1，n n2 2，n nk k，边数

11、分别为，边数分别为m m1 1，m m2 2，m mk k，且，且 ， 。 由于由于G G中无回路，所以每个中无回路，所以每个G Gi i(i(i = 1, 2, = 1, 2, , , k)k)均为树，因此均为树，因此m mi i = n = ni i-1(i = 1, 2, -1(i = 1, 2, , k), k)，于，于是是 故故k = 1k = 1，所以，所以G G是连通的，且是连通的，且m = n-1m = n-1。 k ki ii=1i=1n =nn =n k ki ii=1i=1m =mm =mkkkkiiiii=1i=1i=1i=1m =m =(n -1)= n-k = n-

12、1m =m =(n -1)= n-k = n-1 G G中中无回路无回路，且，且m = n-1m = n-1； G G是是连通的连通的，且，且m = n-1m = n-1；82-82-1111(3) (4)(3) (4)： 首先证明首先证明G G中无回路。对中无回路。对n n作归纳。作归纳。 n = 1 n = 1时，时，m = n-1 = 0m = n-1 = 0，显然无回路。，显然无回路。 假设结点数假设结点数n = k-1n = k-1时无回路，下面考虑结点时无回路，下面考虑结点数数n = kn = k的情况。因的情况。因G G连通，故连通，故G G中每一个结点的度中每一个结点的度数均大

13、于等于数均大于等于1 1。可以证明至少有一个结点。可以证明至少有一个结点v v0 0，使，使得得deg(vdeg(v0 0) = 1) = 1，因若，因若k k个结点的度数都大于等于个结点的度数都大于等于2 2，则则 ，从而，从而mkmk，即至少有，即至少有k k条边，但这与条边，但这与m = n-1m = n-1矛盾。矛盾。 v vV V2 2m m = =d de eg g( (v v) )2 2k k G G是是连通的连通的，且，且m = n-1m = n-1； G G中中无回路无回路，但在，但在G G中中任二结点之间增加一任二结点之间增加一条新边，就得到惟一的一条基本回路条新边，就得到

14、惟一的一条基本回路；82-82-1212 在在G G中删去中删去v0v0及其关联的边，得到新图及其关联的边，得到新图GG，根，根据归纳假设知据归纳假设知GG无回路，由于无回路，由于deg(vdeg(v0 0) = 1) = 1，所以，所以再将结点再将结点v v0 0及其关联的边加回得到原图及其关联的边加回得到原图G G，则，则G G也无也无回路。回路。 其次证明在其次证明在G G中任二结点中任二结点v vi i，v vj j之间增加一条之间增加一条边边(v(vi i, , v vj j) )，得到一条且仅一条基本回路。，得到一条且仅一条基本回路。 由于由于G G是连通的，从是连通的，从v vi

15、 i到到v vj j有一条通路有一条通路L L，再在，再在L L中增加一条边中增加一条边(v(vi i, , v vj j) )，就构成一条回路。若此，就构成一条回路。若此回路不是惟一和基本的，则删去此新边，回路不是惟一和基本的，则删去此新边，G G中必有中必有回路，得出矛盾。回路，得出矛盾。82-82-1313(4) (5)(4) (5)： 若若G G不连通，则存在两结点不连通，则存在两结点vivi和和vjvj，在，在vivi和和vjvj之间无通路，此时增加边之间无通路，此时增加边(vi, (vi, vjvj) )，不会产生回路，不会产生回路，但这与题设矛盾。但这与题设矛盾。 由于由于G G

16、无回路，所以删去任一边，图便不连通。无回路，所以删去任一边，图便不连通。 G G中中无回路无回路，但在，但在G G中中任二结点之间增加一条新任二结点之间增加一条新边，就得到惟一的一条基本回路边，就得到惟一的一条基本回路； G G是是连通的连通的，但，但删除删除G G中任一条边后，便不连通中任一条边后，便不连通；(n2)(n2)82-82-1414 G G是是连通的连通的，但，但删除删除G G中任一条边后，便不连通中任一条边后，便不连通；(n2)(n2) G G中中每一对结点之间有惟一一条基本通路每一对结点之间有惟一一条基本通路。(n2)(n2)(5) (6)(5) (6)： 由于由于G G是连

17、通的，因此是连通的，因此G G中任二结点之间都有通中任二结点之间都有通路，于是有一条基本通路。若此基本通路不惟一，路，于是有一条基本通路。若此基本通路不惟一，则则G G中含有回路，删去回路上的一条边，中含有回路，删去回路上的一条边，G G仍连通，仍连通，这与题设不符。所以此基本通路是惟一的。这与题设不符。所以此基本通路是惟一的。82-82-1515(6) (1)(6) (1)： 显然显然G G是连通的。若是连通的。若G G中含回路，则回路上任二中含回路，则回路上任二结点之间有两条基本通路，这与题设矛盾。因此，结点之间有两条基本通路，这与题设矛盾。因此，G G连通且不含回路。连通且不含回路。 G

18、 G中中每一对结点之间有惟一一条基本通路每一对结点之间有惟一一条基本通路。(n2)(n2) G G连通而不含回路连通而不含回路( (即即G G是树是树) )；82-82-1616树的特点树的特点在结点给定的无向图中，在结点给定的无向图中， 树是边数最多的无回路图树是边数最多的无回路图 树是边数最少的连通图树是边数最少的连通图由此可知，在无向图由此可知，在无向图G = (n, m)G = (n, m)中，中， 若若m mn-1n-1，则，则G G是不连通的是不连通的 若若m mn-1n-1，则，则G G必含回路必含回路由定理由定理10.2.1(4)10.2.1(4)由定理由定理10.2.1(5)

19、10.2.1(5)82-82-1717定理定理10.2.210.2.2任意非平凡树任意非平凡树T = (n, m) T = (n, m) 都至少有两片叶。都至少有两片叶。分析分析 利用握手定理和利用握手定理和m = n-1m = n-1即可。即可。证明证明 因树因树T T是连通的，从而是连通的，从而T T中各结点的度数均大中各结点的度数均大于等于于等于1 1。设。设T T中有中有k k个度数为个度数为1 1的结点的结点( (即即k k片叶片叶) )，其余的结点度数均大于等于其余的结点度数均大于等于2 2。 由于树中有由于树中有m = n-1m = n-1，于是，于是2(n-1)2n-k2(n-

20、1)2n-k，因，因此可得此可得k2k2，这说明，这说明T T中至少有两片叶。中至少有两片叶。 v Vv V2m =deg(v)k + 2(n - k) = 2n - k2m =deg(v)k + 2(n - k) = 2n - k于是由握手定理于是由握手定理82-82-181810.2.2 10.2.2 生成树生成树 定义定义10.2.210.2.2 给定图给定图G = G = ，若，若G G的某个的某个生成生成子图子图是是树树，则称之为，则称之为G G的的生成树生成树(Spanning Tree)(Spanning Tree)，记为记为T TG G。生成树。生成树T TG G中的边称为中的

21、边称为树枝树枝(Branch)(Branch)；G G中中不在不在T TG G中的边称为中的边称为弦弦(Chord)(Chord)；T TG G的所有弦的集合的所有弦的集合称为生成树的称为生成树的补补(Complement)(Complement)。 82-82-1919例例10.2.310.2.3判断下图中的图判断下图中的图(b)(b)、(c)(c)、(d)(d)、(e)(e)是否是图是否是图(a)(a)的生成树。的生成树。a ab bc cd de ef f(a)(a)a ab bc cd de ef f(b)(b)a ab bc cd de ef f(c)(c)a ab bc cd de

22、 ef f(d)(d)b bc cd de ef f(e)(e)分析分析 判断是否是生成树，根据定义判断是否是生成树，根据定义10.2.210.2.2，首先，首先看它是否是树，然后再看它是否是生成子图。由于看它是否是树，然后再看它是否是生成子图。由于图图(b)(b)和和(d)(d)不是树，图不是树，图(e)(e)不是生成子图，因此它不是生成子图，因此它们都不是图们都不是图(a)(a)的生成树，而图的生成树，而图(c)(c)既是树，又是生既是树，又是生成子图，因此是生成树。成子图，因此是生成树。解解 图图(b)(b)、(d)(d)和和(e)(e)不是图不是图(a)(a)的生成树，图的生成树，图(

23、c)(c)是图是图(a)(a)的生成树，其中边的生成树，其中边(a, c)(a, c)、(a, d)(a, d)、(b, (b, f)f)、(c, f)(c, f)、(c, e)(c, e)是树枝，而是树枝，而(a, b)(a, b)、(b, c)(b, c)、(c, d)(c, d)、(d, e)(d, e)、(e, f)(e, f)是弦。是弦。82-82-2020定理定理10.2.310.2.3一个图一个图G = G = 存在生成树存在生成树T TG G = V = 的充分的充分必要条件是必要条件是G G是连通的。是连通的。分析分析 必要性由树的定义即得，充分性利用构造性必要性由树的定义即

24、得，充分性利用构造性方法，具体找出一颗生成树即可方法，具体找出一颗生成树即可证明证明 必要性：假设必要性：假设T TG G = V = 是是G = G = 的生的生成树，由定义成树，由定义10.2.110.2.1，T TG G是连通的，于是是连通的，于是G G也是连通的。也是连通的。 充分性：假设充分性：假设G = G = 是连通的。如果是连通的。如果G G中无回中无回路，路，G G本身就是生成树。如果本身就是生成树。如果G G中存在回路中存在回路C C1 1，可删除，可删除C C1 1中一条边得到图中一条边得到图G1G1，它仍连通且与，它仍连通且与G G有相同的结点集。有相同的结点集。如果如

25、果G G1 1中无回路，中无回路，G G1 1就是生成树。如果就是生成树。如果G G1 1仍存在回路仍存在回路C C2 2，可删除可删除C C2 2中一条边，如此继续，直到得到一个无回路中一条边，如此继续，直到得到一个无回路的连通图的连通图H H为止。因此，为止。因此，H H是是G G的生成树。的生成树。82-82-2121破圈法与避圈法破圈法与避圈法n 算法算法10.2.110.2.1 求连通图求连通图G = G = 的生成树的的生成树的破圈法破圈法：每次每次删除回路中的一条边删除回路中的一条边，其删除的边的总数，其删除的边的总数为为m-n+1m-n+1。n 算法算法10.2.210.2.2

26、 求连通图求连通图G = G = 的生成树的的生成树的避圈法避圈法：每次每次选取选取G G中一条与已选取的边不构成回路的边中一条与已选取的边不构成回路的边，选取的边的总数为选取的边的总数为n-1n-1。由于由于删除回路上的边和选择不构成任何回路的边有删除回路上的边和选择不构成任何回路的边有多种选法多种选法，所以产生的，所以产生的生成树不是惟一的生成树不是惟一的。 82-82-2222例例10.2.410.2.4分别用破圈法和避圈法求下图的生成树。分别用破圈法和避圈法求下图的生成树。 1 12 23 34 45 56 6分析分析 分别用破圈法和避圈法依次进行即可。用破圈法时，分别用破圈法和避圈法

27、依次进行即可。用破圈法时，由于由于n = 6n = 6，m = 9m = 9，所以，所以m-n+1 = 4m-n+1 = 4，故要删除的边数为，故要删除的边数为4 4，因此只需因此只需4 4步即可。用避圈法时，由于步即可。用避圈法时，由于n = 6n = 6，所以，所以n-1 = 5n-1 = 5，故要选取故要选取5 5条边，因此需条边，因此需5 5步即可。步即可。 破圈法破圈法82-82-2323避圈法避圈法 由于由于生成树的形式生成树的形式不惟一不惟一，故上述两棵生成树，故上述两棵生成树都是所求的。都是所求的。 破圈法和避圈法的破圈法和避圈法的计算量较大计算量较大，主要是，主要是需要找需要

28、找出回路出回路或或验证不存在回路验证不存在回路。 1 12 23 34 45 56 61 12 23 34 45 56 682-82-2424算法算法10.2.310.2.3求连通图求连通图G = G = 的生成树的的生成树的广度优先搜索算法广度优先搜索算法：（1 1）任选任选sVsV，将，将v v标记为标记为0 0，令，令L = sL = s，V = V = V-sV-s，k = 0k = 0；（2 2）如果如果V = V = ，则转，则转(4)(4)，否则令，否则令k = k+1k = k+1；（3 3）依次对依次对L L中所有标记为中所有标记为k-1k-1的结点的结点v v，如果它与，如

29、果它与V V中的结点中的结点w w相邻接，则将相邻接，则将w w标记为标记为k k，指定，指定v v为为w w的前驱，令的前驱，令L = L = LwLw ，V = V-wV = V-w，转，转(2)(2)；（4 4）E EG G = (v, = (v, w)|wL-sw)|wL-s ，v v为为w w的前驱的前驱 ，结，结束。束。82-82-2525例例10.2.510.2.5利用广度优先搜索算法求下图的生成树。利用广度优先搜索算法求下图的生成树。 0(-)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

30、)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 h82-82-262610.2.3 10.2.3 最小生成树最小生成树 定义定义10.2.310.2.3 设设G = G = 是是连通的赋权图连通的赋权图，T T是是G G的一棵生成树，的一棵生成树，T T的每个的每个树枝所赋权值之和树枝所赋权值之和称为称为T T的的权权(Weight)(Weight

31、)，记为，记为w(Tw(T) )。G G中具有中具有最小权的生成最小权的生成树树称为称为G G的的最小生成树最小生成树(Minimal Spanning Tree)(Minimal Spanning Tree)。 一个无向图的生成树不是惟一的，同样地，一个无向图的生成树不是惟一的，同样地，一个赋权图的最小生成树也不一定是惟一的。一个赋权图的最小生成树也不一定是惟一的。82-82-2727算法算法10.2.3 10.2.3 KruskalKruskal算法算法 （1 1）在在G G中选取中选取最小权边最小权边e e1 1，置，置i = 1i = 1。（2 2）当当i = n-1i = n-1时，

32、结束，否则转时，结束，否则转(3)(3)。（3 3）设已选取的边为设已选取的边为e e1 1, e, e2 2, , , , e ei i，在，在G G中选取中选取不同于不同于e e1 1, e, e2 2, , , , e ei i的边的边e ei+1i+1，使，使ee1 1, e, e2 2, , , , e ei i, , e ei+1i+1 中中无回路无回路且且e ei+1i+1是满足此条件的是满足此条件的最小权边最小权边。（4 4）置置i = i+1i = i+1，转，转(2)(2)。要点：在与要点：在与已选取的边已选取的边不构成回路不构成回路的边中的边中选取选取最小者最小者。 在在

33、KruskalKruskal算法的步骤算法的步骤1 1和和3 3中，若满足条件中，若满足条件的最小权边不止一条，则可从中任选一条，这样的最小权边不止一条，则可从中任选一条，这样就会产生不同的最小生成树。就会产生不同的最小生成树。82-82-2828例例10.2.610.2.6用用KruskalKruskal算法求图中赋权图的最小生成树。算法求图中赋权图的最小生成树。4 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 k1

34、1f fe ec ch h3 34 4a a3 3i i5 5d dm m2 2g g2 2b bj j4 4解解 n=12n=12，按算法要执行，按算法要执行n-1=11n-1=11次，次，w(Tw(T) = 36) = 36。 82-82-2929算法算法10.2.5 Prim10.2.5 Prim算法算法 （1 1）在在G G中任意选取一个结点中任意选取一个结点v v1 1，置，置VT = vVT = v1 1, E, ET T = = ，k = 1k = 1；（2 2）在在V-VV-VT T中选取与某个中选取与某个v vi iVVT T邻接的结点邻接的结点vjvj，使，使得边得边(v(

35、vi i, , v vj j) )的权最小，置的权最小，置V VT T = = V VT Tvvj j, E, ET T = = E ET T(v(vi i, , v vj j)，k = k+1k = k+1；（3 3）重复步骤重复步骤2 2，直到，直到k = |V|k = |V|。要点：要点：从任意结点开始，每次从任意结点开始，每次增加增加一条一条最小权边最小权边构成一棵构成一棵新树新树。 在在PrimPrim算法的步骤算法的步骤2 2中，若满足条件的最小中，若满足条件的最小权边不止一条，则可从中任选一条，这样就会产权边不止一条，则可从中任选一条，这样就会产生不同的最小生成树。生不同的最小生

36、成树。 82-82-3030例例10.2.710.2.7用用PrimPrim算法求图中赋权图的最小生成树。算法求图中赋权图的最小生成树。 5 5f f10102 2d db bc ce e7 7g g6 64 45 58 82 2a a7 7g ge e2 2f f5 5b b4 42 2c ca ad d5 5解解 n = 7n = 7，按算法要执行，按算法要执行n-1 = 6n-1 = 6次，次，w(Tw(T) = 25) = 25。 由由PrimPrim算法可以看出，每一步得到的图一定算法可以看出，每一步得到的图一定是树，故不需要验证是否有回路，因此它的计算是树，故不需要验证是否有回路，

37、因此它的计算工作量较工作量较KruskalKruskal算法要小。算法要小。 82-82-313110.2.4 10.2.4 无向树的难点无向树的难点 1.1. 树是不含回路的连通图。注意把握树的性质，树是不含回路的连通图。注意把握树的性质，特别是树中叶结点的数目及边数与结点数的关特别是树中叶结点的数目及边数与结点数的关系：系：m = n-1m = n-1；2.2. 生成树是无向连通图是树的生成子图。注意把生成树是无向连通图是树的生成子图。注意把握所有连通图都有生成树，知道生成树的树枝握所有连通图都有生成树，知道生成树的树枝与弦及其数目，会使用避圈法、破圈法和广度与弦及其数目，会使用避圈法、破

38、圈法和广度优先搜索算法求生成树；优先搜索算法求生成树；3.3. 最小生成树是赋权连通图的权值之和最小的生最小生成树是赋权连通图的权值之和最小的生成树。会使用成树。会使用KruskalKruskal算法和算法和PrimPrim算法求最小生算法求最小生成树。成树。 82-82-323210.2.5 10.2.5 无向树的应用无向树的应用 例例10.2.810.2.8 假设有假设有5 5个信息个信息中心中心A A、B B、C C、D D、E E，它们之间，它们之间的距离的距离( (以百公里为单位以百公里为单位) )如图所如图所示。要交换数据，我们可以在任示。要交换数据，我们可以在任意两个信息中心之间

39、通过光纤连接，但是费用的限意两个信息中心之间通过光纤连接，但是费用的限制要求铺设尽可能少的光纤线路。重要的是每个信制要求铺设尽可能少的光纤线路。重要的是每个信息中心能和其它中心通信，但并不需要在任意两个息中心能和其它中心通信，但并不需要在任意两个中心之间都铺设线路，可以通过其它中心转发。中心之间都铺设线路，可以通过其它中心转发。 A AB BC CD DE E3 35 54 47 79 96 62 28 87 79 9A AB BC CD DE E3 34 46 62 2分析分析 这实际上就是求赋权连通图的最小生成树问这实际上就是求赋权连通图的最小生成树问题，可用题，可用PrimPrim算法或

40、算法或KruskalKruskal算法求解。算法求解。解解 求得图的最小生成树如图所示，求得图的最小生成树如图所示，w(Tw(T) = 15) = 15百百公里。即按图的图铺设，使得铺设的线路最短。公里。即按图的图铺设，使得铺设的线路最短。 82-82-333310.3 10.3 根树根树 10.3.1 10.3.1 根树的定义与分类根树的定义与分类 定义定义10.3.110.3.1 一个有向图，若一个有向图，若略去略去所有有向边的所有有向边的方方向向所得到的所得到的无向图无向图是一棵是一棵树树，则这个有向图称为，则这个有向图称为有有向树向树(Directed Tree)(Directed T

41、ree)。 82-82-3434例例10.3.110.3.1判断下图中的图哪些是树？为什么？判断下图中的图哪些是树？为什么？(a)(a)(c)(c)(e)(e)(d)(d)(b)(b)82-82-3535定义定义10.3.210.3.2一棵一棵非平凡的有向树非平凡的有向树，如果，如果恰有一个结点的入度为恰有一个结点的入度为0 0，其余所有结点的入度均为其余所有结点的入度均为1 1，则称之为，则称之为根树根树(Root Tree)(Root Tree)或或外向树外向树(Outward Tree)(Outward Tree)。入度为入度为0 0的结点称为的结点称为根根(Root)(Root)；出度

42、为出度为0 0的结点称为的结点称为叶叶(Leaf)(Leaf)；入度为入度为1 1，出度大于，出度大于0 0的结点称为的结点称为内点内点(Interior Point)(Interior Point)；又将；又将内点和根内点和根统称为统称为分支点分支点(Branch Point)(Branch Point)。在根树中，从。在根树中，从根到任一结点根到任一结点v v的的通路长度通路长度，称为该结点的，称为该结点的层数层数(Layer Number)(Layer Number)；称；称层数相同层数相同的结点的结点在同一层上在同一层上；所有结点的；所有结点的层数中最层数中最大大的称为根树的的称为根树

43、的高高(Height)(Height)。 82-82-3636例例10.3.210.3.2判断下图所示的图是否是根树？若是根树，给出其判断下图所示的图是否是根树？若是根树，给出其根、叶和内点，计算所有结点所在的层数和高。根、叶和内点，计算所有结点所在的层数和高。v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8v v9 9v v1010v v1111v v1212v v1313解解 是一棵根树，其中是一棵根树，其中v v1 1为根，为根，v v5 5,v,v6 6,v,v8 8,v,v9 9,v,v1010,v,v1212,v,v1313为叶，为叶

44、，v v2 2,v,v3 3,v,v4 4,v,v7 7,v,v1111为内点。为内点。v v1 1处 在 第 零 层 ， 层 数 为处 在 第 零 层 ， 层 数 为 0 0 ；v v2 2,v,v3 3,v,v4 4同处在第一层，层数为同处在第一层，层数为1 1；v v5 5,v,v6 6,v,v7 7,v,v8 8,v,v9 9同处在第二层，层同处在第二层，层数为数为2 2；v v1010,v,v1111,v,v1212同处在第三层，同处在第三层，层数为层数为3 3；v v1313处在第四层，层数为处在第四层，层数为4 4；这棵树的高为；这棵树的高为4 4。82-82-3737家族关系家

45、族关系 定义定义10.3.310.3.3 在根树中，若在根树中，若从结点从结点v vi i到到v vj j可达可达，则，则称称v vi i是是v vj j的的祖先祖先(Ancestor)(Ancestor)，v vj j是是v vi i的的后代后代(Descendant)(Descendant)；又若；又若v 是根树中的是根树中的有向边有向边，则称则称v vi i是是v vj j的的父亲父亲(Father)(Father)，v vj j是是v vi i的的儿子儿子(Son)(Son)；如果两个结点是如果两个结点是同一个结点的儿子同一个结点的儿子，则称这两个结，则称这两个结点是点是兄弟兄弟(Br

46、other)(Brother)。定义定义10.3.410.3.4 如果在根树中规定了每一层上结点的如果在根树中规定了每一层上结点的次序次序，这样的根树称为，这样的根树称为有序树有序树(Ordered Tree)(Ordered Tree)。 一般地，在有序树中同一层中结点的次序为一般地，在有序树中同一层中结点的次序为从从左至右左至右。有时也可以用。有时也可以用边的次序边的次序来代替结点的次序。来代替结点的次序。 82-82-3838定义定义10.3.510.3.5在根树在根树T T中，中，n 若每个若每个分支点分支点至多至多有有k k个儿子个儿子，则称，则称T T为为k k元树元树( (k-a

47、ryk-ary Tree) Tree)；n 若每个若每个分支点分支点都都恰有恰有k k个儿子个儿子，则称，则称T T为为k k元完全元完全树树( (k-aryk-ary Complete Tree) Complete Tree)；n 若若k k元树元树T T是是有序有序的，则称的，则称T T为为k k元有序树元有序树( (k-aryk-ary Ordered Tree)Ordered Tree)；n 若若k k元完全树元完全树T T是是有序有序的，则称的，则称T T为为k k元有序完全元有序完全树树( (k-aryk-ary Ordered Complete Tree) Ordered Com

48、plete Tree)。82-82-3939子树子树 在根树在根树T T中，任一中，任一结点结点v v及其所有后代及其所有后代导出的子导出的子图图TT称为称为T T的以的以v v为根的为根的子树子树( (SubtreeSubtree) )。 当然，当然，TT也可以有自己的子树。也可以有自己的子树。 二元有序树的每个结点二元有序树的每个结点v v至多有两个儿子，分至多有两个儿子，分别称为别称为v v的的左儿子左儿子(Left Son)(Left Son)和和右儿子右儿子(Right (Right Son)Son)。 二元有序树的每个结点二元有序树的每个结点v v至多有两棵子树，分至多有两棵子树，

49、分别称为别称为v v的的左子树左子树(Left (Left SubtreeSubtree) )和和右子树右子树(Right (Right SubtreeSubtree) )。 注意区分以注意区分以v v为根的子树和为根的子树和v v的左的左( (右右) )子树，子树，v v为根的子树包含为根的子树包含v v，而，而v v的左的左( (右右) )子树不包子树不包含含v v。 82-82-4040例例10.3.310.3.3判断下图所示的几棵根树是什么树？判断下图所示的几棵根树是什么树？(b)(b)(c)(c)(a)(a)2 2元元完全树完全树 3 3元树元树 3 3元元完全树完全树 3 3元有序

50、元有序完全树完全树1 12 22 2(d)(d)1 13 33 32 21 13 382-82-4141k k元完全树中分支点与叶结点数目之间的关系元完全树中分支点与叶结点数目之间的关系 定理定理10.3.110.3.1 在在k k元完全树中，若叶数为元完全树中，若叶数为t t，分支点，分支点数为数为i i，则下式成立：，则下式成立：(k-1)(k-1)i = t-1i = t-1证明证明 由假设知，该树有由假设知，该树有i+ti+t个结点。由定理个结点。由定理10.2.110.2.1知，该树的边数为知，该树的边数为i+t-1i+t-1。由握手定理知，。由握手定理知，所有结点的出度之和等于边数

51、。而根据所有结点的出度之和等于边数。而根据k k元完全树元完全树的定义知，所有分支点的出度为的定义知，所有分支点的出度为k ki i。因此有。因此有k ki i = i+t-1 = i+t-1即即 (k-1)(k-1)i = t-1i = t-182-82-4242例例10.3.410.3.4假设有一台计算机，它有一条加法指令，可计算假设有一台计算机，它有一条加法指令，可计算3 3个数的和。如果要求个数的和。如果要求9 9个数个数x x1 1, x, x2 2, x, x3 3, x, x4 4, x, x5 5, x, x6 6, , x x7 7, x, x8 8, x, x9 9之和，问

52、至少要执行几次加法指令？之和，问至少要执行几次加法指令？解解 用用3 3个结点表示个结点表示3 3个数，将表示个数，将表示3 3个数之和的结个数之和的结点作为它们的父结点。这样本问题可理解为求一个点作为它们的父结点。这样本问题可理解为求一个三元完全树的分支点问题。把三元完全树的分支点问题。把9 9个数看成叶。由定个数看成叶。由定理理10.910.9知，有知，有(3-1)i = 9-1(3-1)i = 9-1，得，得i = 4i = 4。所以至少。所以至少要执行要执行4 4次加法指令。次加法指令。 (a)(a)x x1 1x x2 2x x3 3x x4 43 3x x5 5x x6 6x x7

53、 7x x8 8x x9 9x x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 7x x9 9(b)(b)82-82-4343一个多种解法的例子一个多种解法的例子 例例10.3.510.3.5 设设T T为任意一棵二元完全树，为任意一棵二元完全树，m m为边数，为边数，t t为叶数，试证明：为叶数，试证明：m = 2tm = 2t2 2。这里。这里t2t2。证明证明 方法一：方法一：设设T T中的结点数为中的结点数为n n，分支点数为，分支点数为i i。根据二元完全树的定义，容易知道下面等式均成立：根据二元完全树的定义，容易知道下面等式均成立：n = n = i+

54、ti+t，m = 2im = 2i，m = n-1m = n-1解关于解关于m, n, im, n, i的三元一次方程组得的三元一次方程组得m = 2t-2m = 2t-2。 82-82-4444方法二：方法二： 在二元完全树中，除树叶外，每个结点的出度在二元完全树中，除树叶外，每个结点的出度均为均为2 2；除根结点外，每个结点的入度均为；除根结点外，每个结点的入度均为1 1。设。设T T中的结点数为中的结点数为n n，由握手定理可知，由握手定理可知2m = = +2m = = + = 2(n-t)+n-1 = 3n-2t-1 = 3(m+1)-2t-1 = 2(n-t)+n-1 = 3n-2

55、t-1 = 3(m+1)-2t-1故故m = 2t-2m = 2t-2。 n ni ii=1i=1deg(v )deg(v )n1ii)v(deg n n+ +i ii=1i=1deg (v )deg (v ) n n- -i ii=1i=1deg (v )deg (v )82-82-4545方法三：方法三： 对树叶数对树叶数t t作归纳法。作归纳法。 当当t = 2t = 2时，结点数为时，结点数为3 3，边数，边数m = 2m = 2，故，故m = m = 2t-22t-2成立。成立。 假设假设t = k(k2)t = k(k2)时，结论成立，下面证明时，结论成立，下面证明t = t =

56、k+1k+1时结论也成立。时结论也成立。 由于由于T T是二元完全树，因此是二元完全树，因此T T中一定存在都是树中一定存在都是树叶的两个兄弟结点叶的两个兄弟结点v v1 1, v, v2 2，设，设v v是是v v1 1, v, v2 2的父亲。在的父亲。在T T中删除中删除v v1 1, v, v2 2，得树，得树TT，TT仍为二元完全树，仍为二元完全树，这时结点这时结点v v成为树叶，树叶数成为树叶，树叶数t= t-2+1 = k+1-1 t= t-2+1 = k+1-1 = k= k，边数，边数m= m-2m= m-2，由归纳假设知，由归纳假设知，m= 2t-2m= 2t-2。所以所以

57、m-2 = 2(t-2+1)-2m-2 = 2(t-2+1)-2，故，故m = 2t-2m = 2t-2。82-82-4646方法四：方法四： 对分支点数对分支点数i i作归纳法。作归纳法。 当当i=1i=1时，边数时，边数m=2m=2，树叶数，树叶数t=2t=2，故，故m=2t-2m=2t-2成立。成立。 假设假设i = k(k1)i = k(k1)时，结论成立，下面证明时，结论成立，下面证明i = i = k+1k+1时结论也成立。时结论也成立。 由于由于T T是二元完全树，因此是二元完全树，因此T T中一定存在两个儿子中一定存在两个儿子都是树叶的分支点，设都是树叶的分支点，设v v就是这

58、样一个分支点，设它的就是这样一个分支点，设它的两个儿子为两个儿子为v v1 1,v,v2 2 。在。在T T中删除中删除v v1 1,v,v2 2，得树，得树TT，TT仍仍为二元完全树，这时结点为二元完全树，这时结点v v成为树叶，分支点数成为树叶，分支点数i=i-i=i-1=k+1-1= k1=k+1-1= k，树叶数，树叶数t= t-2+1t= t-2+1，边数，边数m= m-2m= m-2，由，由归纳假设知，归纳假设知，m= 2t-2m= 2t-2。所以。所以m-2=2(t-2+1)-2m-2=2(t-2+1)-2，故，故m=2t-2m=2t-2。82-82-474710.3.2 10.

59、3.2 根树的遍历根树的遍历 对于根树，一个十分重要的问题是要找到一些对于根树，一个十分重要的问题是要找到一些方法，能系统地方法，能系统地访问树的结点访问树的结点，使得，使得每个结点恰好每个结点恰好访问一次访问一次，这就是根树的，这就是根树的遍历遍历( (ErgodeErgode) )问题问题。 k k元树中，应用最广泛的是元树中，应用最广泛的是二元树二元树。由于二元。由于二元树在计算机中最易处理，下面先介绍二元树的树在计算机中最易处理，下面先介绍二元树的3 3种种常用的常用的遍历方法遍历方法，然后再介绍，然后再介绍将任意根树转化为二将任意根树转化为二元树元树。82-82-4848算法算法10

60、.3.110.3.1二元树的二元树的先根次序遍历先根次序遍历算法：算法：1.1. 访问根；访问根；2.2. 按先根次序遍历根的左子树；按先根次序遍历根的左子树；3.3. 按先根次序遍历根的右子树。按先根次序遍历根的右子树。82-82-4949算法算法10.3.210.3.2二元树的二元树的中根次序遍历中根次序遍历算法：算法：1.1. 按中根次序遍历根的左子树；按中根次序遍历根的左子树；2.2. 访问根；访问根；3.3. 按中根次序遍历根的右子树。按中根次序遍历根的右子树。82-82-5050算法算法10.3.310.3.3二元树的二元树的后根次序遍历后根次序遍历算法：算法：1.1. 按后根次序