離散數(shù)學(xué)第10章樹(shù)

離散數(shù)學(xué)05二月2023電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院2023/2/5第10章樹(shù)

樹(shù)是圖論中的一個(gè)非常重要的概念，而在計(jì)算機(jī)科學(xué)中有著非常廣泛的應(yīng)用，例如現(xiàn)代計(jì)算機(jī)操作系統(tǒng)均采用樹(shù)形結(jié)構(gòu)來(lái)組織文件和文件夾，本章介紹樹(shù)的基本知識(shí)和應(yīng)用。在本章中，所談到的圖都假定是簡(jiǎn)單圖；所談到的回路均指簡(jiǎn)單回路或基本回路。并且同一個(gè)圖形表示的回路(簡(jiǎn)單的或基本的)，可能有不同的交替序列表示方法，但我們規(guī)定它們表示的是同一條回路。2023/2/510.0內(nèi)容提要與樹(shù)相關(guān)的概念：樹(shù)、森林、根樹(shù)、根、葉、分支點(diǎn)、生成樹(shù)、最小生成樹(shù)、k元樹(shù)、k元完全樹(shù)、子樹(shù)、有序樹(shù)、祖先與后代、父親與兒子、最優(yōu)樹(shù)等；樹(shù)的基本性質(zhì)：m=n-1等；樹(shù)的算法：求生成樹(shù)與最小生成樹(shù)的算法、求最優(yōu)樹(shù)的算法、二元樹(shù)遍歷的算法、根樹(shù)與二元樹(shù)相互轉(zhuǎn)化的算法等；樹(shù)的應(yīng)用。2023/2/510.1本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11與樹(shù)相關(guān)基本概念2樹(shù)的性質(zhì)3樹(shù)的基本算法31樹(shù)的同構(gòu)2樹(shù)的應(yīng)用2樹(shù)的算法

2023/2/510.2樹(shù)10.2.1樹(shù)的定義與性質(zhì)例10.2.12006年德國(guó)世界杯8強(qiáng)的比賽結(jié)果圖，最后勝利的隊(duì)捧得大力神杯。德國(guó)阿根廷意大利烏克蘭英格蘭葡萄牙巴西法國(guó)德國(guó)意大利葡萄牙法國(guó)意大利法國(guó)意大利2023/2/5定義10.2.1連通而不含回路的無(wú)向圖稱為無(wú)向樹(shù)(UndirectedTree)，簡(jiǎn)稱樹(shù)(Tree)，常用T表示樹(shù)。樹(shù)中度數(shù)為1的結(jié)點(diǎn)稱為葉(Leaf)；度數(shù)大于1的結(jié)點(diǎn)稱為分支點(diǎn)(BranchPoint)或內(nèi)部結(jié)點(diǎn)(InteriorPoint)。每個(gè)連通分支都是樹(shù)的無(wú)向圖稱為森林(Forest)。平凡圖稱為平凡樹(shù)(TrivialTree)。樹(shù)中沒(méi)有環(huán)和平行邊，因此一定是簡(jiǎn)單圖在任何非平凡樹(shù)中，都無(wú)度數(shù)為0的結(jié)點(diǎn)。2023/2/5例10.2.2判斷下圖中的圖哪些是樹(shù)？為什么？(a)(b)(c)(d)分析判斷無(wú)向圖是否是樹(shù)，根據(jù)定義10.2.1，首先看它是否連通，然后看它是否有回路。解圖(a)、(b)都是連通，并且不含回路，因此是樹(shù)；圖(c)不連通，因此不是樹(shù)，但由于它不含回路，因此是森林；圖(d)雖然連通，但存在回路，因此不是樹(shù)。2023/2/5樹(shù)的性質(zhì)定理10.2.1

