離散數(shù)學(xué)1第10電子科技課程組

1、離 散 數(shù) 學(xué)電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院示 范 性 軟 件 學(xué) 院13 九月 20222022/9/13第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ī)定它們表示的是同一條回路。2022/9/1310.0 內(nèi)容提要 與樹(shù)相關(guān)的概念： 樹(shù)、森林、根樹(shù)、根、葉、分支點(diǎn)、生成樹(shù)、最小生成樹(shù)、k元樹(shù)、k元完全樹(shù)子樹(shù)、有序樹(shù)、祖

2、先與后代、父親與兒子、最優(yōu)樹(shù)等；樹(shù)的基本性質(zhì)：m = n-1等；樹(shù)的算法：求生成樹(shù)與最小生成樹(shù)的算法、求最優(yōu)樹(shù)的算法、二元樹(shù)遍歷的算法、根樹(shù)與二元樹(shù)相互轉(zhuǎn)化的算法等；樹(shù)的應(yīng)用。2022/9/1310.1 本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11 與樹(shù)相關(guān)基本概念2 樹(shù)的性質(zhì)3 樹(shù)的基本算法 31 樹(shù)的同構(gòu)2 樹(shù)的應(yīng)用2樹(shù)的算法 2022/9/1310.2 樹(shù) 10.2.1 樹(shù)的定義與性質(zhì)例10.2.1 2006年德國(guó)世界杯8強(qiáng)的比賽結(jié)果圖，最后勝利的隊(duì)捧得大力神杯。德 國(guó)阿根廷意大利烏克蘭英格蘭葡萄牙巴 西法 國(guó)德 國(guó)意大利葡萄牙法 國(guó)意大利法 國(guó)意大利2022/9/13定義10.2.1連通而不含

3、回路的無(wú)向圖稱(chēng)為無(wú)向樹(shù)(Undirected Tree)，簡(jiǎn)稱(chēng)樹(shù)(Tree)，常用T表示樹(shù)。樹(shù)中度數(shù)為1的結(jié)點(diǎn)稱(chēng)為葉(Leaf)；度數(shù)大于1的結(jié)點(diǎn)稱(chēng)為分支點(diǎn)(Branch Point)或內(nèi)部結(jié)點(diǎn)(Interior Point)。每個(gè)連通分支都是樹(shù)的無(wú)向圖稱(chēng)為森林(Forest)。平凡圖稱(chēng)為平凡樹(shù)(Trivial Tree)。樹(shù)中沒(méi)有環(huán)和平行邊，因此一定是簡(jiǎn)單圖在任何非平凡樹(shù)中，都無(wú)度數(shù)為0的結(jié)點(diǎn)。2022/9/13例10.2.2判斷下圖中的圖哪些是樹(shù)？為什么？ (a)(b)(c)(d)分析 判斷無(wú)向圖是否是樹(shù)，根據(jù)定義10.2.1，首先看它是否連通，然后看它是否有回路。2022/9/13樹(shù)的性

4、質(zhì) 定理10.2.1 設(shè)無(wú)向圖G = ，|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中任一條邊后，便不連通；(n2)G中每一對(duì)結(jié)點(diǎn)之間有惟一一條基本通路。(n2)2022/9/13定理10.2.1 分析 直接證明這6個(gè)命題兩兩等價(jià)工作量太大，一般采用循環(huán)論證的方法，即證明(1) (2) (3) (4) (5) (6) (1)然后利用傳遞行，得到結(jié)論。2022/9/13定理10.2.1 證明 (1) (2)：

