離散數(shù)學(xué)及其應(yīng)用-第2版 課件 第10章樹

第10章

樹2第10章樹10.1樹的定義和特性 10.2生成樹 10.3根樹 10.4根樹的應(yīng)用10.1樹的定義和特性定義10.1.1

一個連通且無回路的無向圖稱為無向樹。樹中的邊稱為樹枝。度數(shù)為1的結(jié)點稱為樹葉。度數(shù)大于1的結(jié)點稱為分支點(內(nèi)點)。平凡圖稱為平凡樹。定義10.1.2一個不連通的，但每個連通分支都是無向樹的圖稱為森林。例如(a)(b)無向樹的性質(zhì)定理10.1.1對于有n個結(jié)點，e條邊的無向樹T，下列的命題等價。(1)T是無回路的連通圖。(2)T是連通的但刪去任一邊后,便不連通。(3)T是連通的且e=n-1。(4)T中無回路且e=n-1。(5)在T的每一對結(jié)點之間有唯一的一條簡單路。(6)T中無回路,但在任意兩個結(jié)點間增加一條邊,得到一條且僅一條回路。4定理10.1.1的證明(1)(2)。用反證法證。對u,vV，若T中刪去任一邊（u，v）后仍連通，則從u到v存在一條通路L，這條通路L加上（u，v）后形成回路，和T無回路矛盾。(2)(3)。對結(jié)點個數(shù)n用數(shù)學(xué)歸納法來證明e=n-1：當(dāng)結(jié)點數(shù)為n=1時，T是平凡圖，結(jié)論顯然成立。當(dāng)結(jié)點數(shù)為n=2時，T是連通的但刪去任一邊后,便不連通，則e=1，結(jié)論成立。假設(shè)結(jié)點數(shù)為nk（k>1）時，結(jié)論成立。當(dāng)結(jié)點數(shù)為n=k+1時，只有刪去T中的一個1度結(jié)點及其關(guān)聯(lián)的邊的圖T，才滿足命題（2）的連通性。根據(jù)歸納假設(shè)，T有k個結(jié)點，所以e=n-1，而e=e-1，n=n-1。因此，將刪去的1度結(jié)點及其關(guān)聯(lián)的邊添入T得到圖T，T仍連通且e=n-1。5定理10.1.1的證明(續(xù))（3）

（4）。對結(jié)點個數(shù)n用數(shù)學(xué)歸納法來證明T是無回路的：當(dāng)結(jié)點數(shù)為2時，e=1，T中無回路，即結(jié)論成立。假設(shè)結(jié)點數(shù)為n=k-1時無回路，e=n-1，結(jié)論成立。當(dāng)結(jié)點數(shù)為n=k時，因為T是連通的，故T中每一個節(jié)點的度數(shù)均大于等于1.可以證明至少有一個結(jié)點v0，使得deg(v0)=1。因為若所有結(jié)點的度數(shù)均大于等于2，則

，從而e

k,，即圖T至少有k條邊，與e=n-1矛盾。在T中刪去1度結(jié)點v0及其關(guān)聯(lián)的邊，得到新圖T

也是連通的。根據(jù)歸納假設(shè)，T

無回路，e

=n

-1，將刪去的1度結(jié)點v0及其關(guān)聯(lián)的邊添入T

得到圖T

，T中仍無回路，且e=n-1。（4）

（5）。用反證法證明。假設(shè)在T的每一對結(jié)點之間的簡單路不唯一，若結(jié)點u,v之間存在兩條簡單路，這兩條簡單路構(gòu)成回路，和T中無回路矛盾，所以在T的每一對結(jié)點之間有唯一的一條簡單路。6定理10.1.1的證明(續(xù))（5）

