文庫發(fā)布：121aolm離散數(shù)學(xué)

第1篇數(shù)理邏輯第2篇集合論第3篇代數(shù)結(jié)構(gòu)第4篇圖論第4篇圖論模型化是數(shù)學(xué)中的一個(gè)基本概念，它處于所有的數(shù)學(xué)應(yīng)用之心臟，也處于某些最抽象的純數(shù)學(xué)核心之中。

R.C.Buck第4篇圖論第10章圖第11章特殊圖第12章樹第4篇圖論第12章樹12.1樹的概念12.2生成樹12.3根樹、二叉樹及其應(yīng)用12.4典型例題解析第12章樹 幾何、理論算術(shù)和代數(shù)，這些學(xué)科除了定義和公理之外，沒有其它原則，除了演繹以外，沒有其它證明過程。但就在這一過程中，卻已綜合了簡(jiǎn)單性、復(fù)雜性、嚴(yán)密性和一般性，這一特性是不為其它學(xué)科所具有的。

WhewellW. 首先介紹樹的基本概念；然后將分別介紹生成樹、根樹及特殊的一類根樹——二叉樹及其應(yīng)用。第12章樹樹是一類特殊的二分圖（偶圖）。作為計(jì)算機(jī)科學(xué)中常用的一種數(shù)據(jù)結(jié)構(gòu)，樹有許多非常好的性質(zhì)，因此樹被廣泛地應(yīng)用于算法設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、網(wǎng)絡(luò)、人工智能、軟件工程、知識(shí)工程以及其他領(lǐng)域。

12.1樹的概念

定義12.1一個(gè)連通且無回路的無向圖稱為樹。在樹中度數(shù)為1的結(jié)點(diǎn)稱為樹葉，度數(shù)大于1的結(jié)點(diǎn)稱為分枝點(diǎn)（內(nèi)點(diǎn)）。單一孤立結(jié)點(diǎn)稱為空樹。如果一個(gè)無回路的無向圖的每一個(gè)連通分圖是樹，且連通分支數(shù)大于等于2，那么稱為森林。v3v2v7v4v1v9v5v8v6（a）樹（b）樹（c）森林定理12.1“給定圖為樹”與下列任一命題等價(jià)： （1）無回路的連通圖； （2）無回路且e=v-1，其中e是邊數(shù)，v是結(jié)點(diǎn)數(shù)； （3）連通且e=v-1； （4）無回路，但增加一條新邊，得到一個(gè)且僅有一個(gè)回路； （5）連通，但刪去一邊后就不再連通； （6）每一對(duì)結(jié)點(diǎn)之間有且僅有一條路。證明：將一次證明⑴

⑵、⑵

⑶、⑶

⑷、⑷

⑸、⑸

⑹、⑹

⑴，從而證明6個(gè)命題之間的等價(jià)性，使定理得證。 （1）歸納法證明⑴

⑵

設(shè)在圖T中，當(dāng)v＝2時(shí)，連通無向圖，T中 的邊數(shù)e＝1，因此e＝v

1 成立。

設(shè)v＝k

1時(shí)命題成立，當(dāng)v＝k時(shí)，因無向圖且連通，故至少有一條邊其一個(gè)端點(diǎn)u的度數(shù)為1。設(shè)該邊為(u,w)，刪去結(jié)點(diǎn)u，便得到一個(gè)k

1個(gè)結(jié)點(diǎn)的連通無向圖T’，由歸納假設(shè)，圖T’的邊數(shù)

e’＝v’

1＝(k

1)

1＝k

2，于是再將結(jié)點(diǎn)u和關(guān)聯(lián)邊(u,w)加到圖T’中得到原圖T，此時(shí)圖T的邊數(shù)為:

e＝e’

1＝(k

2)

1＝k

1，結(jié)點(diǎn)數(shù)v＝v’

1＝(k

1)

1＝k，故

e＝v

1

成立。（2）反證法證明⑵

