第1篇數理邏輯第2篇集合論第3篇代數結構第4篇圖論第4篇圖論模型化是數學中的一個基本概念，它處于所有的數學應用之心臟，也處于某些最抽象的純數學核心之中。

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

WhewellW. 首先介紹樹的基本概念；然后將分別介紹生成樹、根樹及特殊的一類根樹——二叉樹及其應用。第12章樹樹是一類特殊的二分圖（偶圖）。作為計算機科學中常用的一種數據結構，樹有許多非常好的性質，因此樹被廣泛地應用于算法設計、數據結構、網絡、人工智能、軟件工程、知識工程以及其他領域。

12.1樹的概念

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

⑵、⑵

⑶、⑶

⑷、⑷

⑸、⑸

⑹、⑹

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

⑵

設在圖T中，當v＝2時，連通無向圖，T中 的邊數e＝1，因此e＝v

1 成立。

設v＝k

1時命題成立，當v＝k時，因無向圖且連通，故至少有一條邊其一個端點u的度數為1。設該邊為(u,w)，刪去結點u，便得到一個k

1個結點的連通無向圖T’，由歸納假設，圖T’的邊數

e’＝v’

1＝(k

1)

1＝k

2，于是再將結點u和關聯邊(u,w)加到圖T’中得到原圖T，此時圖T的邊數為:

e＝e’

1＝(k

2)

1＝k

1，結點數v＝v’

1＝(k

1)

1＝k，故

e＝v

1

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

⑶若T不連通，并且有k(k≥2)個連通分支T1,T2,…,Tk，因為每個分圖是連通無回路，則可證：如Ti

有vi

個結點vi＜v時，Ti

有vi

1

條邊，而

v＝v1

v2

…

vk e＝(v1

1)

(v2

1)

…

(vk

1)＝v

k

但 e＝v

1

故 k＝1

這與假設G是不連通的，即

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

⑷若T連通且有v

1條邊。

當v＝2時，e＝v

1＝1，故T必無回路。如增加一條邊，那么得到且僅得到一個回路。

設v＝k

1時命題成立。考察v＝k時的情況，因為T是連通的，e＝v

1。故每個結點u有

deg(u)≥1

可以證明至少有一結點u0，使

deg(u0)＝1

若不然，即所有結點u有deg(u)≥2，則2e≥2v，即e≥v

與假設e＝v

1

矛盾。 刪去u0

及其關聯的邊，而得到圖T′，由歸納假設得知T′無回路，在T′中加入u0

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

到uj

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

⑸若圖T不連通，則存在結點ui

與uj，ui

與uj

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

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

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

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

deg(Vi)≥1

且

(1)若T中每一個結點的度數大于等于2，則 得出矛盾。

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

12.2生成樹樹是一種具有優秀結構的、最經濟的圖。人們希望能很好地利用樹這種結構。一些連通圖雖然本身不是樹，但是根據樹的特性，人們想到連通圖的“最小連通生成子圖”應當是樹，其中，重要的一類是生成樹。

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

e2,e3,e7