（6）。首先用反證法證明T中無回路。假設(shè)T中有回路，設(shè)C是一條包含邊（u，v）的簡單回路，在C中刪去邊（u，v）得到從u到v的一條簡單通路，因而從u到v的簡單通路不唯一，與命題（5）矛盾。若在T的任意兩個不鄰接的結(jié)點間加上一條邊e，則e和聯(lián)接這兩個結(jié)點的唯一一條簡單路構(gòu)成T+e的唯一的一條回路。（6）

（1）。根據(jù)命題（6）,任意兩個結(jié)點間存在一條通路，所以T是連通的，結(jié)論成立。7無向樹的性質(zhì)(續(xù))定理10.1.2

設(shè)T是有n(n

2)個結(jié)點的一棵樹,則T中至少有兩片樹葉。8證設(shè)有x片樹葉,由握手定理和定理10.1.1,有

解得x

2.實例例10.1.2

畫出所有6階非同構(gòu)的無向樹。9解5條邊,總度數(shù)等于10可能的度數(shù)列:(1)1,1,1,1,1,5(2)1,1,1,1,2,4(3)1,1,1,1,3,3(4)1,1,1,2,2,3(5)1,1,2,2,2,2(1)(2)(3)(4a)(4b)(5)實例例10.1.3

已知無向樹T中,有1個3度頂點,3個2度頂點,其余結(jié)點全是樹葉.T中有多少樹葉？畫出滿足要求的非同構(gòu)的無向樹.10解設(shè)有x片樹葉,2

(1+3+x-1)=1

3+3

2+x解得x=3，故T有3片樹葉.T的度數(shù)列為1,1,1,2,2,2,3生成樹定義10.2.1給定連通圖G,如果它的生成子圖TG是樹,則稱TG為G的生成樹。生成樹TG中的邊稱為樹枝；G中的不在TG中的邊稱為弦；TG的所有弦的集合稱為生成樹TG的余樹。11例如圖中黑邊構(gòu)成生成樹紅邊構(gòu)成余樹注意:余樹一般不是樹例題例10.2.1

在圖10.2.1中，哪些是圖10.2.1(1)的生成樹？

（1）(2)(3)

(4)(5)（6）解

（2）（5）是（1）的生成樹。（3）(4)（6）不是（1）的生成樹。生成樹的存在性定理10.2.1圖G有生成樹，當(dāng)且僅當(dāng)G是連通的。證明(破圈法)首先證明充分性。當(dāng)圖G是連通的，如果圖G是一棵樹時，G本身就是生成樹。當(dāng)連通圖G不是一棵樹時，G中有回路。對于G的一個回路，刪去回路上的一條邊，得到G的生成子圖G

。若G

仍有回路，繼續(xù)刪去其中一個回路上的一條邊。重復(fù)這個過程，直到得到G的生成子圖中沒有回路，從而得到G的一棵生成樹TG。證明必要性。若圖G有生成樹，由于樹是連通的，所以G是連通的。13求生成樹求生成樹的避圈法：設(shè)圖G=（V，E），|V|=n，E={e1，e2，

，em}，

任取一條邊e

E，令TG={e}；任取一條邊e

E-TG，若TG

{e}無回路，則把e添加到TG中；若TG中的元素有n-1個，則算法結(jié)束，否則返回②。

當(dāng)把n-1條邊加入TG時，TG就是圖G的生成樹。例題例3如下圖所示的無向圖G，用避圈法求生成樹.==》解

對無向圖G，依次取邊(a，b)，(b，c)，(b，e)和(d，e)，就得到G的一棵生成樹，如上面右圖所示。例題例4對下圖的無向圖G，用破圈法求生成樹。解

依次在圖G中刪去邊（a，d），（d，e），（b，c），如（1）(2)(3)所示，使得圖G沒有回路，就得到G的一棵生成樹。

（1）（2）（3）基本割集定義10.2.2

設(shè)T是n階連通圖G的一棵生成樹，e1,e2,…,en-1為T