⑶若T不連通，并且有k(k≥2)個(gè)連通分支T1,T2,…,Tk，因?yàn)槊總€(gè)分圖是連通無回路，則可證：如Ti

有vi

個(gè)結(jié)點(diǎn)vi＜v時(shí)，Ti

有vi

1

條邊，而

v＝v1

v2

…

vk e＝(v1

1)

(v2

1)

…

(vk

1)＝v

k

但 e＝v

1

故 k＝1

這與假設(shè)G是不連通的，即

k≥2 相矛盾。（3）歸納法證明⑶

⑷若T連通且有v

1條邊。

當(dāng)v＝2時(shí)，e＝v

1＝1，故T必?zé)o回路。如增加一條邊，那么得到且僅得到一個(gè)回路。

設(shè)v＝k

1時(shí)命題成立?？疾靨＝k時(shí)的情況，因?yàn)門是連通的，e＝v

1。故每個(gè)結(jié)點(diǎn)u有

deg(u)≥1

可以證明至少有一結(jié)點(diǎn)u0，使

deg(u0)＝1

若不然，即所有結(jié)點(diǎn)u有deg(u)≥2，則2e≥2v，即e≥v

與假設(shè)e＝v

1

矛盾。 刪去u0

及其關(guān)聯(lián)的邊，而得到圖T′，由歸納假設(shè)得知T′無回路，在T′中加入u0

及其關(guān)聯(lián)邊又得到T，故T無回路的，如在T中增加一條邊(ui,uj)，則該邊與T中ui

到uj

的路構(gòu)成一個(gè)回路，則該回路必是唯一的，否則若刪除這條新邊，T必有回路，得出矛盾。（4）反證法證明⑷

⑸若圖T不連通，則存在結(jié)點(diǎn)ui

與uj，ui

與uj

之間沒有路，顯然若加邊{ui，uj}不會(huì)產(chǎn)生回路，與假設(shè)矛盾。又由于T無回路，故刪去任一邊，圖就不連通。（5）反證法證明⑸

⑹由連通性可知，任兩個(gè)結(jié)點(diǎn)間有一條路，若存在兩點(diǎn)，在它們之間有多于一條的路，則T中必有回路，刪去該回路上任一條邊，圖仍是連通的，與命題⑸矛盾。（6）反證法證明⑹

⑴任意兩點(diǎn)間必有唯一一條路，則T必連通，若有回路，則回路上任兩點(diǎn)間有兩條路，與命題⑹矛盾。

根據(jù)定理12.1，如果刪除樹圖的任意一邊，樹就不再連通，所以在保持相同結(jié)點(diǎn)的圖中，樹是“最小的連通圖”。如果為樹圖增加一邊，那么圖中將由回路，所以在保持相同結(jié)點(diǎn)的圖中，樹是“最大的無回路圖”。樹以“最經(jīng)濟(jì)”的方式把圖中各結(jié)點(diǎn)連接起來。因此，樹作為典型的數(shù)據(jù)結(jié)構(gòu)被應(yīng)用在各類網(wǎng)絡(luò)的主干網(wǎng)中。除了上邊描述的樹的性質(zhì)之外，樹還有其他一些特殊的性質(zhì)。定理12.2樹和森林都是2-可著色的，因此樹和森林都是二分圖。 證明略。定理12.3樹和森林都是面數(shù)為1的平面圖。 證明略。定理12.4任何樹至少有兩片葉子。證明：設(shè)樹T＝<V,E>，＝v，因?yàn)門是連通圖，對(duì)于任意，有

deg(Vi)≥1

且

(1)若T中每一個(gè)結(jié)點(diǎn)的度數(shù)大于等于2，則 得出矛盾。

(2)若T中只有一個(gè)結(jié)點(diǎn)度數(shù)為1，其它結(jié)點(diǎn)的度數(shù)大于等于2，則 得出矛盾。 故T至少有兩個(gè)結(jié)點(diǎn)度數(shù)為1，即： 任何樹至少有兩片葉子。