是T的弦。{e2,e3,e7}是生成樹T的補。e3e1e6e4e5e2e7e8e1e6e4e5e8（a）（b）【例12.1】請找出下圖(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）由此可見，一個連通圖的生成樹不唯一。定理12.5任一連通圖都至少有一棵生成樹。證明：⑴設連通圖G沒有回路，則它本身就是一棵生成樹。 ⑵若G至少有一個回路，刪去回路上的一條邊，得到G1，它仍然是連通的，并與G有相同的結點集。 若G1

沒有回路，則G1

就是G的生成樹。 ⑶若G1

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

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

（2）G的任一邊割集與任一生成樹T至少有一條公共邊。證明：反證法。 （1）若有一條回路和一棵生成樹的補沒有公共邊，那么這回路包含在生成樹之中，然而這是不可能的，因為一棵生成樹不能包含回路。 （2）若有一條邊割集和一棵生成樹沒有公共邊，那么刪去這個邊割集后，所得的子圖必然包含該生成樹，這意味著刪去邊割集后仍然連通，與邊割集定義矛盾。定義12.3設G是具有n個結點的帶權連通圖。G的生成樹T的所有邊的權之和為樹的權。在圖G的所有生成樹中，樹權最小的那棵生成樹稱作最小生成樹。注意，帶權圖G的最小生成樹不唯一。7810（a）2025131425630301130418143097810（b）25131461130309帶權圖G和它的一個最小生成樹T

下面我們給出求帶權圖G的最小生成樹的Kruskal

算法。算法12.1(Kruskal)設圖G有n個結點，按以下步驟可以求得圖G的最小生成樹。 （1）按權值升序將圖G的邊排序，得到表L； （2）令； （3）在表L中依次選取下一條邊e，如果，且 構成的子圖是無圈圖，則令； （4）若，則算法停止，輸出集合S即為所求。否則，轉⑶，繼續遍歷表L。 可以證明，算法12.1求得的是圖G的最小生成樹。【例12.2】應用算法12.1求圖G的最小生成樹，G如圖(a)所示。求最小生成樹

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

v61214v5v4v1v7v3v2e1e6e4e7e2141解： （1）根據Kruskal

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

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

放入S中；邊e8,e9

被忽略，因為它們的加入會形成圈。 （4）此時S中有6條邊，滿足，所以算法結束。得到的最小生成樹T如圖(b)所示，樹權為10。

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

是最小權重邊，其中，，則令，； （3）若，算法停止，輸出。否則，轉⑵，繼續向樹中增加新結點。【例12.3】使用Prim算法求圖G的最小生成樹。解：不失一般性，選出結點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)）。這也說明一個圖的最小生成樹不唯一。12.3根樹、二叉樹及其應用本節之前，所討論的特殊圖都是無向圖。本節將討論一類有向圖，也是一類特殊的樹——根樹。12.3.1根樹定義12.4如果一個有向圖在不考慮邊的方向時是一棵樹，那么，這個有向圖稱為有向樹。 有向樹定義12.5一棵有向樹，如果恰有一個結點的入度為0，其余所有結點的入度都為1，則稱為根樹。入度為0的結點稱為根，出度為0的結點稱為葉子，出度不為0的結點稱為分支點或內點。根樹右圖表示一棵根樹，其中，V0

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

為葉子，V1,V2,V6,V7

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

的“父親”，v1,v2,v3

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

的祖先，它們是v0

的“后裔”；v1,v2,v3

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

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

的層次是2，v9,v10

的層次是3。在許多情況下，需要對根樹中同一父親的兒子規定某種順序。定義12.7如果根樹T為每個父親結點的兒子結點規定了次序，則稱T為有序樹。通常默認的順序為從左到右。

根據根樹的結構特點，根樹還可以遞歸定義為：定義12.8樹T稱為根樹，如果：

（1）T為一個孤立結點v0，v0又被稱為T的樹根；

（2）T1…Tk

為以v1…vk

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

及與v1…vk

相鄰的結點v0

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

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

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

（b）轉換第一步

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

DBCAJHEFKIGDBCAJHEFKIG（b）轉換第一步

（c）與(a)對應的二叉樹

同樣地，此方法可以推廣到森林，將森林改寫為二叉樹。圖(a)所示的森林被轉換為圖(c)所示的二叉樹。DBCAJHEFKIGLM(a)DBCAJHEFKIGLM(b)DBCAJHEFKIGLM(c)完全二叉樹的一些性質。 定理12.7設完全m叉樹，有t片葉子、i個分支點，則。 證明：若把m叉樹當作是每局有m位選手參加比賽的單淘汰賽計劃表，樹葉數為t表示參加比賽的選手數，分枝點數為i表示比賽的局數，因為每局比賽將淘汰(m

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

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

1)i

1＝t即(m

1)i＝t

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

