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

第10章

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

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

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

，從而e

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

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

無回路，e

=n

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

得到圖T

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

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

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

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

設(shè)T是有n(n

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

解得x

2.實(shí)例例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)實(shí)例例10.1.3

已知無向樹T中,有1個(gè)3度頂點(diǎn),3個(gè)2度頂點(diǎn),其余結(jié)點(diǎn)全是樹葉.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是一棵樹時(shí)，G本身就是生成樹。當(dāng)連通圖G不是一棵樹時(shí)，G中有回路。對(duì)于G的一個(gè)回路，刪去回路上的一條邊，得到G的生成子圖G

。若G

仍有回路，繼續(xù)刪去其中一個(gè)回路上的一條邊。重復(fù)這個(gè)過程，直到得到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個(gè)，則算法結(jié)束，否則返回②。

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

對(duì)無向圖G，依次取邊(a，b)，(b，c)，(b，e)和(d，e)，就得到G的一棵生成樹，如上面右圖所示。例題例4對(duì)下圖的無向圖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的對(duì)應(yīng)于生成樹T由樹枝ei生成的基本割集，i=1,2,…,n-1，并稱這些割集的全體為G對(duì)應(yīng)T的基本割集組，稱n-1為G的割集秩，記作η(G)。樹枝a,b,c,d對(duì)應(yīng)的基本割集:Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,f

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

對(duì)應(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é)束時(shí)，T就是G的最小生成樹。實(shí)例例5求圖的一棵最小生成樹23W(T)=3810.3根樹10.3.1有向根樹和有序根數(shù)10.3.2有序根樹的遍歷2510.3.1有向根樹和有序根數(shù)定義10.3.1一個(gè)有向圖G，如果略去有向邊的方向所得無向圖為一棵無向樹，則稱G為有向樹。

有向根樹定義10.3.2一棵非平凡的有向樹，如果有一個(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)）。在根樹中，從樹根到任意結(jié)點(diǎn)vi只有唯一的一條簡(jiǎn)單路，這條路的長(zhǎng)度稱為vi的級(jí)(層)數(shù)。級(jí)數(shù)最大的結(jié)點(diǎn)的級(jí)數(shù)稱為樹的高度。

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

a是樹根

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

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

a,c,d,g是分支點(diǎn)

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

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

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

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

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

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

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

。證明

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

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

，因?yàn)閔是整數(shù)，所以有當(dāng)m

元樹的所有樹葉的高度都是h時(shí)，等號(hào)成立，即

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

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

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

有序根樹

左子樹

右子樹

3910.3.2有序根樹的遍歷

系統(tǒng)地訪問有序根樹的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)恰好訪問一次，進(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帶下劃線的是(子)樹根,一對(duì)括號(hào)內(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ù)運(yùn)算算式如下:將運(yùn)算符放在分支點(diǎn)上,數(shù)放在樹葉上,每個(gè)運(yùn)算符對(duì)它所在分支點(diǎn)的2棵子樹進(jìn)行運(yù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é)點(diǎn)的中序遍歷結(jié)果可存在二義性為了讓這樣的表達(dá)式無歧義，遇到運(yùn)算時(shí)，按中序遍歷算法得到的表達(dá)式要包含括號(hào)，括號(hào)中是子樹的表達(dá)式。波蘭符號(hào)法與逆波蘭符號(hào)法(續(xù))波蘭符號(hào)法(前綴符號(hào)法):按前序遍歷訪問,不加括號(hào).從右到左進(jìn)行,每個(gè)運(yùn)算符對(duì)其后面緊鄰兩個(gè)數(shù)進(jìn)行運(yùn)算.逆波蘭符號(hào)法(后綴符號(hào)法):按后序遍歷訪問,不加括號(hào).從左到右進(jìn)行,每個(gè)運(yùn)算符對(duì)前面緊鄰兩數(shù)運(yùn)算.43例2(續(xù))波蘭符號(hào)法逆波蘭符號(hào)法

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的子樹，最后用這兩個(gè)子樹分別作為左子樹和右子樹，以

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

（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為長(zhǎng)度為n的符號(hào)串，稱a1，a1a2，

，a1a2a3

an-1分別為符號(hào)串

的長(zhǎng)度為1，2，

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

1，

2，

，

m}為一個(gè)字符串集合，若對(duì)任意的

i，

j

B，i

j，

i，

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

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

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

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

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

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

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

標(biāo)記每一個(gè)前綴碼在這棵二元樹上對(duì)應(yīng)的一個(gè)結(jié)點(diǎn)。將對(duì)應(yīng)于前綴碼的每一個(gè)結(jié)點(diǎn)的所有后代結(jié)點(diǎn)及其關(guān)聯(lián)的邊都刪去；刪去沒有和任一前綴碼對(duì)應(yīng)的樹葉，得到前綴碼對(duì)應(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個(gè)權(quán)值w1、w2

、

…、wt

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