主要內容有向樹最優樹圖

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

論有向樹是結點集合非空的，符合以下三條要求的有向圖：有向樹最優樹圖

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

b,c,d；c沒有兒子。e的父親是b，真祖先是

a和b。樹的葉是c,e,f,g,i,ja,b,d,h是內部結點。樹的高度是3。具有結點集{b,e,f,g}的子有向圖是樹根為b的子樹。abcedf

g

hij圖

論有向樹最優樹設T是一棵有向樹，根是r，并設a是T的任一結點，則從r到a有唯一的有向路徑。有向樹中的每一有向路徑是基本路徑。有向樹沒有非零長度的任何回路。有向樹中，m=n-1，m是邊數，n是結點數。有向樹的子樹是有向樹。圖

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

論有向樹最優樹abcd

e

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

論有向樹最優樹三元樹，但不是完全三元樹完全三元樹圖

論在樹T中，如果每一結點的兒子個數是n個或少于

n個，則稱此樹為n元樹。如果每一結點或有n個兒子或沒有兒子，則稱此樹為完全n元樹（或稱為正則n元樹）。圖

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

EMEMEMEM

EM圖

論圖

論如果從每一結點引出的邊都給定一個次序，或者等價的給結點的每一兒子編序，稱它們為某結點的第一、第二、…、第n個兒子。樹中每一結點引出的邊都規定次序的樹，稱為有序樹。一般自左至右的排列，左兄右弟。如果樹中每一結點的兒子不僅給出次序，還明確它們的位置，則此樹稱為位置樹。二元位置樹每個結點的兒子，都被指明左兒子或右兒子。一個有向圖，如果它的每個連通分圖是有向樹，則稱該有向圖為（有向）森林；在森林中，如果所有樹都是有序樹且給樹指定了次序，則稱此森林是有序森林。不是相等的有序樹b

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

論圖

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

1113245798610

11圖

論d/c+f/e-ab圖

論常用樹來表示離散結構的層次關系，如可表示算術表達式。例：a-b+(c/d+e/f)+tw(T

)

=

wi

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

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

論設T為帶權w1≤w2≤…≤wt的最優樹，則帶權w1，w2的樹葉vw1，vw2是兄弟；以樹葉vw1，vw2為兒子的分枝點是通路長度最長（層次最大）的分枝點。證明：設在帶權w1,w2,…,wt的最優樹中，v是通路長度最長的分枝點，

v的兒子分別帶權wx和wy，故有L(wx)=L(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)。圖

論設T為帶權w1≤w2≤…≤wt的最優樹，則帶權w1，w2的樹葉vw1，vw2是兄弟；以樹葉vw1，vw2為兒子的分枝點是通路長度最長（層次最大）的分枝點。證明：同理可證，L(wy)=L(w2)。因此L(w1)=L(w2)=L(wx)=L(wy)，分別將w1，w2與wx，wy對調得到一棵最優樹，其中帶權w1和w2的樹葉是兄弟，且以樹葉vw1，vw2為兒子的分枝點是通路長度最長的分枝

點。圖

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

w(T’’’)<w(T)，與T是帶權w1,w2,…,wt的最優樹的假設矛盾，因此w(T’’)＝w(T’)，所以T’是帶權w1+w2,w3,…,wt的最優

樹。w1+w2w1w2圖

論于是，要畫一棵帶有t個權的最優樹，可簡化為畫一棵帶有t-1個權的最優樹，而這又可簡化為畫一棵帶有t-2個權的最優樹，依此類推。具體做法：首先找出兩個最小的w值，設為w1和w2，然后對t-1個權w1+w2，w3，…，wt，作一棵最優樹，并將這棵最優樹中的結點代之以

，依此類推。34561271118圖

論例：設有一組權3,4,5,6,12,求相應的最優樹。30圖

論給定一個序列的集合，若沒有一個序列是另一個序列的前綴，該序列集合稱為前綴碼。例：{000,001,01,10,110}是前綴碼，{1,0001,000}不是。任意一棵二元樹的樹葉可對應一個前綴碼。證明：給定一棵二元樹，從每一個分枝點引出兩條邊，對左側邊標以0，對右側邊標以1，則每片樹葉將可標定一個0和1的序列，它是由樹根到這片樹葉的通路上各邊標號所組成的序列，顯然，沒有一片樹葉的標定序列是另一片樹葉標定序列的前綴，所以，任何一棵二元樹的樹葉可對應一個前綴碼。圖

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

0

1

0

1

0111001例：前綴碼{000,001,01,1}對應的完全二元樹。1

011對二進制序列00010011011101001，譯碼為000，1，001，1，01，1，1，01，001圖

論于是，26個英文字母的變長編碼問題，可以根據各字母的使用幾率p1,p2,…p26，構造一棵具有權值p1,p2,…p26的最優樹，按前述方法即可獲得其前綴碼。圖

論圖

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

b

d

e

h

i

c

f

j

k

g圖

論假設二元樹的根為r，左子樹為T1，右子樹為T2，中序：a如果T1存在，中序遍歷T1；處理T的根結點r；如果T2存在，中序遍歷T2。bdcefghjikd

b

h

e

i

a

f

k

j

c

g圖

論假設二元樹的根為r，左子樹為T1，右子樹為T2，后序：如果T1存在，后序遍歷T1；如果T2存在，后序遍歷T2。處理T的根結點r；adbcefghjikd

h

i

e

b

k

j

f

g

c

a圖

論圖

論三元樹做搜索樹時，記錄通常只存儲在葉結點上，而內部結點只存儲兩個用作比較的值d1和d2，稱為鑒別子。如果要找的記錄鍵值為A，從根結點開始，如果A<d1，轉根的左子樹，如果d1≤A<d2，轉根的中子樹，如果d2