5、 對(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；2022/9/13(2) (3)： 證明只有一個(gè)連通分支。 設(shè)G有k個(gè)連通分支G1，G2，Gk，其結(jié)點(diǎn)數(shù)分別為n1，n2，nk，邊數(shù)

6、分別為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；2022/9/13(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，則 ，

7、從而mk，即至少有k條邊，但這與m = n-1矛盾。 G是連通的，且m = n-1；G中無(wú)回路，但在G中任二結(jié)點(diǎn)之間增加一條新邊，就得到惟一的一條基本回路；2022/9/13(3) (4)(續(xù))： 在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中必有回路，得出矛盾。

8、2022/9/13(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中任一條邊后，便不連通；(n2)2022/9/13G是連通的，但刪除G中任一條邊后，便不連通；(n2)G中每一對(duì)結(jié)點(diǎn)之間有惟一一條基本通路。(n2)(5) (6)： 由于G是連通的，因此G中任二結(jié)點(diǎn)之間都有通路，于是有一條基本通路。若此基本通路不惟一，則G中含有回路，刪去回路上的一條邊，G仍連通，這與題設(shè)不

9、符。 所以此基本通路是惟一的。2022/9/13(6) (1)： 顯然G是連通的。若G中含回路，則回路上任二結(jié)點(diǎn)之間有兩條基本通路，這與題設(shè)矛盾。 因此，G連通且不含回路。G中每一對(duì)結(jié)點(diǎn)之間有惟一一條基本通路。(n2)G連通而不含回路(即G是樹(shù))；2022/9/13樹(shù)的特點(diǎn)在結(jié)點(diǎn)給定的無(wú)向圖中， 樹(shù)是邊數(shù)最多的無(wú)回路圖 樹(shù)是邊數(shù)最少的連通圖由此可知，在無(wú)向圖G = (n, m)中， 若mn-1，則G是不連通的 若mn-1，則G必含回路由定理10.2.1(4)由定理10.2.1(5)2022/9/13定理10.2.2任意非平凡樹(shù)T = (n, m) 都至少有兩片葉。分析 利用握手定理和m = n

10、-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，因此可得k2，這說(shuō)明T中至少有兩片葉。于是由握手定理2022/9/1310.2.2 生成樹(shù) 定義10.2.2 給定圖G = ，若G的某個(gè)生成子圖是樹(shù)，則稱(chēng)之為G的生成樹(shù)(Spanning Tree)，記為T(mén)G。生成樹(shù)TG中的邊稱(chēng)為樹(shù)枝(Branch)；G中不在TG中的邊稱(chēng)為弦(Chord)；TG的所有弦的集合稱(chēng)為生成樹(shù)的補(bǔ)(Complement)。 2022/9/13例10.2.3判斷下圖中的圖(b)、(c)

11、、(d)、(e)是否是圖(a)的生成樹(shù)。abcdef(a)abcdef(b)abcdef(c)abcdef(d)bcdef(e)解 圖(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)是弦。2022/9/13定理10.2.3一個(gè)圖G = 存在生成樹(shù)TG = 的充分必要條件是G是連通的。分析 必要性由樹(shù)的定義即得，充分性利用構(gòu)造性方法，具體找出一顆生成樹(shù)即可證明 必要性：假設(shè)TG = 是G = 的生成樹(shù)，由定義10.2.1，

12、TG是連通的，于是G也是連通的。2022/9/13定理10.2.3一個(gè)圖G = 存在生成樹(shù)TG = 的充分必要條件是G是連通的。證明 充分性：假設(shè)G = 是連通的。 如果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ù)。2022/9/13破圈法與避圈法算法10.2.1 求連通圖G = 的生成樹(shù)的破圈法：每次刪除回路中的一條邊，其刪除的邊的總數(shù)為m-n+1。算法10.2.2 求連通圖G

13、= 的生成樹(shù)的避圈法：每次選取G中一條與已選取的邊不構(gòu)成回路的邊，選取的邊的總數(shù)為n-1。由于刪除回路上的邊和選擇不構(gòu)成任何回路的邊有多種選法，所以產(chǎn)生的生成樹(shù)不是惟一的。 2022/9/13例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步即可。 破圈法2022/9/13避圈法由于生成樹(shù)的形式不惟一，故上述兩棵生成樹(shù)都是所求的。 破圈法和避圈法的計(jì)算量較大，主要是需

14、要找出回路或驗(yàn)證不存在回路。 1234561234562022/9/13算法10.2.3求連通圖G = 的生成樹(shù)的廣度優(yōu)先搜索算法：（1）任選sV，將v標(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 = Lw，V = V-w，轉(zhuǎn)(2)；（4）EG = (v, w)|wL-s，v為w的前驅(qū)，結(jié)束。2022/9/13例10.2.5利用廣度優(yōu)先搜索算法求下圖的生成樹(shù)。 0(-)1(a)1(a)2(c)2(b)3(e)3(e)3(e)4

15、(d)4(h)bacdgjifeh0(-)1(a)1(a)2(c)2(b)3(e)3(f)3(e)4(h)4(h)bacdgjifeh2022/9/1310.2.3 最小生成樹(shù) 定義10.2.3 設(shè)G = 是連通的賦權(quán)圖，T是G的一棵生成樹(shù)，T的每個(gè)樹(shù)枝所賦權(quán)值之和稱(chēng)為T(mén)的權(quán)(Weight)，記為w(T)。 G中具有最小權(quán)的生成樹(shù)稱(chēng)為G的最小生成樹(shù)(Minimal Spanning Tree)。 一個(gè)無(wú)向圖的生成樹(shù)不是惟一的，同樣地，一個(gè)賦權(quán)圖的最小生成樹(shù)也不一定是惟一的。2022/9/13算法10.2.3 Kruskal算法 （1）在G中選取最小權(quán)邊e1，置i = 1。（2）當(dāng)i = n-1

16、時(shí)，結(jié)束，否則轉(zhuǎn)(3)。（3）設(shè)已選取的邊為e1, e2, , ei，在G中選取不同于e1, e2, , ei的邊ei+1，使e1, e2, , ei, ei+1中無(wú)回路且ei+1是滿(mǎn)足此條件的最小權(quán)邊。（4）置i = i+1，轉(zhuǎn)(2)。要點(diǎn)：在與已選取的邊不構(gòu)成回路的邊中選取最小者。 步驟1和3中，若滿(mǎn)足條件的最小權(quán)邊不止一條，則可從中任選一條2022/9/13例10.2.6用Kruskal算法求圖中賦權(quán)圖的最小生成樹(shù)。4655761f923adbcimjkehg343446587582345k1fech34a3i5dm2g2bj4解 n=12，按算法要執(zhí)行n-1=11次，w(T) = 36

17、。 2022/9/13算法10.2.5 Prim算法 （1）在G中任意選取一個(gè)結(jié)點(diǎn)v1，置VT = v1, ET = ，k = 1；（2）在V-VT中選取與某個(gè)viVT鄰接的結(jié)點(diǎn)vj，使得邊(vi, vj)的權(quán)最小，置VT = VTvj, ET = ET(vi, vj)，k = k+1；（3）重復(fù)步驟2，直到k = |V|。要點(diǎn)：從任意結(jié)點(diǎn)開(kāi)始，每次增加一條最小權(quán)邊構(gòu)成一棵新樹(shù)。 步驟2中，若滿(mǎn)足條件的最小權(quán)邊不止一條，則可從中任選一條2022/9/13例10.2.7用Prim算法求圖中賦權(quán)圖的最小生成樹(shù)。 5f102dbce7g64582a7ge2f5b42cad5解 n = 7，按算法要執(zhí)

18、行n-1 = 6次，w(T) = 25。 2022/9/1310.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ù)。 2022/9/1310.2.5 無(wú)向樹(shù)的應(yīng)用 例10.2.8 假設(shè)有5個(gè)信息中心A、B、C、D、E，它們之間的距離(以百公里為單位)如圖所示。要交換數(shù)據(jù)，我們可以在任意兩

19、個(gè)信息中心之間通過(guò)光纖連接，但是費(fèi)用的限制要求鋪設(shè)盡可能少的光纖線(xiàn)路。重要的是每個(gè)信息中心能和其它中心通信，但并不需要在任意兩個(gè)中心之間都鋪設(shè)線(xiàn)路，可以通過(guò)其它中心轉(zhuǎn)發(fā)。 分析 這實(shí)際上就是求賦權(quán)連通圖的最小生成樹(shù)問(wèn)題，可用Prim算法或Kruskal算法求解。ABCDE35479628792022/9/1310.2.5 無(wú)向樹(shù)的應(yīng)用 ABCDE3547962879ABCDE3462解 求得圖的最小生成樹(shù)如圖所示，w(T) = 15百公里。即按圖的圖鋪設(shè)，使得鋪設(shè)的線(xiàn)路最短。 2022/9/1310.3 根樹(shù) 10.3.1 根樹(shù)的定義與分類(lèi) 定義10.3.1 一個(gè)有向圖，若略去所有有向邊的方向

20、所得到的無(wú)向圖是一棵樹(shù)，則這個(gè)有向圖稱(chēng)為有向樹(shù)(Directed Tree)。 2022/9/13例10.3.1判斷下圖中的圖哪些是樹(shù)？為什么？(a)(c)(e)(d)(b)2022/9/13定義10.3.2 一棵非平凡的有向樹(shù)，如果恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度均為1，則稱(chēng)之為根樹(shù)(Root Tree)或外向樹(shù)(Outward Tree)。 入度為0的結(jié)點(diǎn)稱(chēng)為根(Root)；出度為0的結(jié)點(diǎn)稱(chēng)為葉(Leaf)； 入度為1，出度大于0的結(jié)點(diǎn)稱(chēng)為內(nèi)點(diǎn)(Interior Point)；又將內(nèi)點(diǎn)和根統(tǒng)稱(chēng)為分支點(diǎn)(Branch Point)。 在根樹(shù)中，從根到任一結(jié)點(diǎn)v的通路長(zhǎng)度，稱(chēng)為該結(jié)點(diǎn)

21、的層數(shù)(Layer Number)；稱(chēng)層數(shù)相同的結(jié)點(diǎn)在同一層上；所有結(jié)點(diǎn)的層數(shù)中最大的稱(chēng)為根樹(shù)的高(Height)。 2022/9/13例10.3.2判斷下圖所示的圖是否是根樹(shù)？若是根樹(shù)，給出其根、葉和內(nèi)點(diǎn)，計(jì)算所有結(jié)點(diǎn)所在的層數(shù)和高。v1v2v3v4v5v6v7v8v9v10v11v12v13解 是一棵根樹(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處在第四層，層

22、數(shù)為4；這棵樹(shù)的高為4。2022/9/13家族關(guān)系 定義10.3.3 在根樹(shù)中，若從結(jié)點(diǎn)vi到vj可達(dá)，則稱(chēng)vi是vj的祖先(Ancestor)，vj是vi的后代(Descendant)；又若是根樹(shù)中的有向邊，則稱(chēng)vi是vj的父親(Father)，vj是vi的兒子(Son)；如果兩個(gè)結(jié)點(diǎn)是同一個(gè)結(jié)點(diǎn)的兒子，則稱(chēng)這兩個(gè)結(jié)點(diǎn)是兄弟(Brother)。定義10.3.4 如果在根樹(shù)中規(guī)定了每一層上結(jié)點(diǎn)的次序，這樣的根樹(shù)稱(chēng)為有序樹(shù)(Ordered Tree)。 一般地，在有序樹(shù)中同一層中結(jié)點(diǎn)的次序?yàn)閺淖笾劣?。有時(shí)也可以用邊的次序來(lái)代替結(jié)點(diǎn)的次序。 2022/9/13定義10.3.5在根樹(shù)T中，若每個(gè)分支

23、點(diǎn)至多有k個(gè)兒子，則稱(chēng)T為k元樹(shù)(k-ary Tree)；若每個(gè)分支點(diǎn)都恰有k個(gè)兒子，則稱(chēng)T為k元完全樹(shù)(k-ary Complete Tree)；若k元樹(shù)T是有序的，則稱(chēng)T為k元有序樹(shù)(k-ary Ordered Tree)；若k元完全樹(shù)T是有序的，則稱(chēng)T為k元有序完全樹(shù)(k-ary Ordered Complete Tree)。2022/9/13子樹(shù) 在根樹(shù)T中，任一結(jié)點(diǎn)v及其所有后代導(dǎo)出的子圖T稱(chēng)為T(mén)的以v為根的子樹(shù)(Subtree)。 二元有序樹(shù)的每個(gè)結(jié)點(diǎn)v至多有兩棵子樹(shù)，分別稱(chēng)為v的左子樹(shù)(Left Subtree)和右子樹(shù)(Right Subtree)。 注意區(qū)分以v為根的子樹(shù)和v

24、的左(右)子樹(shù)，v為根的子樹(shù)包含v，而v的左(右)子樹(shù)不包含v。2022/9/13例10.3.3判斷下圖所示的幾棵根樹(shù)是什么樹(shù)？(b)(c)(a)2元完全樹(shù) 3元樹(shù) 3元完全樹(shù) 3元有序完全樹(shù)122(d)1332132022/9/13k元完全樹(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)的出度為ki。因此有ki = i+t-1即 (k-1)i = t

25、-12022/9/13例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)2022/9/13一個(gè)多種解法的例子 例10.3.5 設(shè)T為任意一棵二元完全樹(shù)，m為邊數(shù)，t為葉

26、數(shù)，試證明：m = 2t-2，其中t2。證明 方法一：設(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。 2022/9/13方法二：例10.3.5 設(shè)T為任意一棵二元完全樹(shù)，m為邊數(shù)，t為葉數(shù)，試證明：m = 2t-2 ，其中t2。 在二元完全樹(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。2022

27、/9/13方法三： 對(duì)樹(shù)葉數(shù)t作歸納法。 當(dāng)t = 2時(shí)，結(jié)點(diǎn)數(shù)為3，邊數(shù)m = 2，故m = 2t-2成立。 假設(shè)t = k(k2)時(shí)，結(jié)論成立，下面證明t = k+1時(shí)結(jié)論也成立。 由于T是二元完全樹(shù)，因此T中一定存在都是樹(shù)葉的兩個(gè)兄弟結(jié)點(diǎn)v1, v2，設(shè)v是v1, v2的父親。在T中刪除v1, v2，得樹(shù)T，T仍為二元完全樹(shù)，這時(shí)結(jié)點(diǎn)v成為樹(shù)葉，樹(shù)葉數(shù)t= t-2+1 = k+1-1 = k，邊數(shù)m= m-2，由歸納假設(shè)知，m= 2t-2。所以m-2 = 2(t-2+1)-2，故m = 2t-2。2022/9/13方法四： 對(duì)分支點(diǎn)數(shù)i作歸納法。 當(dāng)i=1時(shí)，邊數(shù)m=2，樹(shù)葉數(shù)t=2，故

28、m=2t-2成立。 假設(shè)i = k(k1)時(shí)，結(jié)論成立，下面證明i = k+1時(shí)結(jié)論也成立。 由于T是二元完全樹(shù)，因此T中一定存在兩個(gè)兒子都是樹(shù)葉的分支點(diǎn)，設(shè)v就是這樣一個(gè)分支點(diǎn)，設(shè)它的兩個(gè)兒子為v1,v2 。在T中刪除v1,v2，得樹(shù)T，T仍為二元完全樹(shù)，這時(shí)結(jié)點(diǎn)v成為樹(shù)葉，分支點(diǎn)數(shù)i=i-1=k+1-1= k，樹(shù)葉數(shù)t= t-2+1，邊數(shù)m= m-2，由歸納假設(shè)知，m= 2t-2。所以m-2=2(t-2+1)-2，故m=2t-2。2022/9/1310.3.2 根樹(shù)的遍歷 對(duì)于根樹(shù)，一個(gè)十分重要的問(wèn)題是要找到一些方法，能系統(tǒng)地訪問(wèn)樹(shù)的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)恰好訪問(wèn)一次，這就是根樹(shù)的遍歷(Erg

29、ode)問(wèn)題。 k元樹(shù)中，應(yīng)用最廣泛的是二元樹(shù)。由于二元樹(shù)在計(jì)算機(jī)中最易處理，下面先介紹二元樹(shù)的3種常用的遍歷方法，然后再介紹將任意根樹(shù)轉(zhuǎn)化為二元樹(shù)。2022/9/13算法10.3.1二元樹(shù)的先根次序遍歷算法：訪問(wèn)根；按先根次序遍歷根的左子樹(shù)；按先根次序遍歷根的右子樹(shù)。2022/9/13算法10.3.2二元樹(shù)的中根次序遍歷算法：按中根次序遍歷根的左子樹(shù)；訪問(wèn)根；按中根次序遍歷根的右子樹(shù)。2022/9/13算法10.3.3二元樹(shù)的后根次序遍歷算法：按后根次序遍歷根的左子樹(shù)；按后根次序遍歷根的右子樹(shù)；訪問(wèn)根。2022/9/13例10.3.6寫(xiě)出對(duì)圖中二元樹(shù)的3種遍歷方法得到的結(jié)果。abedghkl

30、micjf解 先根遍歷次序?yàn)閍bdghceijklmf；中根遍歷次序?yàn)間dhbaielkmjcf；后根遍歷次序?yàn)間hdbilmkjefca。2022/9/13算法10.3.4根樹(shù)轉(zhuǎn)化為二元樹(shù)算法：從根開(kāi)始，保留每個(gè)父親同其最左邊兒子的連線(xiàn)，撤銷(xiāo)與別的兒子的連線(xiàn)。兄弟間用從左向右的有向邊連接。按如下方法確定二元樹(shù)中結(jié)點(diǎn)的左兒子和右兒子：直接位于給定結(jié)點(diǎn)下面的結(jié)點(diǎn)，作為左兒子，對(duì)于同一水平線(xiàn)上與給定結(jié)點(diǎn)右鄰的結(jié)點(diǎn)，作為右兒子，依此類(lèi)推。2022/9/13例10.3.7將下圖轉(zhuǎn)化為一棵二元樹(shù)。v1v2v3v4v5v6v7v10v11v9v1v2v3v4v5v6v7v8v10v11v9v1v2v3v4