的樹枝，Sei是G的只含樹枝ei的割集，則稱Sei為G的對應(yīng)于生成樹T由樹枝ei生成的基本割集，i=1,2,…,n-1，并稱這些割集的全體為G對應(yīng)T的基本割集組，稱n-1為G的割集秩，記作η(G)。樹枝a,b,c,d對應(yīng)的基本割集:Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,f

g},Sd={d,g},{Sa,Sb,Sc,Sd}為G

對應(yīng)T

的基本割集組，割集秩η(G)=4.基本回路

樹的基本變換

定理

10.2.2最小生成樹及其應(yīng)用定義10.2.2設(shè)無向連通帶權(quán)圖G=(V,E,W)，T是G的一棵生成樹，T各邊帶權(quán)之和稱為T的權(quán)，記作W(T)。G的所有生成樹中帶權(quán)最小的生成樹稱為最小生成樹。最小生成樹的典型算法有Kruskal算法、Prim算法和Sollin算法Kruskal算法Kruskal算法（基于避圈法思想）設(shè)G=（V,E,W）是n階連通帶權(quán)圖，(1)在邊集E中選一條具有最小權(quán)值的邊e，加入生成樹T中，并將e從邊集E中刪去。(2)在邊集E中選一條具有最小權(quán)值的邊e，若e和已在T中的邊不構(gòu)成回路，將e添加到T中，并從邊集E中刪去e；若e和已在T中的邊構(gòu)成回路，從邊集E中刪去e。(3)若T中的邊數(shù)為n-1，算法結(jié)束，否則返回（2）。算法結(jié)束時，T就是G的最小生成樹。實例例5求圖的一棵最小生成樹23W(T)=3810.3根樹10.3.1有向根樹和有序根數(shù)10.3.2有序根樹的遍歷2510.3.1有向根樹和有序根數(shù)定義10.3.1一個有向圖G，如果略去有向邊的方向所得無向圖為一棵無向樹，則稱G為有向樹。

有向根樹定義10.3.2一棵非平凡的有向樹，如果有一個結(jié)點的入度為0，其余結(jié)點的入度均為1，則稱此有向樹為有向根樹。稱入度為0的結(jié)點為樹根，稱出度為0的結(jié)點為樹葉，稱出度不為0的結(jié)點（含根）為分支點（內(nèi)點）。在根樹中，從樹根到任意結(jié)點vi只有唯一的一條簡單路，這條路的長度稱為vi的級(層)數(shù)。級數(shù)最大的結(jié)點的級數(shù)稱為樹的高度。

實例根樹的畫法:樹根放最上方,省去所有有向邊上的箭頭右圖中

a是樹根

b,e,f,h,i是樹葉

c,d,g是內(nèi)點

a,c,d,g是分支點

a為0層;1層有b,c;2層有d,e,f;3層有g(shù),h;4層有i.

樹高為42728有向根樹定義10.3.3在根樹T中，(1)若結(jié)點vi到結(jié)點vj可達(dá)，則稱vi是vj的祖先，vj是vi的后代；(2)若結(jié)點vi鄰接到結(jié)點vj，則稱vi是vj的父親，vj是vi的兒子；(3)若兩個節(jié)點同為一個結(jié)點的兒子，則稱這兩個結(jié)點為兄弟。定義10.3.4設(shè)T為一棵根樹，vi為T中一個結(jié)點，且vi不是樹根，稱vi及其后代的導(dǎo)出子圖為T的以vi為根的子樹，簡稱根子樹。m元樹定義10.3.5在根樹中，如果每個結(jié)點的出度小于或等于m，則稱這棵樹為m元樹。m=2時稱為二元樹或二叉樹。如果每個分支點的出度都等于m

，則稱這棵樹為m元正則樹。所有樹葉級(層)數(shù)相同的m元正則樹稱為完全m元正則樹。三元樹三元正則樹

完全二元正則樹定理10.3.1定理10.3.1有i個分支點的m元正則樹有n=mi+1個結(jié)點。證明