12.2生成樹樹是一種具有優(yōu)秀結(jié)構(gòu)的、最經(jīng)濟(jì)的圖。人們希望能很好地利用樹這種結(jié)構(gòu)。一些連通圖雖然本身不是樹，但是根據(jù)樹的特性，人們想到連通圖的“最小連通生成子圖”應(yīng)當(dāng)是樹，其中，重要的一類是生成樹。

定義12.2若圖G的生成子圖是一棵樹，則該樹稱為G的生成樹。設(shè)圖G有一棵生成樹T，則T中的邊稱作樹枝。圖G中不在生成樹上的邊稱為弦。所有弦的集合稱為生成樹T相對(duì)于G的補(bǔ)。 上圖所示的連通圖G的一棵生成樹T如圖(b)所示，其中e1,e4,e6,e5,e8是T的樹枝

e2,e3,e7

是T的弦。{e2,e3,e7}是生成樹T的補(bǔ)。e3e1e6e4e5e2e7e8e1e6e4e5e8（a）（b）【例12.1】請(qǐng)找出下圖(a)所示的圖G的所有生成樹。解：圖G的生成樹如圖(b)~(l)所示。

v4v1v2v3v5v6v7v8（a）v4v1v2v3v5v6v7v8（b）v4v1v2v3v5v6v7v8（c）v4v1v2v3v5v6v7v8（d）v4v1v2v3v5v6v7v8（e）v4v1v2v3v5v6v7v8（f）v4v1v2v3v5v6v7v8（g）v4v1v2v3v5v6v7v8（h）v4v1v2v3v5v6v7v8（i）v4v1v2v3v5v6v7v8（k）v4v1v2v3v5v6v7v8（j）v4v1v2v3v5v6v7v8（l）由此可見，一個(gè)連通圖的生成樹不唯一。定理12.5任一連通圖都至少有一棵生成樹。證明：⑴設(shè)連通圖G沒有回路，則它本身就是一棵生成樹。 ⑵若G至少有一個(gè)回路，刪去回路上的一條邊，得到G1，它仍然是連通的，并與G有相同的結(jié)點(diǎn)集。 若G1

沒有回路，則G1

就是G的生成樹。 ⑶若G1

仍然有回路，那么再刪去G1

回路上的一條邊，重復(fù)上面的步驟，直到得到一個(gè)連通圖H，它沒有回路，但與G有相同的結(jié)點(diǎn)集，因此H為G的生成樹。定理12.5證明再次說明，一個(gè)連通圖的生成樹是不唯一的。生成樹有兩個(gè)很重要的性質(zhì)。定理12.6設(shè)G為連通無向圖，那么：（1）G的任一回路與任一生成樹T的關(guān)于G的補(bǔ)G-T至少有一條公共邊。

（2）G的任一邊割集與任一生成樹T至少有一條公共邊。證明：反證法。 （1）若有一條回路和一棵生成樹的補(bǔ)沒有公共邊，那么這回路包含在生成樹之中，然而這是不可能的，因?yàn)橐豢蒙蓸洳荒馨芈贰? （2）若有一條邊割集和一棵生成樹沒有公共邊，那么刪去這個(gè)邊割集后，所得的子圖必然包含該生成樹，這意味著刪去邊割集后仍然連通，與邊割集定義矛盾。定義12.3設(shè)G是具有n個(gè)結(jié)點(diǎn)的帶權(quán)連通圖。G的生成樹T的所有邊的權(quán)之和為樹的權(quán)。在圖G的所有生成樹中，樹權(quán)最小的那棵生成樹稱作最小生成樹。注意，帶權(quán)圖G的最小生成樹不唯一。7810（a）2025131425630301130418143097810（b）25131461130309帶權(quán)圖G和它的一個(gè)最小生成樹T

下面我們給出求帶權(quán)圖G的最小生成樹的Kruskal