31、v5v6v7v8v10v11v92022/9/13有序森林業(yè)轉(zhuǎn)換成二元樹(shù)算法10.3.5 森林轉(zhuǎn)化為二元樹(shù)算法：先把森林中的每一棵樹(shù)都表示成二元樹(shù)；除第一棵二元樹(shù)外，依次將剩下的每棵二元樹(shù)作為左邊二元樹(shù)的根的右子樹(shù)，直到所有的二元樹(shù)都連成一棵二元樹(shù)為止。2022/9/13例10.3.8將圖所示的森林轉(zhuǎn)化成一棵二元樹(shù)。v1v2v3v4v5v6v7v12v9v10v8v11v13v14v1v2v3v4v5v6v7v12v9v10v8v11v13v14將二元樹(shù)轉(zhuǎn)化為森林，要點(diǎn)是“先將根的右子樹(shù)變?yōu)樾露獦?shù)，再將這些二元樹(shù)還原為根樹(shù)”。 2022/9/1310.3.3 最優(yōu)樹(shù)與哈夫曼算法 在計(jì)算機(jī)及通

32、訊事業(yè)中，常用二進(jìn)制編碼來(lái)表示符號(hào)，稱(chēng)之為碼字(codeword)。 例如，可用00、01、10、11分別表示字母A、B、C、D，則傳輸100個(gè)字母用200個(gè)二進(jìn)制位。 但如果A出現(xiàn)的頻率為50，B出現(xiàn)的頻率為25，C出現(xiàn)的頻率為20，D出現(xiàn)的頻率為5。 用000表示字母D，用001表示字母C，01表示B，1表示A。則傳輸100個(gè)字母所用的二進(jìn)制位為35+320+225+150 = 175。2022/9/1310.3.3 最優(yōu)樹(shù)與哈夫曼算法 問(wèn)題：當(dāng)用1表示A，用00表示B，用001表示C，用000表示D時(shí)，如果接收到的信息為001000，則： 無(wú)法辨別它是CD還是BAD。 因而，不能用這種二