設(shè)無(wú)向圖G=<V,E>，|V|=n，|E|=m，下列各命題是等價(jià)的：G連通而不含回路(即G是樹(shù))；G中無(wú)回路，且m=n-1；G是連通的，且m=n-1；G中無(wú)回路，但在G中任二結(jié)點(diǎn)之間增加一條新邊，就得到惟一的一條基本回路；G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G中每一對(duì)結(jié)點(diǎn)之間有惟一一條基本通路。(n≥2)2023/2/5分析直接證明這6個(gè)命題兩兩等價(jià)工作量太大，一般采用循環(huán)論證的方法，即證明(1)(2)(3)(4)(5)(6)(1)然后利用傳遞性，得到結(jié)論。2023/2/5證明(1)(2)：對(duì)n作歸納。n=1時(shí)，m=0，顯然有m=n-1。假設(shè)n=k時(shí)命題成立，現(xiàn)證n=k+1時(shí)也成立。由于G連通而無(wú)回路，所以G中至少有一個(gè)度數(shù)為1的結(jié)點(diǎn)v0，在G中刪去v0及其關(guān)聯(lián)的邊，便得到k個(gè)結(jié)點(diǎn)的連通而無(wú)回路的圖，由歸納假設(shè)知它有k-1條邊。再將結(jié)點(diǎn)v0及其關(guān)聯(lián)的邊加回得到原圖G，所以G中含有k+1個(gè)結(jié)點(diǎn)和k條邊，符合公式m=n-1。所以，G中無(wú)回路，且m=n-1。G連通而不含回路(即G是樹(shù))G中無(wú)回路，且m=n-1；2023/2/5(2)(3)：證明只有一個(gè)連通分支。設(shè)G有k個(gè)連通分支G1，G2，…，Gk，其結(jié)點(diǎn)數(shù)分別為n1，n2，…，nk，邊數(shù)分別為m1，m2，…，mk，且，。由于G中無(wú)回路，所以每個(gè)Gi(i=1,2,…,k)均為樹(shù)，因此mi=ni-1(i=1,2,…,k)，于是故k=1，所以G是連通的，且m=n-1。G中無(wú)回路，且m=n-1；G是連通的，且m=n-1；2023/2/5(3)(4)：首先證明G中無(wú)回路。對(duì)n作歸納。n=1時(shí)，m=n-1=0，顯然無(wú)回路。假設(shè)結(jié)點(diǎn)數(shù)n=k-1時(shí)無(wú)回路，下面考慮結(jié)點(diǎn)數(shù)n=k的情況。因G連通，故G中每一個(gè)結(jié)點(diǎn)的度數(shù)均大于等于1。可以證明至少有一個(gè)結(jié)點(diǎn)v0，使得deg(v0)=1，因若k個(gè)結(jié)點(diǎn)的度數(shù)都大于等于2，則，從而m≥k，即至少有k條邊，但這與m=n-1矛盾。G是連通的，且m=n-1；G中無(wú)回路，但在G中任二結(jié)點(diǎn)之間增加一條新邊，就得到惟一的一條基本回路；2023/2/5在G中刪去v0及其關(guān)聯(lián)的邊，得到新圖G’，根據(jù)歸納假設(shè)知G’無(wú)回路，由于deg(v0)=1，所以再將結(jié)點(diǎn)v0及其關(guān)聯(lián)的邊加回得到原圖G，則G也無(wú)回路。其次證明在G中任二結(jié)點(diǎn)vi，vj之間增加一條邊(vi,vj)，得到一條且僅一條基本回路。由于G是連通的，從vi到vj有一條通路L，再在L中增加一條邊(vi,vj)，就構(gòu)成一條回路。若此回路不是惟一和基本的，則刪去此新邊，G中必有回路，得出矛盾。2023/2/5(4)(5)：若G不連通，則存在兩結(jié)點(diǎn)vi和vj，在vi和vj之間無(wú)通路，此時(shí)增加邊(vi,vj)，不會(huì)產(chǎn)生回路，但這與題設(shè)矛盾。由于G無(wú)回路，所以刪去任一邊，圖便不連通。G中無(wú)回路，但在G中任二結(jié)點(diǎn)之間增加一條新邊，就得到惟一的一條基本回路；G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)2023/2/5G是連通的，但刪除G中任一條邊后，便不連通；(n≥2)G中每一對(duì)結(jié)點(diǎn)之間有惟一一條基本通路。(n≥2)(5)(6)：由于G是連通的，因此G中任二結(jié)點(diǎn)之間都有通路，于是有一條基本通路。若此基本通路不惟一，則G中含有回路，刪去回路上的一條邊，G仍連通，這與題設(shè)不符。所以此基本通路是惟一的。2023/2/5(6)(1)：顯然G是連通的。若G中含回路，則回路上任二結(jié)點(diǎn)之間有兩條基本通路，這與題設(shè)矛盾。因此，G連通且不含回路。G中每一對(duì)結(jié)點(diǎn)之間有惟一一條基本通路。(n≥2)G連通而不含回路(即G是樹(shù))；2023/2/5樹(shù)的特點(diǎn)在結(jié)點(diǎn)給定的無(wú)向圖中，樹(shù)是邊數(shù)最多的無(wú)回路圖樹(shù)是邊數(shù)最少的連通圖由此可知，在無(wú)向圖G=(n,m)中，若m＜n-1，則G是不連通的若m＞n-1，則G必含回路由定理10.2.1(4)由定理10.2.1(5)2023/2/5定理10.2.2任意非平凡樹(shù)T=(n,m)都至少有兩片葉。分析利用握手定理和m=n-1即可。證明因非平凡樹(shù)T是連通的，從而T中各結(jié)點(diǎn)的度數(shù)均大于等于1。設(shè)T中有k個(gè)度數(shù)為1的結(jié)點(diǎn)(即k片葉)，其余的結(jié)點(diǎn)度數(shù)均大于等于2。由于樹(shù)中有m=n-1，于是2(n-1)≥2n-k，因此可得k≥2，這說(shuō)明T中至少有兩片葉。于是由握手定理2023/2/510.2.2生成樹(shù)定義10.2.2