除根之外的每個結(jié)點都是分支點的兒子。因為每個分支點都有m個兒子，所以，在樹中除根之外還有mi個結(jié)點。因此，這棵樹共有mi+1個結(jié)點。定理10.3.2定理10.3.2一個m元正則樹T若T有n個結(jié)點，則有i=（n?1）/m個分支點和l=[(m?1)n+1]/m片樹葉；若T有i個分支點，則有n=mi+1個結(jié)點和l=(m?1)i+1片樹葉；若T有l(wèi)片樹葉，則有n=(ml?1)/(m?1)個結(jié)點和i=（l?1）/(m?1)個分支點。定理10.3.2證明

(1)若T有n個結(jié)點，利用定理10.3.1，n=mi+1，則分支點i=（n?1）/m，樹葉數(shù)l=n?i,將i的表達(dá)式代入l=n?i,得l=[(m?1)n+1]/m。(2)若T有i個分支點，利用定理10.3.1，有n=mi+1個結(jié)點；樹葉數(shù)l=n?i，將n的表達(dá)式代入得l=(m?1)i+1；(3)若T有l(wèi)片樹葉，i=n?l,代入n=mi+1，則有n=m(n?l)+1,整理得n=(ml?1)/(m?1)，而分支點數(shù)i=n?l=(ml?1)/(m?1)?l=（l?1）/(m?1)。例題例9.3.3假設(shè)有一條計算機(jī)加法指令，可計算3個數(shù)之和。如果要計算33個數(shù)x1,x2,...x33之和，則至少執(zhí)行幾次加法指令？解：將問題表示為根樹，有33片樹葉，執(zhí)行指令的結(jié)果為分支點，則問題為：求有33片樹葉的3元樹，有多少個分支點？由定理10.3.2可得:i=（l?1）/(m?1)=(33-1)/(3-1)=16即要執(zhí)行16次加法指令.定理10.3.3定理10.3.3在高度為h的m元樹里至多有mh片樹葉。證明

用歸納法對高度h進(jìn)行歸納證明。假設(shè)高度h=1。高度h=1的m元樹由根結(jié)點及其不超過m個子結(jié)點組成，每個子結(jié)點都是樹葉。因此高度為h的m元樹里至多有m1=m片樹葉。假設(shè)高度h=k-1時結(jié)論成立，即高度為k-1的m元樹里至多有mk-1片樹葉。高度h=k時，在高度為k-1的m元樹中給每片樹葉添加至多m個子結(jié)點，就是高度為k的m元樹，最多需要添加m(mk-1)=mk片樹葉。因此，高度h=k時，至多有mk片樹葉，結(jié)論成立。推論推論若一個高度為h的m元樹T有l(wèi)片樹葉，則

。證明

根據(jù)定理10.3.3，在高度為h的m元樹中，樹葉數(shù)l

mh，取以m為底的對數(shù)，得

，因為h是整數(shù)，所以有當(dāng)m

元樹的所有樹葉的高度都是h時，等號成立，即

例題例：t名選手參加象棋淘汰賽，每一場比賽的失敗者退出比賽，剩下的勝利者繼續(xù)比賽，直到剩下最后一名勝利者就是比賽的冠軍。假設(shè)比賽沒有平局，問共需進(jìn)行多少場比賽才能決出冠軍？解

在淘汰賽中，每一場比賽的失敗者退出比賽，剩下的勝利者繼續(xù)比賽，直到剩下最后一名勝利者就是比賽的冠軍。因此可以用二元正則樹來表示比賽過程。這棵樹有t片樹葉，每個分支點對應(yīng)一場比賽，根結(jié)點對應(yīng)冠軍賽。假設(shè)分支點有i個，根據(jù)定理10.3.2，有i=t?1，所以共需進(jìn)行t?1場比賽才能決出冠軍。有序根樹定義10.3.6如果將根樹每一層上的結(jié)點都規(guī)定次序，這樣的根樹稱為有序根樹。

