離散數(shù)學(xué)講義鄭版watched08圖論有向樹(shù)

主要內(nèi)容有向樹(shù)最優(yōu)樹(shù)圖

論有且僅有一個(gè)結(jié)點(diǎn)稱為樹(shù)根，其引入次數(shù)是0；除樹(shù)根外每一結(jié)點(diǎn)的引入次數(shù)是1；樹(shù)的每一結(jié)點(diǎn)a，都有從樹(shù)根到a的一條有向路徑。有向樹(shù)也稱為根樹(shù)。通常表示為樹(shù)根在上，所有弧向下，弧的箭頭略去的圖。圖

論有向樹(shù)是結(jié)點(diǎn)集合非空的，符合以下三條要求的有向圖：有向樹(shù)最優(yōu)樹(shù)圖

論設(shè)a和b是有向樹(shù)T的結(jié)點(diǎn)，如果有一弧從a到b，則稱a是b的父親，而b是a的兒子。如果從結(jié)點(diǎn)a到結(jié)點(diǎn)b有一有向路徑，則稱a是b的祖先，而b是a的后裔。如果a≠b，則a是b的一個(gè)真祖先，而b是a的一個(gè)真后裔。由結(jié)點(diǎn)a和它的所有后裔導(dǎo)出的子有向圖稱為T的子樹(shù)，a稱為子樹(shù)的樹(shù)根。如果a不是T的樹(shù)根，則該子樹(shù)是T的真子樹(shù)。引出次數(shù)是0的結(jié)點(diǎn)稱為樹(shù)的葉；一個(gè)結(jié)點(diǎn)若不是葉，則稱為內(nèi)部結(jié)點(diǎn)（或分枝點(diǎn)）。從樹(shù)根r到一結(jié)點(diǎn)a的路徑長(zhǎng)度（邊的條數(shù)）稱為a的路徑長(zhǎng)度，也稱為a的層次。樹(shù)T中層次的最大值稱為樹(shù)T的高度。樹(shù)根是a；有三個(gè)兒子

b,c,d；c沒(méi)有兒子。e的父親是b，真祖先是

a和b。樹(shù)的葉是c,e,f,g,i,ja,b,d,h是內(nèi)部結(jié)點(diǎn)。樹(shù)的高度是3。具有結(jié)點(diǎn)集{b,e,f,g}的子有向圖是樹(shù)根為b的子樹(shù)。abcedf

g

hij圖

論有向樹(shù)最優(yōu)樹(shù)設(shè)T是一棵有向樹(shù)，根是r，并設(shè)a是T的任一結(jié)點(diǎn)，則從r到a有唯一的有向路徑。有向樹(shù)中的每一有向路徑是基本路徑。有向樹(shù)沒(méi)有非零長(zhǎng)度的任何回路。有向樹(shù)中，m=n-1，m是邊數(shù)，n是結(jié)點(diǎn)數(shù)。有向樹(shù)的子樹(shù)是有向樹(shù)。圖

論有向樹(shù)最優(yōu)樹(shù)（遞歸定義）有向樹(shù)包含一個(gè)或多個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)中某一個(gè)稱為樹(shù)根，其它所有結(jié)點(diǎn)被分成有限個(gè)子有向樹(shù)。把n個(gè)結(jié)點(diǎn)的有向樹(shù)用結(jié)點(diǎn)數(shù)少于n的有向樹(shù)來(lái)定義，最后得到每一棵都是僅有一個(gè)結(jié)點(diǎn)的有向樹(shù)，它們就是原來(lái)那棵樹(shù)的葉。（括號(hào)表示）設(shè)有向樹(shù)T：如果T只有一個(gè)結(jié)點(diǎn)，則此結(jié)點(diǎn)就是它的括號(hào)表示。如果T由根r和子樹(shù)T1，T2，…，Tn組成，則T的括號(hào)表示為：根r，左括號(hào)，T1，T2，…，Tn的括號(hào)表示（兩子樹(shù)之間用逗號(hào)分開(kāi)），右括號(hào)。圖

論有向樹(shù)最優(yōu)樹(shù)abcd

e

f括號(hào)表示為a括號(hào)表示為a[b[d,e,f],c]括號(hào)表示為a[b,c[e,f[g,h]],d]acdegfbha圖

論有向樹(shù)最優(yōu)樹(shù)三元樹(shù)，但不是完全三元樹(shù)完全三元樹(shù)圖

論在樹(shù)T中，如果每一結(jié)點(diǎn)的兒子個(gè)數(shù)是n個(gè)或少于