算法。算法12.1(Kruskal)設(shè)圖G有n個(gè)結(jié)點(diǎn)，按以下步驟可以求得圖G的最小生成樹。 （1）按權(quán)值升序?qū)DG的邊排序，得到表L； （2）令； （3）在表L中依次選取下一條邊e，如果，且 構(gòu)成的子圖是無圈圖，則令； （4）若，則算法停止，輸出集合S即為所求。否則，轉(zhuǎn)⑶，繼續(xù)遍歷表L。 可以證明，算法12.1求得的是圖G的最小生成樹?！纠?2.2】應(yīng)用算法12.1求圖G的最小生成樹，G如圖(a)所示。求最小生成樹

e5（a）Gv61214v5v4v1v7v3v2e1e6e8e4e7e9e3e10e11e224155441e5（b）G的最小生成樹

v61214v5v4v1v7v3v2e1e6e4e7e2141解： （1）根據(jù)Kruskal

算法，首先根據(jù)圖G得到按權(quán)值的邊排序表L：e5,e7,e2,e4,e6,e8,e9,e1,e10,e3,e11

。 （2）然后，令。 （3）接下來，依次將e5,e7,e2,e4,e6,e1

放入S中；邊e8,e9

被忽略，因?yàn)樗鼈兊募尤霑?huì)形成圈。 （4）此時(shí)S中有6條邊，滿足，所以算法結(jié)束。得到的最小生成樹T如圖(b)所示，樹權(quán)為10。

最小生成樹的構(gòu)造還可以使用其他算法。算法12.2（Prim算法） （1）選出結(jié)點(diǎn)v，令，； （2）在所有的結(jié)點(diǎn)中，若連接結(jié)點(diǎn)u和w的邊e＝uw

是最小權(quán)重邊，其中，，則令，； （3）若，算法停止，輸出。否則，轉(zhuǎn)⑵，繼續(xù)向樹中增加新結(jié)點(diǎn)?！纠?2.3】使用Prim算法求圖G的最小生成樹。解：不失一般性，選出結(jié)點(diǎn)v1，令，。 圖(a)~(g)顯示出按照Prim算法求最小生成樹的過程。

e5Gv61214v5v4v1v7v3v2e1e6e8e4e7e9e3e10e11e224155441e5（g）V(T)={V1,V6,V5,V7,V4,V2,V3}E(T)={e6,e5,e7,e4,e10,e2}v61214v5v4v1v7v3v2e6e4e7e10e2141e5（c）V(T)={V1,V6,V5

}E(T)={e6,e5}v6124v5v1e6e5（d）V(T)={V1,V6,V5,V7

}E(T)={e6,e5,e7}v6124v5v1v7e6e71（b）V(T)={V1,V6}E(T)={e6}v62v1e6（b）V(T)={V1

}E(T)={}v1e5（f）V(T)={V1,V6,V5,V7,V4,V2}E(T)={e6,e5,e7,e4,e10}v61214v5v4v1v7v2e6e4e7e1014e5（e）V(T)={V1,V6,V5,V7,V4

}E(T)={e6,e5,e7,e4}v61214v5v4v1v7e6e4e71注意，例12.3求得的最小生成樹（圖(g)）不同于例12.2（圖(b)）。這也說明一個(gè)圖的最小生成樹不唯一。12.3根樹、二叉樹及其應(yīng)用本節(jié)之前，所討論的特殊圖都是無向圖。本節(jié)將討論一類有向圖，也是一類特殊的樹——根樹。12.3.1根樹定義12.4如果一個(gè)有向圖在不考慮邊的方向時(shí)是一棵樹，那么，這個(gè)有向圖稱為有向樹。 有向樹定義12.5一棵有向樹，如果恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度都為1，則稱為根樹。入度為0的結(jié)點(diǎn)稱為根，出度為0的結(jié)點(diǎn)稱為葉子，出度不為0的結(jié)點(diǎn)稱為分支點(diǎn)或內(nèi)點(diǎn)。根樹右圖表示一棵根樹，其中，V0