給定圖G=<V,E>，若G的某個(gè)生成子圖是樹(shù)，則稱之為G的生成樹(shù)(SpanningTree)，記為T(mén)G。生成樹(shù)TG中的邊稱為樹(shù)枝(Branch)；G中不在TG中的邊稱為弦(Chord)；TG的所有弦的集合稱為生成樹(shù)的補(bǔ)(Complement)。2023/2/5例10.2.3判斷下圖中的圖(b)、(c)、(d)、(e)是否是圖(a)的生成樹(shù)。abcdef(a)abcdef(b)abcdef(c)abcdef(d)bcdef(e)分析判斷是否是生成樹(shù)，根據(jù)定義10.2.2，首先看它是否是樹(shù)，然后再看它是否是生成子圖。由于圖(b)和(d)不是樹(shù)，圖(e)不是生成子圖，因此它們都不是圖(a)的生成樹(shù)，而圖(c)既是樹(shù)，又是生成子圖，因此是生成樹(shù)。解圖(b)、(d)和(e)不是圖(a)的生成樹(shù)，圖(c)是圖(a)的生成樹(shù)，其中邊(a,c)、(a,d)、(b,f)、(c,f)、(c,e)是樹(shù)枝，而(a,b)、(b,c)、(c,d)、(d,e)、(e,f)是弦。2023/2/5定理10.2.3一個(gè)圖G=<V,E>存在生成樹(shù)TG=<V,ET>的充分必要條件是G是連通的。分析必要性由樹(shù)的定義即得，充分性利用構(gòu)造性方法，具體找出一顆生成樹(shù)即可證明必要性：假設(shè)TG=<V,ET>是G=<V,E>的生成樹(shù)，由定義10.2.1，TG是連通的，于是G也是連通的。充分性：假設(shè)G=<V,E>是連通的。如果G中無(wú)回路，G本身就是生成樹(shù)。如果G中存在回路C1，可刪除C1中一條邊得到圖G1，它仍連通且與G有相同的結(jié)點(diǎn)集。如果G1中無(wú)回路，G1就是生成樹(shù)。如果G1仍存在回路C2，可刪除C2中一條邊，如此繼續(xù)，直到得到一個(gè)無(wú)回路的連通圖H為止。因此，H是G的生成樹(shù)。2023/2/5破圈法與避圈法算法10.2.1