33、進(jìn)制序列表示A、B、C、D，要尋找另外的表示法。 問(wèn)題出現(xiàn)在哪里？2022/9/13定義10.3.6 設(shè)a1a2an-1an為長(zhǎng)度為n的符號(hào)串，稱(chēng)其子串a(chǎn)1，a1a2，, a1a2an-1分別為a1a2an-1an的長(zhǎng)度為1，2，n-1的前綴(Prefix)。 設(shè)A = b1, b2, , bm是一個(gè)符號(hào)串集合，若對(duì)任意bi, bjA，bibj，bi不是bj的前綴，bj也不是bi的前綴，則稱(chēng)A為前綴碼(Prefixed Code)。若符號(hào)串bi(i = 1, 2, m)中，只出現(xiàn)0和1兩個(gè)符號(hào)，則稱(chēng)A為二元前綴碼(Binary Prefixed Code)。 1, 01, 001, 000是前

34、綴碼1, 11, 001, 0011不是前綴碼。 2022/9/13例：1, 01, 001, 000是前綴碼1, 11, 001, 0011不是前綴碼。2022/9/13用二元樹(shù)產(chǎn)生二元前綴碼 給定一棵二元樹(shù)T，假設(shè)它有t片樹(shù)葉。 設(shè)v是T任意一個(gè)分支點(diǎn)，則v至少有一個(gè)兒子至多有兩個(gè)兒子。 若v有兩個(gè)兒子，則在由v引出的兩條邊上，左邊的標(biāo)上0，右邊的標(biāo)上1；若v只有一個(gè)兒子，在v引出的邊上可標(biāo)0也可標(biāo)1。 設(shè)vi為T(mén)的任意一片樹(shù)葉，從樹(shù)根到vi的通路上各邊的標(biāo)號(hào)組成的符號(hào)串放在vi處，t片樹(shù)葉處的t個(gè)符號(hào)串組成的集合為一個(gè)二元前綴碼。2022/9/13例圖中所示的二元樹(shù)產(chǎn)生的前綴碼為：1，0