為根，V4,V5,V3,V8,V9,V10

為葉子，V1,V2,V6,V7

為內(nèi)點(diǎn)或分支點(diǎn)。V0V3V2V1V7V6V5V4V10V9V8定義12.6設(shè)a是一棵根樹的分支點(diǎn)，b、c是結(jié)點(diǎn)。如果從a到b存在一條邊，則結(jié)點(diǎn)b被稱為a的“兒子”結(jié)點(diǎn)，a為b的“父親”結(jié)點(diǎn)。如果從a到c存在一條單向通路，則a被稱為的“祖先”，c為a的“后裔”。同一個(gè)分支點(diǎn)的“兒子”結(jié)點(diǎn)被稱為“兄弟”結(jié)點(diǎn)。 上圖中，v0為v1,v2,v3

的“父親”，v1,v2,v3

是v0的“兒子”；v0是v4,v5,v6,v7,v8,v9,v10

的祖先，它們是v0

的“后裔”；v1,v2,v3

三者是“兄弟”。 根樹的任一結(jié)點(diǎn)v的層次是從根到該結(jié)點(diǎn)的單向通路長度。在上圖中，v1,v2,v3

的層次是1，v4,v5,v6,v7

的層次是2，v9,v10

的層次是3。在許多情況下，需要對(duì)根樹中同一父親的兒子規(guī)定某種順序。定義12.7如果根樹T為每個(gè)父親結(jié)點(diǎn)的兒子結(jié)點(diǎn)規(guī)定了次序，則稱T為有序樹。通常默認(rèn)的順序?yàn)閺淖蟮接摇?/p>

根據(jù)根樹的結(jié)構(gòu)特點(diǎn)，根樹還可以遞歸定義為：定義12.8樹T稱為根樹，如果：

（1）T為一個(gè)孤立結(jié)點(diǎn)v0，v0又被稱為T的樹根；

（2）T1…Tk

為以v1…vk

為樹根的根樹，T1由T1…Tk

及與v1…vk

相鄰的結(jié)點(diǎn)v0

組成。稱v0為T的樹根。根樹除了具有樹的一般特性外，還有下列簡(jiǎn)明特性:

（1）根樹的每個(gè)結(jié)點(diǎn)都是一顆子樹的樹根； （2）除了樹根，根樹中每結(jié)點(diǎn)均為某一結(jié)點(diǎn)的兒子，除了樹葉，根樹中每一結(jié)點(diǎn)均為某些結(jié)點(diǎn)的父親； （3）樹根到葉子有唯一的通路，這樣的通路中最長一條的長度稱為樹高。為了圖示清晰，通常約定：根樹的樹根總畫在樹的頂部，同一結(jié)點(diǎn)的兒子畫在同一水平線上。12.3.2二叉樹及其遍歷有一類特殊的根樹稱為二叉樹。由于二叉樹有許多很好的特性，所以二叉樹有廣泛的應(yīng)用。定義12.9在根樹中，若每一個(gè)結(jié)點(diǎn)的出度小于或等于m，則這棵樹稱為m叉樹；若m＝2時(shí)，稱為二叉樹。如果每一個(gè)結(jié)點(diǎn)的出度恰好等于m或零，則這棵樹稱為完全m叉樹；若m＝2時(shí)，稱為完全二叉樹。若所有的樹葉層次相同，則這棵樹稱為正則m叉樹；若m＝2時(shí)，稱為正則二叉樹。