I，外部通路長度總和為E，則。證明：歸納法。對分枝點數目n進行歸納。 （1）當n＝1時，E＝2，I＝0，故

E＝I

2n 成立。 （2）假設n＝k

1時成立，即

E’＝I’

2(k

1)

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

1的樹葉和一個長度為l的分枝點，因為T’有(k

1)個分枝點，故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完全二叉樹的結點個數必定為奇數。 證明：完全二叉樹中，除樹根的度為2外，其它結點的度均為3或1，因此完全二叉樹的度數總和為n

1個奇數的和加上2。若n為偶數，則n

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

1

l個、度為3的分支結點，因此有：得為定理12.11設完全二叉樹有n個結點，則完全二叉樹的高h滿足，其中[]表示取整運算，取不大于[]中的表達式值得最大整數。證明：先證，再證。

（1）如果高為h

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

，那么，該樹的結點數為 因此，對一般高為h的完全二叉樹而言，其結點數 即： 因此 故（2）如果高為h的完全二叉樹的每個分支結點的兩個兒子結點中必有一個是葉子，那么它的結點數應是(h

1)

h，而對一般高為h的完全二叉樹而言，其結 點數為 故

由⑴⑵可知，有n個結點的完全二叉樹其樹高h滿足算法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】請用前序、中序和后序遍歷算法遍歷圖中所示的二叉樹。解： ⑴前序遍歷結果：； ⑵中序遍歷結果：； ⑶后序遍歷結果：DBCAJHFKIG二叉樹的遍歷

E12.3.3應用舉例 二叉樹的第一個應用就是最優樹。 定義12.11設二叉樹T有t片葉子，分別帶權為w1,w2,…,wt，則T稱為帶權二叉樹。如果T中帶權wi

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

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

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

和wy，故有

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

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

與w1

對調，得到新樹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是最優樹的假定矛盾。故 L(wx)＝

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

L(w2)因此 L(w1)＝

L(w2)＝

L(wx)＝

L(wy)分別將w1，w2

與wx，wy

對調，得到一棵最優樹，其中帶權w1

和w2

的樹葉是兄弟。

定理12.13設T是帶權的最優樹。如果將帶權w1,w2的葉子的父結點由分支點改為帶權的葉子結點，得到一棵新樹T，則T也是最優樹。證明：根據題設，有 w(T)＝w(T’)

w1

w2

若T’不是最優樹，則必有另外一棵帶權為 w1

w2，w3，…，wt的最優樹T”。 對T”中帶權為w1

w2的樹葉vw1

w2生成兩個兒子，得到樹，則

w()＝w(T”)

w1

w2

因為T”是帶權為w1

w2，w3，…，wt

的最優樹,

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

與T是帶權為w1，w2，…，wt

最優樹矛盾，因此

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

w2，w3，…，wt

的最優樹。根據上述定理，1952年，D.A.Huffman

給出求最優二叉樹的算法。根據上面兩個定理，要畫一棵帶有t個權的最優樹，可簡化為畫一棵帶有t

1個權的最優樹，而又可簡化為畫一棵帶t

2個權的最優樹，依此類推。具體的做法是：首先找出兩個最小w值，設為w1

和w2，然后對t

1個權w1

w2,w3,…,wt求作一棵最優樹，并且將這棵最優樹的結點vw1

w2

分叉生成兩個兒子v1

和v2，依此類推。23571113171923293137415571113171923293137411071113171923293137411711131719232931374117241719232931374124341923293137412434422931374134425331374142536537414253657895657895143

238【例12.5】設一組權2,3,5,7,11,13,17,19,23,29,31,37,41。求相應的最優樹。解：求最優樹的過程可描述為：最優樹

二叉樹的另一個應用是前綴碼。在遠距離通訊中，常常用0和1的字符串作為英文字母傳送信息，因為英文字母共有26個，故用不等長的二進制序列表示26個英文字母時，由于長度為1的序列有2個，長度為2的二進制序列有2