35、0，010，011。因此用1表示A，用00表示B，用010表示 C，用011表示 即可滿(mǎn)足要求。010011100010011當(dāng)知道了傳輸?shù)姆?hào)出現(xiàn)的頻率時(shí)，如何選擇前綴碼，使傳輸?shù)亩M(jìn)制位盡可能地少呢？先產(chǎn)生最優(yōu)二元樹(shù)T，然后用T產(chǎn)生二元前綴碼。2022/9/13最優(yōu)樹(shù)定義10.3.7 設(shè)有一棵二元樹(shù)，若對(duì)其所有的t片葉賦以權(quán)值w1、w2、wt，則稱(chēng)之為賦權(quán)二元樹(shù)(Power Binary Tree)；若權(quán)為wi的葉的層數(shù)為L(zhǎng)(wi)，則稱(chēng) 為該賦權(quán)二元樹(shù)的權(quán)；而在所有賦權(quán)w1、w2、wt的二元樹(shù)中，W(T)最小的二元樹(shù)稱(chēng)為最優(yōu)樹(shù)(Optimal Tree)。 1952年哈夫曼(Huffma

36、n)給出了求最優(yōu)樹(shù)的方法。該方法的關(guān)鍵是：從帶權(quán)為W1+W2、W3、Wt(這里假設(shè)W1W2Wt)的最優(yōu)樹(shù)T中得到帶權(quán)為W1、W2、Wt的最優(yōu)樹(shù)。2022/9/13算法10.3.6 哈夫曼算法：初始：令S = W1, W2, , Wt；從S中取出兩個(gè)最小的權(quán)Wi和Wj，畫(huà)結(jié)點(diǎn)vi，帶權(quán)Wi，畫(huà)結(jié)點(diǎn)vj，帶權(quán)Wj。畫(huà)vi和vj的父親v，連接vi和v，vj和v，令v帶權(quán)Wi+Wj；令S = (S -Wi, Wj)Wi+Wj；判斷S是否只含一個(gè)元素？若是，則停止，否則轉(zhuǎn)2。2022/9/13例10.3.9求帶權(quán)7、8、9、12、16的最優(yōu)樹(shù)。1578916122131522022/9/13例10.3.