n個(gè)，則稱此樹(shù)為n元樹(shù)。如果每一結(jié)點(diǎn)或有n個(gè)兒子或沒(méi)有兒子，則稱此樹(shù)為完全n元樹(shù)（或稱為正則n元樹(shù)）。圖

論設(shè)有完全n元樹(shù)G，其樹(shù)葉數(shù)為t，分枝點(diǎn)數(shù)為i，則(n-1)i=t-1證明：設(shè)圖G有v個(gè)結(jié)點(diǎn)，e條邊，則e＝v－1，而v＝t＋i，e＝n·i，則n·i＝t＋i－1，所以(n－1)i＝t－1。例：設(shè)有28盞電燈，擬公用一個(gè)電源插座，問(wèn)需要多少塊具有四插座的接線板。解：將四元樹(shù)的每個(gè)分枝點(diǎn)看作是具有四插座的接線板，樹(shù)葉看作電燈，則有(4-1)i=28-1，i=9，所以9塊具有四插座的接線板。例：M和E兩人進(jìn)行網(wǎng)球比賽，如果一人連勝兩盤或共勝三盤就獲勝，比賽結(jié)束。則可用二元樹(shù)表示比賽可能進(jìn)行的所有情況。從樹(shù)根到樹(shù)葉的每一條路徑對(duì)應(yīng)比賽中可能發(fā)生的一種情況。EMEMEMEM

EMEMEMEM

EM圖

論圖

論如果從每一結(jié)點(diǎn)引出的邊都給定一個(gè)次序，或者等價(jià)的給結(jié)點(diǎn)的每一兒子編序，稱它們?yōu)槟辰Y(jié)點(diǎn)的第一、第二、…、第n個(gè)兒子。樹(shù)中每一結(jié)點(diǎn)引出的邊都規(guī)定次序的樹(shù)，稱為有序樹(shù)。一般自左至右的排列，左兄右弟。如果樹(shù)中每一結(jié)點(diǎn)的兒子不僅給出次序，還明確它們的位置，則此樹(shù)稱為位置樹(shù)。二元位置樹(shù)每個(gè)結(jié)點(diǎn)的兒子，都被指明左兒子或右兒子。一個(gè)有向圖，如果它的每個(gè)連通分圖是有向樹(shù)，則稱該有向圖為（有向）森林；在森林中，如果所有樹(shù)都是有序樹(shù)且給樹(shù)指定了次序，則稱此森林是有序森林。不是相等的有序樹(shù)b

cbccc不是相等的位置樹(shù)，上圖c是左兒子，下圖c是右兒子，是相等的有序樹(shù)。圖

論圖

論有序樹(shù)轉(zhuǎn)化成二元位置樹(shù)：方法一：除了最左邊的分枝點(diǎn)外，刪去所有從每一個(gè)結(jié)點(diǎn)長(zhǎng)出的分枝。在同一層次中，兄弟結(jié)點(diǎn)之間用從左到右的有向邊連接。方法二：選定二元樹(shù)的左兒子和右兒子如下：直接處于給定結(jié)點(diǎn)下面的結(jié)點(diǎn)，作為左兒子，對(duì)于同一水平線上與給定結(jié)點(diǎn)右鄰的結(jié)點(diǎn)，作為右兒子，以此類推/p>

1113245798610

11圖

論d/c+f/e-ab圖

論常用樹(shù)來(lái)表示離散結(jié)構(gòu)的層次關(guān)系，如可表示算術(shù)表達(dá)式。例：a-b+(c/d+e/f)+tw(T

)

=

wi

L(wi)i=1稱為該帶權(quán)二元樹(shù)的權(quán)。在所有帶權(quán)w1,w2,…,wt的二元樹(shù)中，w(T)最小的那棵樹(shù)，稱為最優(yōu)樹(shù)。圖

論給定一組權(quán)w1,w2,…,wt，不妨設(shè)w1≤w2≤…≤wt，設(shè)有一棵完全二元樹(shù)，共有t片樹(shù)葉，分別帶權(quán)w1,w2,…,wt，該二元樹(shù)稱為帶權(quán)二元樹(shù)。在帶權(quán)二元樹(shù)中，若帶權(quán)為wi的樹(shù)葉，其通路長(zhǎng)度為L(zhǎng)(wi)，把圖