求連通圖G=<V,E>的生成樹(shù)的破圈法： 每次刪除回路中的一條邊，其刪除的邊的總數(shù)為m-n+1。算法10.2.2

求連通圖G=<V,E>的生成樹(shù)的避圈法： 每次選取G中一條與已選取的邊不構(gòu)成回路的邊，選取的邊的總數(shù)為n-1。由于刪除回路上的邊和選擇不構(gòu)成任何回路的邊有多種選法，所以產(chǎn)生的生成樹(shù)不是惟一的。2023/2/5例10.2.4分別用破圈法和避圈法求下圖的生成樹(shù)。123456分析分別用破圈法和避圈法依次進(jìn)行即可。用破圈法時(shí)，由于n=6，m=9，所以m-n+1=4，故要?jiǎng)h除的邊數(shù)為4，因此只需4步即可。用避圈法時(shí)，由于n=6，所以n-1=5，故要選取5條邊，因此需5步即可。破圈法2023/2/5避圈法由于生成樹(shù)的形式不惟一，故上述兩棵生成樹(shù)都是所求的。破圈法和避圈法的計(jì)算量較大，主要是需要找出回路或驗(yàn)證不存在回路。1234561234562023/2/5算法10.2.3求連通圖G=<V,E>的生成樹(shù)的廣度優(yōu)先搜索算法：（1）任選s∈V，將s標(biāo)記為0，令L={s}，V=V-{s}，k=0；（2）如果V=Φ，則轉(zhuǎn)(4)，否則令k=k+1；（3）依次對(duì)L中所有標(biāo)記為k-1的結(jié)點(diǎn)v，如果它與V中的結(jié)點(diǎn)w相鄰接，則將w標(biāo)記為k，指定v為w的前驅(qū)，令L=L∪{w}，V=V-{w}，轉(zhuǎn)(2)；（4）EG={(v,w)|w∈L-{s}，v為w的前驅(qū)}，結(jié)束。2023/2/5例10.2.5利用廣度優(yōu)先搜索算法求下圖的生成樹(shù)。0(-)1(a)1(a)2(c)2(b)3(e)3(e)3(e)4(d)4(h)bacdgjifeh0(-)1(a)1(a)2(c)2(b)3(e)3(f)3(e)4(h)4(h)bacdgjifeh2023/2/510.2.3最小生成樹(shù)定義10.2.3

設(shè)G=<V,E>是連通的賦權(quán)圖，T是G的一棵生成樹(shù)，T的每個(gè)樹(shù)枝所賦權(quán)值之和稱為T(mén)的權(quán)(Weight)，記為w(T)。G中具有最小權(quán)的生成樹(shù)稱為G的最小生成樹(shù)(MinimalSpanningTree)。

一個(gè)無(wú)向圖的生成樹(shù)不是惟一的，同樣地，一個(gè)賦權(quán)圖的最小生成樹(shù)也不一定是惟一的。2023/2/5算法10.2.3Kruskal算法（1）在G中選取最小權(quán)邊e1，置i=1。（2）當(dāng)i=n-1時(shí)，結(jié)束，否則轉(zhuǎn)(3)。（3）設(shè)已選取的邊為e1,e2,…,ei，在G中選取不同于e1,e2,…,ei的邊ei+1，使{e1,e2,…,ei,ei+1}中無(wú)回路且ei+1是滿足此條件的最小權(quán)邊。（4）置i=i+1，轉(zhuǎn)(2)。要點(diǎn)：在與已選取的邊不構(gòu)成回路的邊中選取最小者。