37、10用機(jī)器分辨一些幣值為1分、2分、5分的硬幣，假設(shè)各種硬幣出現(xiàn)的概率分別為0.5、0.4、0.1。問(wèn)如何設(shè)計(jì)一個(gè)分辨硬幣的算法，使所需的時(shí)間最少(假設(shè)每作一次判別所用的時(shí)間相同，以此為一個(gè)時(shí)間單位)？ 10.50.50.40.1(a)是否5分5分是2分1分(b)是否2分否是否所需時(shí)間：20.1+20.4+10.5 = 1.5(時(shí)間單位)。 2022/9/13例10.3.11已知字母A、B、C、D、E、F出現(xiàn)的頻率如下：A30，B25，C20D10，E10，F(xiàn) 5構(gòu)造一個(gè)表示A、B、C、D、E、F前綴碼，使得傳輸?shù)亩M(jìn)制位最少。解（1）求帶權(quán)30,25,20,10,10,5的最優(yōu)二元樹(shù)T。（2

38、）在T上求一個(gè)前綴碼。01001101000000101015101020253015254555100101100012022/9/13（3）設(shè)樹(shù)葉vi帶權(quán)為w100 = w，則vi處的符號(hào)串表示出現(xiàn)頻率為w的字母。01，10，11，001，0001，0000為一前綴碼，其中0000表示F，0001表示E，001表示D，01表示C，10表示B，11表示A。傳輸100個(gè)這樣的字母所用的二進(jìn)制位為：4(5+10)+310+2(20+25+30) = 240。 A30，B25，C20D10，E10，F(xiàn) 52022/9/1310.3.4 根樹(shù)的難點(diǎn) 有向樹(shù)是略去所有邊的方向所得無(wú)向圖為無(wú)向樹(shù)的有向圖