論設(shè)T為帶權(quán)w1≤w2≤…≤wt的最優(yōu)樹(shù)，則帶權(quán)w1，w2的樹(shù)葉vw1，vw2是兄弟；以樹(shù)葉vw1，vw2為兒子的分枝點(diǎn)是通路長(zhǎng)度最長(zhǎng)（層次最大）的分枝點(diǎn)。證明：設(shè)在帶權(quán)w1,w2,…,wt的最優(yōu)樹(shù)中，v是通路長(zhǎng)度最長(zhǎng)的分枝點(diǎn)，

v的兒子分別帶權(quán)wx和wy，故有L(wx)=L(wy)，L(wx)≥L(w1)，L(wy)≥L(w2)。若L(wx)>L(w1)，將wx和w1對(duì)調(diào)，得到新樹(shù)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)樹(shù)的假設(shè)矛盾。故L(wx)=L(w1)。圖

論設(shè)T為帶權(quán)w1≤w2≤…≤wt的最優(yōu)樹(shù)，則帶權(quán)w1，w2的樹(shù)葉vw1，vw2是兄弟；以樹(shù)葉vw1，vw2為兒子的分枝點(diǎn)是通路長(zhǎng)度最長(zhǎng)（層次最大）的分枝點(diǎn)。證明：同理可證，L(wy)=L(w2)。因此L(w1)=L(w2)=L(wx)=L(wy)，分別將w1，w2與wx，wy對(duì)調(diào)得到一棵最優(yōu)樹(shù)，其中帶權(quán)w1和w2的樹(shù)葉是兄弟，且以樹(shù)葉vw1，vw2為兒子的分枝點(diǎn)是通路長(zhǎng)度最長(zhǎng)的分枝

點(diǎn)。圖

論設(shè)T為帶權(quán)w1≤w2≤…≤wt的最優(yōu)樹(shù)，若將以帶權(quán)w1和w2的樹(shù)葉為兒子的分枝點(diǎn)改為帶權(quán)w1+w2的樹(shù)葉，得到一棵新樹(shù)T’，則T’也是最優(yōu)樹(shù)。證明：由已知條件有w(T)=w(T’)+w1+w2，若T’不是最優(yōu)樹(shù)，則必有另一棵帶權(quán)w1+w2,w3,…,wt的最優(yōu)樹(shù)T’’。對(duì)T’’中帶權(quán)w1+w2的樹(shù)葉vw1+w2生成兩個(gè)兒子，得到新樹(shù)T’’’，則w(T’’’)=w(T’’)+w1+w2，因?yàn)門’’是帶權(quán)w1+w2,w3,…,wt的最優(yōu)樹(shù)，故w(T’’)≤w(T’)。如果w(T’’)<w(T’)，則

w(T’’’)<w(T)，與T是帶權(quán)w1,w2,…,wt的最優(yōu)樹(shù)的假設(shè)矛盾，因此w(T’’)＝w(T’)，所以T’是帶權(quán)w1+w2,w3,…,wt的最優(yōu)

樹(shù)。w1+w2w1w2圖

論于是，要畫一棵帶有t個(gè)權(quán)的最優(yōu)樹(shù)，可簡(jiǎn)化為畫一棵帶有t-1個(gè)權(quán)的最優(yōu)樹(shù)，而這又可簡(jiǎn)化為畫一棵帶有t-2個(gè)權(quán)的最優(yōu)樹(shù)，依此類推。具體做法：首先找出兩個(gè)最小的w值，設(shè)為w1和w2，然后對(duì)t-1個(gè)權(quán)w1+w2，w3，…，wt，作一棵最優(yōu)樹(shù)，并將這棵最優(yōu)樹(shù)中的結(jié)點(diǎn)代之以

，依此類推。34561271118圖

論例：設(shè)有一組權(quán)3,4,5,6,12,求相應(yīng)的最優(yōu)樹(shù)。30圖

論給定一個(gè)序列的集合，若沒(méi)有一個(gè)序列是另一個(gè)序列的前綴，該序列集合稱為前綴碼。例：{000,001,01,10,110}是前綴碼，{1,0001,000}不是。任意一棵二元樹(shù)的樹(shù)葉可對(duì)應(yīng)一個(gè)前綴碼。證明：給定一棵二元樹(shù)，從每一個(gè)分枝點(diǎn)引出兩條邊，對(duì)左側(cè)邊標(biāo)以0，對(duì)右側(cè)邊標(biāo)以1，則每片樹(shù)葉將可標(biāo)定一個(gè)0和1的序列，它是由樹(shù)根到這片樹(shù)葉的通路上各邊標(biāo)號(hào)所組成的序列，顯然，沒(méi)有一片樹(shù)葉的標(biāo)定序列是另一片樹(shù)葉標(biāo)定序列的前綴，所以，任何一棵二元樹(shù)的樹(shù)葉可對(duì)應(yīng)一個(gè)前綴碼。圖