圖(a)~(d)分別給出了m叉樹、二叉樹、完全二叉樹、正則二叉樹。（a）m叉樹（b）二叉樹（c）完全二叉樹（d）正則二叉樹現(xiàn)實(shí)生活許多問題都可以用二叉樹來描述和求解。例如，A和B進(jìn)行一場(chǎng)網(wǎng)球比賽。如果一人連勝兩盤活五盤三勝，那么他就獲勝。每一盤比賽要么A獲勝，要么B獲勝，只有這兩種可能。因此，A和B得比賽可能產(chǎn)生的結(jié)果可以用二叉樹來表示，如圖所示。AAABAAAAAABBBBBB二叉樹表示的比賽結(jié)果任一棵叉樹都可以改寫為一棵對(duì)應(yīng)的二叉樹。圖(a)為m叉樹，將其轉(zhuǎn)換為圖(c)所示的二叉樹，方法如下： （1）保留每個(gè)結(jié)點(diǎn)最左邊的分支點(diǎn)，刪去所有其他分支。同一層中，兄弟結(jié)點(diǎn)之間以從左到右的有向邊連接，如圖(b)所示。DBCAJHEFKIGDBCAJHEFKIG（a）m叉樹

（b）轉(zhuǎn)換第一步

（2）將直接處于給定結(jié)點(diǎn)下面的結(jié)點(diǎn)，作為左兒子，與給定結(jié)點(diǎn)處于同一水平線上的右鄰結(jié)點(diǎn)作為右兒子，如圖(c)所示。

DBCAJHEFKIGDBCAJHEFKIG（b）轉(zhuǎn)換第一步

（c）與(a)對(duì)應(yīng)的二叉樹

同樣地，此方法可以推廣到森林，將森林改寫為二叉樹。圖(a)所示的森林被轉(zhuǎn)換為圖(c)所示的二叉樹。DBCAJHEFKIGLM(a)DBCAJHEFKIGLM(b)DBCAJHEFKIGLM(c)完全二叉樹的一些性質(zhì)。 定理12.7設(shè)完全m叉樹，有t片葉子、i個(gè)分支點(diǎn)，則。 證明：若把m叉樹當(dāng)作是每局有m位選手參加比賽的單淘汰賽計(jì)劃表，樹葉數(shù)為t表示參加比賽的選手?jǐn)?shù)，分枝點(diǎn)數(shù)為i表示比賽的局?jǐn)?shù)，因?yàn)槊烤直荣悓⑻蕴?m

1)位選手，比賽的結(jié)果共淘汰(m

1)i位選手，最后剩下一個(gè)冠軍，因此(m

1)i

1＝t即(m

1)i＝t

1。定義12.10在根樹中，從樹根到某個(gè)結(jié)點(diǎn)的通路中的邊數(shù)稱為該結(jié)點(diǎn)的通路長度。分枝點(diǎn)的通路長度稱作內(nèi)部通路長度，樹葉的通路長度稱作外部通路長度。最長的外部通路長度稱為樹高。定理12.8若完全二叉樹有n個(gè)分支點(diǎn)，內(nèi)部通路長度總和為

I，外部通路長度總和為E，則。證明：歸納法。對(duì)分枝點(diǎn)數(shù)目n進(jìn)行歸納。 （1）當(dāng)n＝1時(shí)，E＝2，I＝0，故

E＝I

2n 成立。 （2）假設(shè)n＝k

1時(shí)成立，即

E’＝I’

2(k

1)

（3）當(dāng)n＝k時(shí)，若刪除去一個(gè)分枝點(diǎn)v，該分枝點(diǎn)與根的通路長度為l，且v的兩個(gè)兒子是樹葉，得到新樹T’。將T’與原樹比較，它減少了兩片長度為l

1的樹葉和一個(gè)長度為l的分枝點(diǎn)，因?yàn)門’有(k

1)個(gè)分枝點(diǎn)，故E’＝I’

2(k

1)。但在原樹中，有E＝E’

2(l

1)

l＝E’

l

2,I＝I’

l，代入上式得E

l

2＝I

l

2(k

1)，即

E＝I

2k 成立。定理12.9完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)必定為奇數(shù)。 證明：完全二叉樹中，除樹根的度為2外，其它結(jié)點(diǎn)的度均為3或1，因此完全二叉樹的度數(shù)總和為n

1個(gè)奇數(shù)的和加上2。若n為偶數(shù)，則n