39、；根樹(shù)是只有一個(gè)結(jié)點(diǎn)的入度為0，其余結(jié)點(diǎn)的入度均1的有向樹(shù)；注意根樹(shù)的葉和分支點(diǎn)與無(wú)向數(shù)的葉和分支點(diǎn)的細(xì)微差別；有序樹(shù)是對(duì)結(jié)點(diǎn)標(biāo)定了順序的根樹(shù)；k元樹(shù)的每個(gè)分支點(diǎn)至多有k個(gè)兒子，因此其出度均小于等于k，一般取滿(mǎn)足條件的最小值k；k元完全樹(shù)的每個(gè)分支點(diǎn)都恰有k個(gè)兒子，因此其出度均恰好等于k；2022/9/13根樹(shù)的難點(diǎn) 注意區(qū)分以v為根的子樹(shù)和v的左子樹(shù)、右子樹(shù)；二元樹(shù)遍歷的3種方法：先根次序遍歷法、中根次序遍歷法、后根次序遍歷法；有序樹(shù)、森林與二元樹(shù)之間的相互轉(zhuǎn)換；一棵根樹(shù)也可看成一個(gè)家族，若邊在樹(shù)中，則稱(chēng)a是b的父親，b是a兒子。若,都在樹(shù)中，且bc,則b,c稱(chēng)為兄弟。若a可達(dá)b,則稱(chēng)a是b