在Kruskal算法的步驟1和3中，若滿足條件的最小權(quán)邊不止一條，則可從中任選一條，這樣就會(huì)產(chǎn)生不同的最小生成樹(shù)。2023/2/5例10.2.6用Kruskal算法求圖中賦權(quán)圖的最小生成樹(shù)。4655761f923adbcimjkehg343446587582345k1fech34a3i5dm2g2bj4解n=12，按算法要執(zhí)行n-1=11次，w(T)=36。2023/2/5算法10.2.5Prim算法（1）在G中任意選取一個(gè)結(jié)點(diǎn)v1，置VT={v1},ET=Φ，k=1；（2）在V-VT中選取與某個(gè)vi∈VT鄰接的結(jié)點(diǎn)vj，使得邊(vi,vj)的權(quán)最小，置VT=VT∪{vj},ET=ET∪{(vi,vj)}，k=k+1；（3）重復(fù)步驟2，直到k=|V|。要點(diǎn)：從任意結(jié)點(diǎn)開(kāi)始，每次增加一條最小權(quán)邊構(gòu)成一棵新樹(shù)。

在Prim算法的步驟2中，若滿足條件的最小權(quán)邊不止一條，則可從中任選一條，這樣就會(huì)產(chǎn)生不同的最小生成樹(shù)。

2023/2/5例10.2.7用Prim算法求圖中賦權(quán)圖的最小生成樹(shù)。5f102dbce7g64582a7ge2f5b42cad5解n=7，按算法要執(zhí)行n-1=6次，w(T)=25。由Prim算法可以看出，每一步得到的圖一定是樹(shù)，故不需要驗(yàn)證是否有回路，因此它的計(jì)算工作量較Kruskal算法要小。

2023/2/510.2.4無(wú)向樹(shù)的難點(diǎn)樹(shù)是不含回路的連通圖。注意把握樹(shù)的性質(zhì)，特別是樹(shù)中葉結(jié)點(diǎn)的數(shù)目及邊數(shù)與結(jié)點(diǎn)數(shù)的關(guān)系：m=n-1；生成樹(shù)是無(wú)向連通圖是樹(shù)的生成子圖。注意把握所有連通圖都有生成樹(shù)，知道生成樹(shù)的樹(shù)枝與弦及其數(shù)目，會(huì)使用避圈法、破圈法和廣度優(yōu)先搜索算法求生成樹(shù)；最小生成樹(shù)是賦權(quán)連通圖的權(quán)值之和最小的生成樹(shù)。會(huì)使用Kruskal算法和Prim算法求最小生成樹(shù)。2023/2/510.2.5無(wú)向樹(shù)的應(yīng)用

例10.2.8

假設(shè)有5個(gè)信息中心A、B、C、D、E，它們之間的距離(以百公里為單位)如圖所示。要交換數(shù)據(jù)，我們可以在任意兩個(gè)信息中心之間通過(guò)光纖連接，但是費(fèi)用的限制要求鋪設(shè)盡可能少的光纖線路。重要的是每個(gè)信息中心能和其它中心通信，但并不需要在任意兩個(gè)中心之間都鋪設(shè)線路，可以通過(guò)其它中心轉(zhuǎn)發(fā)。ABCDE3547962879ABCDE3462分析這實(shí)際上就是求賦權(quán)連通圖的最小生成樹(shù)問(wèn)題，可用Prim算法或Kruskal算法求解。解求得圖的最小生成樹(shù)如圖所示，w(T)=15百公里。即按圖的圖鋪設(shè)，使得鋪設(shè)的線路最短。2023/2/510.3根樹(shù)10.3.1根樹(shù)的定義與分類(lèi)定義10.3.1