1為奇數(shù)，從而樹的度數(shù)總和為奇數(shù)，但這是不可能的。因此n必為奇數(shù)。定理12.10完全二叉樹中葉子的數(shù)目，其中n為樹中的結(jié)點(diǎn)個(gè)數(shù)。 證明：設(shè)完全二叉樹T有n個(gè)結(jié)點(diǎn)、l片葉子和m條邊，那么，除樹根和葉子以外，T有n

1

l個(gè)、度為3的分支結(jié)點(diǎn)，因此有：得為定理12.11設(shè)完全二叉樹有n個(gè)結(jié)點(diǎn)，則完全二叉樹的高h(yuǎn)滿足，其中[]表示取整運(yùn)算，取不大于[]中的表達(dá)式值得最大整數(shù)。證明：先證，再證。

（1）如果高為h

的完全二叉樹的樹根到每片葉子的通路長度均為h

，那么，該樹的結(jié)點(diǎn)數(shù)為 因此，對(duì)一般高為h的完全二叉樹而言，其結(jié)點(diǎn)數(shù) 即： 因此 故（2）如果高為h的完全二叉樹的每個(gè)分支結(jié)點(diǎn)的兩個(gè)兒子結(jié)點(diǎn)中必有一個(gè)是葉子，那么它的結(jié)點(diǎn)數(shù)應(yīng)是(h

1)

h，而對(duì)一般高為h的完全二叉樹而言，其結(jié) 點(diǎn)數(shù)為 故

由⑴⑵可知，有n個(gè)結(jié)點(diǎn)的完全二叉樹其樹高h(yuǎn)滿足算法12.3二叉樹的前序遍歷（先根遍歷）（1）訪問二叉樹的根r（先根、前序）；（2）如果r有左兒子，那么以前序遍歷算法訪問r的左子樹（以r的左兒子為根的子樹）；（3）如果r有右兒子，那么以前序遍歷算法訪問r的右子樹（以r的右兒子為根的子樹）。算法12.4二叉樹的中序遍歷（中根遍歷）（1）如果二叉樹樹根r有左兒子，那么以中序遍歷算法訪問r的左子樹（以r的左兒子為根的子樹）；（2）訪問二叉樹的根r（中根、中序）；（3）如果r有右兒子，那么以中序遍歷算法訪問r的右子樹（以r的右兒子為根的子樹）。算法12.5二叉樹的后序遍歷（后根遍歷）（1）如果二叉樹樹根r有左兒子，那么以后序遍歷算法訪問r的左子樹（以r的左兒子為根的子樹）；（2）如果r有右兒子，那么以后序遍歷算法訪問r的右子樹（以r的右兒子為根的子樹）；（3）訪問二叉樹的根r（后根、后序）；【例12.4】請(qǐng)用前序、中序和后序遍歷算法遍歷圖中所示的二叉樹。解： ⑴前序遍歷結(jié)果：； ⑵中序遍歷結(jié)果：； ⑶后序遍歷結(jié)果：DBCAJHFKIG二叉樹的遍歷

E12.3.3應(yīng)用舉例 二叉樹的第一個(gè)應(yīng)用就是最優(yōu)樹。 定義12.11設(shè)二叉樹T有t片葉子，分別帶權(quán)為w1,w2,…,wt，則T稱為帶權(quán)二叉樹。如果T中帶權(quán)wi

的葉子，其通路長度為L(wi)，則稱為帶權(quán)二叉樹T的權(quán)。在所有帶權(quán)w1,w2,…,wt的T中，w(T)最小的那棵被稱為最優(yōu)樹。

該定義可以從二叉樹推廣到m叉樹。定義12.12具有t片葉子、帶權(quán)w1,w2,…,wt

的m叉樹中，帶權(quán)最小的m叉樹稱為最優(yōu)m叉樹。在給出求最優(yōu)樹的算法之前，我們必須先證明下面的定理。定理12.12設(shè)T是帶權(quán)的最優(yōu)樹，則： （1）帶權(quán),的葉子,是兄弟； （2）以,為兒子的分支點(diǎn)具有最長的通路長度。證明：設(shè)在帶權(quán),,…,的最優(yōu)樹中，v是通路長度最長的分枝點(diǎn)，v的兒子分別為wx