40、的祖先，b是a的后代；最優(yōu)樹(shù)與哈夫曼算法。 2022/9/1310.3.5 根樹(shù)的應(yīng)用 1、計(jì)算機(jī)的文件結(jié)構(gòu) 2022/9/132、波蘭符號(hào)法與逆波蘭符號(hào)法 規(guī)定用樹(shù)葉表示參加運(yùn)算的元素，分支結(jié)點(diǎn)表示相應(yīng)的運(yùn)算。jhifgedabc (a+(bc)d-e)(f+g)+(hi)j 2022/9/13中綴符號(hào)法按中根次序遍歷算法訪問(wèn)T，其結(jié)果為(a+(bc)d)-e)(f+g)+(hi)j)，根據(jù)運(yùn)算符的優(yōu)先次序可以省去部分括號(hào)，得(a+bc)d-e)(f+g)+hij。因?yàn)檫\(yùn)算符夾在兩數(shù)之間，故稱(chēng)此種表示法為中綴符號(hào)法。2022/9/13波蘭符號(hào)法按先根次序遍歷算法訪問(wèn)T，其結(jié)果為+(-(+a(bc)d)e)(+fg)(hi)j)，省去全部括號(hào)后，規(guī)定每個(gè)運(yùn)算符對(duì)它后面緊鄰的兩個(gè)數(shù)進(jìn)行運(yùn)算，仍是正確的。因而可省去全部括號(hào)，其結(jié)果為+-+abcde+fghij。因?yàn)檫\(yùn)算符在參加運(yùn)算的兩數(shù)之前，故稱(chēng)此種表示法為前綴符號(hào)法，或稱(chēng)為波蘭符號(hào)法。 2022/9/13逆波蘭符號(hào)法按后根次序遍歷算法訪問(wèn)T，其結(jié)果為(a(bc)+)d)e-)(fg+)(hi)j)+，省去全部括號(hào)后，規(guī)定每個(gè)運(yùn)算符對(duì)它前面緊鄰的兩個(gè)數(shù)進(jìn)行運(yùn)算，仍是正確的。因而可省去