在有序根樹中，每一層上的結(jié)點按從左到右的次序排序。如二元有序樹的一個分支點有兩個子結(jié)點，則從左到右稱這兩個子結(jié)點為左兒子和右兒子。以這兩個子結(jié)點為根所產(chǎn)生的根子樹分別稱為左子樹和右子樹。有序根樹

有序根樹

左子樹

右子樹

3910.3.2有序根樹的遍歷

系統(tǒng)地訪問有序根樹的每個結(jié)點，使得每個結(jié)點恰好訪問一次，進(jìn)行數(shù)據(jù)存取的過程稱為遍歷算法。三種遍歷2元有序根樹的算法：①前序遍歷算法:樹根、前序遍歷左子樹、前序遍歷右子樹②中序遍歷算法:中序遍歷左子樹、樹根、中序遍歷右子樹③后序遍歷算法:后序遍歷左子樹、后序遍歷右子樹、樹根例題例40中序遍歷:前序遍歷:后序遍歷:b

a((f

d

g)c

e)a

b(c(d

f

g)e)b((f

g

d)e

c)a帶下劃線的是(子)樹根,一對括號內(nèi)是一棵子樹例題例寫出用三種遍歷算法遍歷下列二元樹的結(jié)果。41前序遍歷:hdibjea

f

kcga

b

d

hie

jcfkghidjebkf

gca(1)(2)(3)(4)(5)(6)(8)(9)(7)(10)(11)中序遍歷:(1)(2)(3)(4)(5)(6)(8)(9)(7)(10)(11)(1)(3)(2)(6)(4)(5)(8)(7)(11)(10)(9)后序遍歷:2元有序根樹用2元有序根樹表示算術(shù)運算算式如下:將運算符放在分支點上,數(shù)放在樹葉上,每個運算符對它所在分支點的2棵子樹進(jìn)行運算,并規(guī)定左子樹是被除數(shù)或被減數(shù).42例2

右圖表示算式((b+(c+d))

a)

((e

f)

(g+h)

(i

j))前序遍歷

b+c

d

a

e

f

+g

h

i

j后序遍歷b

c

d++a

e

f

g

h+i

j

需要注意的是，結(jié)點的中序遍歷結(jié)果可存在二義性為了讓這樣的表達(dá)式無歧義，遇到運算時，按中序遍歷算法得到的表達(dá)式要包含括號，括號中是子樹的表達(dá)式。波蘭符號法與逆波蘭符號法(續(xù))波蘭符號法(前綴符號法):按前序遍歷訪問,不加括號.從右到左進(jìn)行,每個運算符對其后面緊鄰兩個數(shù)進(jìn)行運算.逆波蘭符號法(后綴符號法):按后序遍歷訪問,不加括號.從左到右進(jìn)行,每個運算符對前面緊鄰兩數(shù)運算.43例2(續(xù))波蘭符號法逆波蘭符號法

b+c

d

a

e

f

+g

h

i

j

b

c

d++a

e

f

g

h+i

j

例題例

用2元有序樹表示命題公式：

（p

q）

（p

q），寫出它的波蘭記法和逆波蘭記法。解

由底向上構(gòu)造二元有序樹。首先構(gòu)造p

q，p和

q的子樹，然后構(gòu)造

（p

q），p

q的子樹，最后用這兩個子樹分別作為左子樹和右子樹，以

為根結(jié)點的二元有序樹就是所求的表示命題公式：

（p

q）

（p

q）的有序樹。前序遍歷得波蘭記法：

pq

p

q后序遍歷得逆波蘭記法：pq

pq

10.4根樹的應(yīng)用10.4.1前綴碼10.4.2最優(yōu)二元樹和Huffman編碼10.4.3決策樹10.4.1前綴碼定義10.4.1設(shè)

=a1a2a3