一個(gè)有向圖，若略去所有有向邊的方向所得到的無(wú)向圖是一棵樹(shù)，則這個(gè)有向圖稱為有向樹(shù)(DirectedTree)。2023/2/5例10.3.1判斷下圖中的圖哪些是樹(shù)？為什么？(a)(c)(e)(d)(b)2023/2/5定義10.3.2一棵非平凡的有向樹(shù)，如果恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度均為1，則稱之為根樹(shù)(RootTree)或外向樹(shù)(OutwardTree)。入度為0的結(jié)點(diǎn)稱為根(Root)；出度為0的結(jié)點(diǎn)稱為葉(Leaf)；入度為1，出度大于0的結(jié)點(diǎn)稱為內(nèi)點(diǎn)(InteriorPoint)；又將內(nèi)點(diǎn)和根統(tǒng)稱為分支點(diǎn)(BranchPoint)。在根樹(shù)中，從根到任一結(jié)點(diǎn)v的通路長(zhǎng)度，稱為該結(jié)點(diǎn)的層數(shù)(LayerNumber)；稱層數(shù)相同的結(jié)點(diǎn)在同一層上；所有結(jié)點(diǎn)的層數(shù)中最大的稱為根樹(shù)的高(Height)。2023/2/5例10.3.2判斷下圖所示的圖是否是根樹(shù)？若是根樹(shù)，給出其根、葉和內(nèi)點(diǎn)，計(jì)算所有結(jié)點(diǎn)所在的層數(shù)和高。v1v2v3v4v5v6v7v8v9v10v11v12v13v1v2v3v4v5v6v7v8v9v10v11v12v13解是一棵根樹(shù)，其中v1為根，v5,v6,v8,v9,v10,v12,v13為葉，v2,v3,v4,v7,v11為內(nèi)點(diǎn)。v1處在第零層，層數(shù)為0；v2,v3,v4同處在第一層，層數(shù)為1；v5,v6,v7,v8,v9同處在第二層，層數(shù)為2；v10,v11,v12同處在第三層，層數(shù)為3；v13處在第四層，層數(shù)為4；這棵樹(shù)的高為4。倒置法

2023/2/5家族關(guān)系定義10.3.3

在根樹(shù)中，若從結(jié)點(diǎn)vi到vj可達(dá)，則稱vi是vj的祖先(Ancestor)，vj是vi的后代(Descendant)；又若<vi,vj>是根樹(shù)中的有向邊，則稱vi是vj的父親(Father)，vj是vi的兒子(Son)；如果兩個(gè)結(jié)點(diǎn)是同一個(gè)結(jié)點(diǎn)的兒子，則稱這兩個(gè)結(jié)點(diǎn)是兄弟(Brother)。定義10.3.4

如果在根樹(shù)中規(guī)定了每一層上結(jié)點(diǎn)的次序，這樣的根樹(shù)稱為有序樹(shù)(OrderedTree)。一般地，在有序樹(shù)中同一層中結(jié)點(diǎn)的次序?yàn)閺淖笾劣?。有時(shí)也可以用邊的次序來(lái)代替結(jié)點(diǎn)的次序。2023/2/5定義10.3.5(J0430)在根樹(shù)T中，若每個(gè)分支點(diǎn)至多有k個(gè)兒子，則稱T為k元樹(shù)(k-aryTree)；若每個(gè)分支點(diǎn)都恰有k個(gè)兒子，則稱T為k元完全樹(shù)(k-aryCompleteTree)；若k元樹(shù)T是有序的，則稱T為k元有序樹(shù)(k-aryOrderedTree)；若k元完全樹(shù)T是有序的，則稱T為k元有序完全樹(shù)(k-aryOrderedCompleteTree)。2023/2/5子樹(shù)在根樹(shù)T中，任一結(jié)點(diǎn)v及其所有后代導(dǎo)出的子圖T’稱為T(mén)的以v為根的子樹(shù)(Subtree)。當(dāng)然，T’也可以有自己的子樹(shù)。二元有序樹(shù)的每個(gè)結(jié)點(diǎn)v至多有兩個(gè)兒子，分別稱為v的左兒子(LeftSon)和右兒子(RightSon)。二元有序樹(shù)的每個(gè)結(jié)點(diǎn)v至多有兩棵子樹(shù)，分別稱為v的左子樹(shù)(LeftSubtree)和右子樹(shù)(RightSubtree)。注意區(qū)分以v為根的子樹(shù)和v的左(右)子樹(shù)，v為根的子樹(shù)包含v，而v的左(右)子樹(shù)不包含v。