和wy，故有

L(wx)≥L(w1) L(wy)≥L(w2)

若有L(wx)＞L(w1)，將wx

與w1

對(duì)調(diào)，得到新樹T’，則

w(T’)

w(T)＝(L(wx)·w1

L(w1)·wx)

(L(wx)·wx

L(w1)·w1)＝

L(wx)(w1

wx)

L(w1)(

wx

w1)＝(

wx

w1)(L(w1)

L(wx))＜0即

w(T’)＜w(T)

與T是最優(yōu)樹的假定矛盾。故 L(wx)＝

L(w1)同理可證 L(wy)＝

L(w2)因此 L(w1)＝

L(w2)＝

L(wx)＝

L(wy)分別將w1，w2

與wx，wy

對(duì)調(diào)，得到一棵最優(yōu)樹，其中帶權(quán)w1

和w2

的樹葉是兄弟。

定理12.13設(shè)T是帶權(quán)的最優(yōu)樹。如果將帶權(quán)w1,w2的葉子的父結(jié)點(diǎn)由分支點(diǎn)改為帶權(quán)的葉子結(jié)點(diǎn)，得到一棵新樹T，則T也是最優(yōu)樹。證明：根據(jù)題設(shè)，有 w(T)＝w(T’)

w1

w2

若T’不是最優(yōu)樹，則必有另外一棵帶權(quán)為 w1

w2，w3，…，wt的最優(yōu)樹T”。 對(duì)T”中帶權(quán)為w1

w2的樹葉vw1

w2生成兩個(gè)兒子，得到樹，則

w()＝w(T”)

w1

w2

因?yàn)門”是帶權(quán)為w1

w2，w3，…，wt

的最優(yōu)樹,

故 w(T”)≤w(T’)如果 w(T”)＜w(T’) 則 w()＜w(T)

與T是帶權(quán)為w1，w2，…，wt

最優(yōu)樹矛盾，因此

w(T”)＝w(T’) T′一棵帶權(quán)為w1

w2，w3，…，wt

的最優(yōu)樹。根據(jù)上述定理，1952年，D.A.Huffman

給出求最優(yōu)二叉樹的算法。根據(jù)上面兩個(gè)定理，要畫一棵帶有t個(gè)權(quán)的最優(yōu)樹，可簡(jiǎn)化為畫一棵帶有t

1個(gè)權(quán)的最優(yōu)樹，而又可簡(jiǎn)化為畫一棵帶t

2個(gè)權(quán)的最優(yōu)樹，依此類推。具體的做法是：首先找出兩個(gè)最小w值，設(shè)為w1

和w2，然后對(duì)t

1個(gè)權(quán)w1

w2,w3,…,wt求作一棵最優(yōu)樹，并且將這棵最優(yōu)樹的結(jié)點(diǎn)vw1

w2

分叉生成兩個(gè)兒子v1

和v2，依此類推。23571113171923293137415571113171923293137411071113171923293137411711131719232931374117241719232931374124341923293137412434422931374134425331374142536537414253657895657895143

238【例12.5】設(shè)一組權(quán)2,3,5,7,11,13,17,19,23,29,31,37,41。求相應(yīng)的最優(yōu)樹。解：求最優(yōu)樹的過程可描述為：最優(yōu)樹

二叉樹的另一個(gè)應(yīng)用是前綴碼。在遠(yuǎn)距離通訊中，常常用0和1的字符串作為英文字母?jìng)魉托畔?，因?yàn)橛⑽淖帜腹灿?6個(gè)，故用不等長的二進(jìn)制序列表示26個(gè)英文字母時(shí)，由于長度為1的序列有2個(gè)，長度為2的二進(jìn)制序列有2