an為長度為n的符號串，稱a1，a1a2，

，a1a2a3

an-1分別為符號串

的長度為1，2，

，n-1的前綴；設(shè)B={

1，

2，

，

m}為一個字符串集合，若對任意的

i，

j

B，i

j，

i，

j互不為前綴，則稱B為前綴碼；若

i（i=1，2，，m）中只有0，1兩個符號，則稱B為二元前綴碼。例如，{0，10，110，111}，{a,b,ca,cb,eda}都是二元前綴碼，而{1，01，010，110}不是前綴碼。前綴碼和二元樹定理10.4.1任何一棵二元樹的樹葉可對應(yīng)一個前綴碼。證明

對于給定的一棵二元樹，每個分支點至少有一個子結(jié)點，至多有兩個子結(jié)點。若分支點有兩個子結(jié)點，在分支點和左子結(jié)點連接的邊上標(biāo)0，和右子結(jié)點連接的邊上標(biāo)1；若分支點只有1個子結(jié)點，在分支點和它的子結(jié)點連接的邊上標(biāo)0或1都可以。

這樣，每片樹葉將對應(yīng)一個由0和1組成的序列，該序列由樹根到這片樹葉的通路上各邊的標(biāo)記組成。由于每片樹葉對應(yīng)的標(biāo)記序列都不是另一片樹葉標(biāo)記序列的前綴，因而由所有樹葉的標(biāo)記序列構(gòu)成一個前綴碼。例題

例前綴碼{00,11,011,0100}前綴碼和二元樹定理10.4.2任何一個前綴碼都對應(yīng)一棵二元樹。證明

設(shè)給定一個前綴碼，h表示前綴碼中最長序列的長度。畫出一棵高度為h的二元正則樹，在分支點和子結(jié)點連接的兩條邊上分別標(biāo)記0和1；

對長度不超過h的每一個二進(jìn)制序列必對應(yīng)這棵二元樹上的一個結(jié)點。將對應(yīng)于前綴碼的每一個結(jié)點的所有后代結(jié)點及其關(guān)聯(lián)的邊都刪去；最后再刪去沒有和任一前綴碼對應(yīng)的樹葉，得到一棵二元樹；這棵二元樹的樹葉就對應(yīng)給定的前綴碼。例題例1畫出前綴碼{00,10,010,111,1101}對應(yīng)的二元樹。解：畫出一棵高度為h的二元正則樹，在分支點和子結(jié)點連接的兩條邊上分別標(biāo)記0和1；000000111110100011101011000111例題例1畫出前綴碼{00,10,010,111,1101}對應(yīng)的二元樹。解：畫出一棵高度為h的二元正則樹，在分支點和子結(jié)點連接的兩條邊上分別標(biāo)記0和1；

標(biāo)記每一個前綴碼在這棵二元樹上對應(yīng)的一個結(jié)點。將對應(yīng)于前綴碼的每一個結(jié)點的所有后代結(jié)點及其關(guān)聯(lián)的邊都刪去；刪去沒有和任一前綴碼對應(yīng)的樹葉，得到前綴碼對應(yīng)的二元樹；000000111110100011101101000111000101011011115210.4.2最優(yōu)二元樹和Huffman編碼定義10.4.2設(shè)2元樹T有t片樹葉v1,v2,…,vt,樹葉的權(quán)分別為w1,w2,…,wt,稱為T的權(quán),記作W(T),其中l(wèi)(vi)是vi的層數(shù).在所有有t片樹葉,帶權(quán)w1,w2,…,wt的2元樹中,權(quán)最小的2元樹稱為最優(yōu)2元樹例如134561345613456W(T1)=47W(T2)=54W(T3)=4353求最優(yōu)2元樹的算法哈夫曼(Huffman)算法1）給定t個權(quán)值w1、w2

、

…、wt

，構(gòu)造t個結(jié)點分別對應(yīng)t個權(quán)值；