論任何一個(gè)前綴碼都對(duì)應(yīng)一棵二元樹(shù)。證明：設(shè)給定一個(gè)前綴碼，h表示前綴碼中最長(zhǎng)序列的長(zhǎng)度。可以畫出一棵高度為h的完全二元樹(shù)，并給每一分枝點(diǎn)射出的兩條邊標(biāo)以0和1，這樣，每個(gè)結(jié)點(diǎn)可以標(biāo)定一個(gè)二進(jìn)制序列，它是由樹(shù)根到該結(jié)點(diǎn)通路上各邊的標(biāo)號(hào)所確定，因此，對(duì)于長(zhǎng)度不超過(guò)h的每一二進(jìn)制序列必對(duì)應(yīng)一個(gè)結(jié)點(diǎn)。對(duì)應(yīng)于前綴碼中的每一序列的結(jié)點(diǎn)，給予一個(gè)標(biāo)記，并將標(biāo)記結(jié)點(diǎn)的所有后裔和射出的邊全部刪去，這樣得到一棵二元樹(shù)，再刪去其中未加標(biāo)記的樹(shù)葉，得到一棵新的二元樹(shù)，它的樹(shù)葉就對(duì)應(yīng)給定的前綴碼。00001

0

1

0

1

0111001例：前綴碼{000,001,01,1}對(duì)應(yīng)的完全二元樹(shù)。1

011對(duì)二進(jìn)制序列00010011011101001，譯碼為000，1，001，1，01，1，1，01，001圖

論于是，26個(gè)英文字母的變長(zhǎng)編碼問(wèn)題，可以根據(jù)各字母的使用幾率p1,p2,…p26，構(gòu)造一棵具有權(quán)值p1,p2,…p26的最優(yōu)樹(shù)，按前述方法即可獲得其前綴碼。圖

論圖

論二元搜索樹(shù)：每一結(jié)點(diǎn)代表一個(gè)記錄，假定每一記錄的鍵值都不相同。每一結(jié)點(diǎn)的鍵值大于其左子樹(shù)中的所有結(jié)點(diǎn)的鍵值，而小于其右子樹(shù)中所有結(jié)點(diǎn)的鍵值。搜索過(guò)程：如果要找的記錄的鍵值是A，則把A和根結(jié)點(diǎn)的鍵值K比較，如果相等，則表示已找到；如果A<K，則轉(zhuǎn)到左子樹(shù)，若左子樹(shù)不存在，說(shuō)明沒(méi)有該記錄；如果A>K，則轉(zhuǎn)到右子樹(shù)，若右子樹(shù)不存在，說(shuō)明沒(méi)有該記錄；轉(zhuǎn)到左(右)子樹(shù)后，對(duì)其重復(fù)上述過(guò)程。二元搜索樹(shù)的遍歷(周游)：按照根結(jié)點(diǎn)被處理的先后不同，分別稱為前序、中序、后序遍歷算法。假設(shè)二元樹(shù)的根為r，左子樹(shù)為T1，右子樹(shù)為T2，前序：a處理T的根結(jié)點(diǎn)r；如果T1存在，前序遍歷T1；如果T2存在，前序遍歷T2。bdcefghjika

b

d

e

h

i

c

f

j

k

g圖

論假設(shè)二元樹(shù)的根為r，左子樹(shù)為T1，右子樹(shù)為T2，中序：a如果T1存在，中序遍歷T1；處理T的根結(jié)點(diǎn)r；如果T2存在，中序遍歷T2。bdcefghjikd

b

h

e

i

a

f

k

j

c

g圖

論假設(shè)二元樹(shù)的根為r，左子樹(shù)為T1，右子樹(shù)為T2，后序：如果T1存在，后序遍歷T1；如果T2存在，后序遍歷T2。處理T的根結(jié)點(diǎn)r；adbcefghjikd

h

i

e

b

k

j

f

g

c

a圖

論圖

論三元樹(shù)做搜索樹(shù)時(shí)，記錄通常只存儲(chǔ)在葉結(jié)點(diǎn)上，而內(nèi)部結(jié)點(diǎn)只存儲(chǔ)兩個(gè)用作比較的值d1和d2，稱為鑒別子。如果要找的記錄鍵值為A，從根結(jié)點(diǎn)開(kāi)始，如果A<d1，轉(zhuǎn)根的左子樹(shù)，如果d1≤A<d2，轉(zhuǎn)根的中子樹(shù)，如果d2