2023/2/5例10.3.3判斷下圖所示的幾棵根樹(shù)是什么樹(shù)？(b)(c)(a)2元完全樹(shù)

3元樹(shù)

3元完全樹(shù)

3元有序完全樹(shù)122(d)1332132023/2/5k元完全樹(shù)中分支點(diǎn)與葉結(jié)點(diǎn)數(shù)目之間的關(guān)系定理10.3.1

在k元完全樹(shù)中，若葉數(shù)為t，分支點(diǎn)數(shù)為i，則下式成立：(k-1)×i=t-1證明由假設(shè)知，該樹(shù)有i+t個(gè)結(jié)點(diǎn)。由定理10.2.1知，該樹(shù)的邊數(shù)為i+t-1。由握手定理知，所有結(jié)點(diǎn)的出度之和等于邊數(shù)。而根據(jù)k元完全樹(shù)的定義知，所有分支點(diǎn)的出度為k×i。因此有k×i=i+t-1即 (k-1)×i=t-12023/2/5例10.3.4假設(shè)有一臺(tái)計(jì)算機(jī)，它有一條加法指令，可計(jì)算3個(gè)數(shù)的和。如果要求9個(gè)數(shù)x1,x2,x3,x4,x5,x6,x7,x8,x9之和，問(wèn)至少要執(zhí)行幾次加法指令？解用3個(gè)結(jié)點(diǎn)表示3個(gè)數(shù)，將表示3個(gè)數(shù)之和的結(jié)點(diǎn)作為它們的父結(jié)點(diǎn)。這樣本問(wèn)題可理解為求一個(gè)三元完全樹(shù)的分支點(diǎn)問(wèn)題。把9個(gè)數(shù)看成葉。由定理10.9知，有(3-1)i=9-1，得i=4。所以至少要執(zhí)行4次加法指令。(a)x1x2x3x43x5x6x7x8x9x1x2x3x4x5x6x7x9(b)2023/2/5一個(gè)多種解法的例子例10.3.5

設(shè)T為任意一棵二元完全樹(shù)，m為邊數(shù)，t為葉數(shù)，試證明：m=2t-2。這里t≥2。證明

方法一：設(shè)T中的結(jié)點(diǎn)數(shù)為n，分支點(diǎn)數(shù)為i。根據(jù)二元完全樹(shù)的定義，容易知道下面等式均成立：n=i+t，m=2i，m=n-1解關(guān)于m,n,i的三元一次方程組得m=2t-2。2023/2/5方法二：在二元完全樹(shù)中，除樹(shù)葉外，每個(gè)結(jié)點(diǎn)的出度均為2；除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的入度均為1。設(shè)T中的結(jié)點(diǎn)數(shù)為n，由握手定理可知2m==+=2(n-t)+n-1=3n-2t-1=3(m+1)-2t-1故m=2t-2。2023/2/5方法三：對(duì)樹(shù)葉數(shù)t作歸納法。當(dāng)t=2時(shí)，結(jié)點(diǎn)數(shù)為3，邊數(shù)m=2，故m=2t-2成立。假設(shè)t=k(k≥2)時(shí)，結(jié)論成立，下面證明t=k+1時(shí)結(jié)論也成立。由于T是二元完全樹(shù)，因此T中一定存在都是樹(shù)葉的兩個(gè)兄弟結(jié)點(diǎn)v1,