1、Ch1 哈夫曼樹一、基本概念1、路徑和路徑長度在一棵樹中，如果存在著一個結點序列k,k,k,使得k是k的父結點（lWiWj）,12jii+1則稱此結點序列是從k到k的路徑，因樹中每個結點只有一個父結點，所以它也是這兩個 1j結點之間的唯一路徑。從k到k所經過的分支數稱為這兩點之間的路徑長度，它等于路徑 1j上的結點數減1。2、結點的權和帶權路徑長度在許多應用中，常常將樹中的結點賦上一個有著某種意義的數，稱此數為該結點的權。 結點的帶權路徑長度定義為從樹根結點到該結點之間的路徑長度與該結點上權的乘積。3、樹的帶權路徑長度樹的帶權路徑長度（Weigh ted Path Leng th縮寫為WPL）

2、定義為樹中所有葉子結點的帶權路徑長度之和，通常記為：nWPL wliii=l其中的n表示葉子結點的數目，w和l分別表示葉子結點k的權值和根到k之間的路iiii徑長度。4、哈夫曼樹哈夫曼（Huffman）樹又稱為最優二叉樹，它是n個帶權葉子結點構成的所有二叉樹中, 帶權路徑長度WPL最小的二叉樹。因為構造這種樹的算法是最早由哈夫曼于1952年提出的, 所以稱為哈夫曼樹。例如，有四個葉子結點a、b、c、d,它們的權分別為9、4、5、2,由它們構成的三棵不同的二叉樹（當然還有其他許多種）分別如下圖（a）（c）所示。(a)(b)(c)(a)(b)(c)根據WPL的定義，每一棵二叉的帶權路徑長度WPL分

3、別為：WPL=9X 2+4X2+5X2+2X2=40WPL=4X 1+2 X 2+5 X 3+9 X 3=50WPL=9X 1+5X 2+4X 3+2X 3=37其中(c)樹的WPL最小，稍后就可以看出，這棵樹就是哈夫曼樹。由上面可以看出，由 n 個帶權葉子結點所構成的二叉樹中，滿二叉樹或完全二叉樹不一 定是最優二叉樹。權值越大的結點離根越近，這樣的二叉樹才是最優二叉樹。二、哈夫曼樹的構造假設有n個權值(w,w,w)，試構造一棵有n個葉子結點的二叉樹，每個葉子結點12n權值為w,則其中帶權路徑長度WPL最小的二叉樹就是“最優二叉樹或哈夫曼二叉樹”哈i夫曼二叉樹最主要的特點是，葉子的權越大就應該

4、越靠近根結點，權越小就應該越遠離根結 點，因此哈夫曼樹又稱為最優葉子二叉樹。如何構造哈夫曼二叉樹呢？ D A Huffman給出了一個簡單而又漂亮的算法，這個算法 稱為哈夫曼算法，它的基本思想就是讓權大的葉子離根最近，具體做法是： 根據給定的n個權值w,w,w ,構造n棵二叉樹的集合F=T ,T ,T ,其12n12n中每棵二叉樹中均只含一個帶權值為w的根結點，其左、右子樹為空樹；i在F中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新 的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；從F中刪去這兩棵樹，同時加入剛生成的新樹；重復(2)和(3)兩步，直

5、到F中只含一棵樹為止。從上述算法中可以看出，F實際上是森林，算法的目的是不斷地對森林中的二叉樹進行 “合并”，最終得到哈夫曼二叉樹。假定采用下圖(a)中的四個帶權葉子結點來構造一棵哈夫曼樹，按照上述算法，則構 造過程如下圖(a)至0(d)所示，其中(d)樹就是最后生成的哈夫曼樹，它的帶權路徑長度為 37。(d)(c)(d)(c)三、哈夫曼編碼哈夫曼樹的應用很廣，哈夫曼編碼就是其中的一種，下面給予簡要介紹。在電報通訊中，電文是以二進制的0、1 序列傳送的。在發送端需要將電文中的字符序 列轉換成二進制的0、1 序列（即編碼），在接收端又需要把接收到的0、1 序列轉換成對應 的字符序列（即譯碼）。最

6、簡單的二進制編碼方式是等長編碼，例如，假定電文中只使用A、B、C、D、E、F這 六種字符，若進行等長編碼，它們分別需要三位二進制字符，可以依次編碼為 000、 001、 010、 011、 100、 101。若用這六個字符作為六個葉子結點，來生成一棵二叉樹，讓該二叉樹 中每個分支結點的左、右分支分別用0和1編碼，從樹根結點到每個葉子結點的路徑上所經 過的分支的 0、 1 編碼序列應等于該葉子結點的二進制編碼，則對應的編碼二叉樹如下圖所 示。由常識可知，電文中每個字符出現的頻率一般是不同的。假定在一份電文中，這六個字 符出現的頻率依次為4、2、6、8、3、2,則電文經過編碼后的總長度L可以由下式

7、計算出 來：L =工cliii=1其中n表示電文中使用的字符種數，c和l分別表示對應字符k在電文中的出現頻率i i i和編碼長度。結合我們的例子，可以求出L為：L = f （c x 3） = 3 x （4 + 2 + 6 + 8 + 3 + 2） = 75i i=1可知，采用等長編碼時，傳送電文的總長度為75。如何通過縮短傳送電文的總長度，以節省傳送時間呢？如果采用不等長編碼，讓出現頻 率高的字符具有較短的編碼，讓出現頻率低的字符具有較長的編碼，這樣有可能縮短傳送電 文的總長度。采用不等長編碼要避免譯碼的二義性或多義性。假設用0表示字符D,用01 表示字符C,則當接收到編碼串01，并譯字符0時

8、，是立即譯出對應的字符D,還是與 下一個字符1一起譯為對應的字符C呢？這種情況下就會產生二義性了。因此，如果對某一 字符集進行不等長編碼，則要求字符集中任一字符的編碼都不能是其他字符編碼的前綴。符 合此要求的編碼叫做前綴編碼。顯然，等長編碼是前綴編碼，這從等長編碼所對應的編碼二 叉樹也可以直觀地看出，任一葉子結點都不可能是其他葉子結點的前驅，也就是說，只有當 一個結點是另一個結點的前驅時，該結點的字符編碼才會是另一個結點的字符編碼的前綴為了使不等長編碼為前綴編碼，可以用該字符集中的每個字符作為葉子結點生成一棵編 碼二叉樹。為了獲得傳送電文的最短長度，可以將每個字符的出現頻率作為字符結點的權值

9、賦予該結點上，求出此樹的最小帶權路徑長度就等于求出傳送電文的最短長度。因此，求傳 送電文的最短長度問題就轉化為求由字符集中的所有字符作為葉子結點，由字符的出現頻率 作為其權值所產生的哈夫曼樹的問題。根據上面所討論的例子，生成的哈夫曼樹如下圖所示，由編碼哈夫曼樹得到的字符編碼 稱為哈夫曼編碼。在下圖中，A、B、C、D、E、F這六個字符的哈夫曼編碼依次為：00、1110、 01、 10、 110、 1111。電文的最短傳送長度為：L 二 WPL = wliii 二14 x 2 + 2 x 4 + 6 x 2 + 8 x 2 + 3 x 3 + 2 x 4二 61顯然，這比等長編碼所得到的傳送總長度

10、75 要小得多。四、哈夫曼算法的實現 如何用程序實現哈夫曼算法呢？這與實際問題所采用的存儲結構有關，現假設用數組 F來存儲哈夫曼二叉樹，其中第i個數組元素Fi是哈夫曼二叉樹中的一個結點，其地址為i， 有3個域，Data域存放該結點的權值，lChild域和rChild域分別存放該結點左、右子樹的 根結點的地址（下標）。在初始狀態下：Fi.Data=W ；Fi.lChild=0；Fi.rChild=0 （i=1,2,n）i即先構造好n個葉子結點，以后每步構造一棵新的二叉樹時，都對森林中所有二叉樹的 根結點進行排序，因此可用數組a作為排序暫存空間，其中第i個數組元素ai是森林中 第i棵二叉樹的根結點

11、，有2個域，Data是根結點所對應的權值，Addr是根結點在F中的 地址（下標），在初始狀態下：ai.Data=W ；ai.Addr=i（i=1,2,n）i下面給出建立哈夫曼二叉樹的過程：Procedure createhfm（f, t,a,n）已知n個權值ai，構造哈夫曼樹f,且根結點地址為t Var i:Integer；BeginFor i:=1 To n Do Begin 初始化 fi.data:=ai.data； fi.lchild:=0； fi.rchild:=0； ai.addr:=iEnd；t:=n+1；t指向下一個可利用單元i:=n；當前森林中的二叉樹是iWhile i=2 D

12、o Begininsert（a,i） ； 對a的前i個元素按data域進行排序 f t.da ta:二al.da ta+a2.da ta； 生成新的二叉樹 ft.lchild:=a1.addr；ft.rchild:=a2.addr； a1.data:=ft.data； 修改森林 a1.addr:=t；a2.data:=ai.data； 修改森林 a2.addr:=ai.add；i:=i-1； 二叉樹數目減一 t:=t+1；End；End； 該算法是使用數組來建立二叉樹，使用指針鏈表來建立二叉樹的程序留給讀者完成。Ch2 排序二叉樹一、基本概念排序二叉樹（BST, Binary Sort Tre

13、e）或者是一棵空樹，或者是具有下列性質的二叉 樹：（1）若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；（2）若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；（ 3） 它的左、右子樹也分別為排序二叉樹。等價定義：若以中序遍歷排序二叉樹，則會產生一個所有結點關鍵字值的遞增序列。如：45/ 12 53 TOC o 1-5 h z / 3 37100/246190/78排序二叉樹又稱查找二叉樹，排序二叉樹是“排過序”的二叉樹，但并非是“用于排序” 的二叉樹。不難發現，排序二叉樹這種數據結構的優勢在于它的有序性，而且其插入和查找算法的 時間復雜度均為0 （h）, 般情況下h

14、=log2b n表示結點數，h表示樹的高度，這是其它類 似功能的數據結構無法達到的。比如有序線性表雖然有序，但是插入算法的時間復雜度為0（n）；堆的插入算法雖然時間復雜度為O（log2n）,但是堆并不具有有序性。因此，我們要充 分發揮排序二叉樹的優勢，就要充分利用其有序性和插入、查找算法的高效性。所以，如果 要經常對有序數列進行“動態”的插入或查找工作，就可以采用排序二叉樹。例如有這樣一道題目，大意是按照先后順序輸入一列人的身高（n個整數，n=104, 任意兩個人的身高不相同），只能相鄰的兩個人互換位置（比較身高），問最少用幾次交換可 以使隊伍從矮到高按升序排列？線性的方法很容易想到，即求出每

15、個人前有多少人比他高。因為，如果前面已經排好的 話，后面只要和比他高的人換就可以了,于是得到一個0（12）的算法。可是問題規模是104, 0（12）不可能對付得了，必需要使用0（nlog2n）的算法。于是，我們考慮使用排序二叉樹。令每一個節點有一個權值，指的是在此人前且比該人高的人數。如（2， 4， 1， 3）初始 時變成（2， 0），（4， 0），（1， 0），（3， 0），從第1個結點開始從前向后插入，每次若進 入右子樹，則將當前結點的權值加1，若進入左子樹，則將插入結點的權值變為當前結點的 權值加1。同時，用一個變量total記錄所有左孩子權值的總和。過程如下，開始時：（ 2， 0）to

16、tal=0，插入（4, 0），即：（2， 1）（4， 0）total=0,再插入（1, 0）,即：（2， 1）/ （1， 2）（4， 0）total=2，再插入（3, 0）,即：（2， 2）/ （1， 2）（4， 0）/（3， 1）total=3，所以最少用3次交換即可。大家可以用（1, 2, 3, 4, 5）、（5, 4, 3, 2, 1） 這些序列去試試，看看是否正確，為什么？二、存儲結構Type tree=node；node=Recordkey:integer； 關鍵值left,right,p:tree； 左孩子、右孩子、父結點也可以根據需要增加一些數據域End；Var bst:tree

17、;排序二叉樹看似簡單,且沒有太多的規則,其實它在題目中變化無常,所以要真正要用 好它,是需要下一番功夫的,首先要熟練掌握好它的各種基本操作,下面一一給出。三、輸出Procedure inorder_print(bst:tree)；遞歸中序輸出,從小到大BeginIf bstNil ThenBegininorder_pri nt(bst .lef t)；Write(bst.key, )； inorder_print(bst.right)；End；End；也可以用廣義表的形式輸出：procedure out(root:tree);begin write();if root.leftnil then

18、 out(root.left); write(root.key);if root.rightnil then out(root.right); write();end;四、査找關鍵字值為k的結點procedure search(x: tree,k:integer) ； 找到則返回關鍵字k的指針，沒找到則返回NIL beginif (x=nil) or (k= x.key) then exit(x);if k x.key then search(x.left,k)else search(x.right,k);end;也可以編寫一個高效的非遞歸算法，如下：function search(T:tre

19、e;k:integer):tree; beginwhile (Tnil) and (kT.key) dobeginif kT.key then T:= T.leftelse T:= T.right;end; search:=T;end;五、求最小(大)關鍵字值的結點 function min(x:tree):tree;beginwhile x.leftnil do x:= x.left; min:=x;end;function max（x:tree）:tree;beginwhile x.righ tnil do x:= x.righ t; max:=x;end;六、求一棵排序二叉樹中結點x,在

20、中序遍歷下的后繼（前趨）結點。如果結點X的右子樹非空，則x的后繼即右子樹中的最左（?。┙Y點，如下圖6的后繼如果結點X的右子樹為空，且X有后繼y,則y是X的最低的一個祖先結點，且y的左 兒子也是x的祖先。如上圖13的右子樹為空且有后繼，則后繼為13的父結點的父結點的父 結點，即15,因為15的左兒子6也是13的祖先，也就是要從下往上找某個結點y，它的左 孩子子是 x 的祖先。function succ(x:tree):tree;var y:tree;BeginIf x.righ tnil t hen begin x:二min(x.righ t);y :二x;end else beginy：= x

21、.p；While (y.pnil) and (x=y.righ t) doBegin x:=y;y:=y.p;end;end;succ:=y;End;如果結點x的左子樹非空，則x的前趨即左子樹中的最右（大）結點，如上圖15的前 趨為 13；如果結點x的左子樹為空，且x有前趨y,則y是x的最低的一個祖先結點，且y的右 兒子也是x的祖先。如上圖9的前趨為7,也就是要從下往上找某個結點y,它的右孩子是x 的祖先。其實，如果x是右孩子，則前趨就是x的父結點。function pred(x:tree):tree;var y:tree;BeginIf x.lef tnil t hen begin x:二m

22、ax(x.lef t);y :二x;end else beginy：= x.p；While (y.pnil) and (x=y.lef t) doBegin x:=y;y:=y.p;end;end;succ:=y;End;*定理1： 一棵高度為h的排序二叉樹，對它進行以上的輸出、査找、求最大（小）值、求 前趨和后繼的操作，時間復雜度都為 O（h）。七、插入把結點 z如把 14插入到上圖，從結果可以看出，只要從根結點開始不斷沿著樹枝下降即可。用 指針x跟蹤這條路徑，而y始終指向x的父結點。先令：z.key： =14； zleft：二nil； z.right：二nil； z.p:二nil； pro

23、cedure insert（var T:tree，z:tree）；beginy:=nil;x:=T;while xnil do 從上往下找位置beginy:=x;if z.keyx.key t hen x:=x.lef telse x:=x.righ t;end;z.p:=y; 插入 if y=nil then T： =z 空樹，則作為根結點else if z.key bs t.key Then inser t(bst .righ t,s); End;八、刪除 排序二叉樹的刪除與普通二叉樹的刪除有所不同，因為它要保證刪除某個結點后，剩下 的所有結點按中序遍歷后仍然有序輸出。刪除結點z,可以分3

24、種情況討論：1、如果z沒有孩子，則直接刪除即可，即z.p.left:二nil或z.p.right:二nil；2、如果 z 只有一個孩子,則可通過在其父結點和孩子結點之間建立一個鏈接從而刪除 z；即若z無左子樹，則用z的右子樹的根代替z,如下左圖；若z無右子樹，則用 z的左子樹的根代替z,如下右圖；或或3、如果結點z有兩個孩子，則先刪除z的后繼y （它一定沒有左孩子，為什么？）再 用y的內容代替z的內容，同時把y的右子樹（如果有）的根結點代替y；當然也 可以先刪除z的前趨y （它一定沒有右孩子，同理），再用y的內容代替z的內容， 并將y的左子樹（如果有）的根結點代替y；但最好的方法卻是把z的左子

25、樹的根 結點（下圖中的C）代替z,而把z的右子樹的根（下圖中的D）插在z的左子樹的 最右側（下圖，作為 y 的右孩子， y 本身一定無右孩子），具體如下圖：以下是一個實現刪除的程序段：procedure delete(var T:tree,z:tree);beginif (z.lef t二nil) or (z.righ t二nil) t hen y:=zelse y:二succ(z);找到要刪除的結點yif y.lef tnil t hen x:二y.lef telse x:二ylright;x是 y 的孩子if xnil t hen x.p:二y.pif y.p=nil t hen T:=x

26、 刪除的是根else if y=y.p.lef t t hen y.p.lef t:=xelse y.p.righ t:二x;if yz thenbeginzlkey:二ylkey;如果有其它域，也一并進行復制；dispose(y);end;end;* 定理 2：一棵高度為 h 的排序二叉樹，對它進行插入和刪除操作，時間復雜度都為 O(h)。例 1：編程輸入一組不同的整數(約定大于等于0，輸入負數表示結束)，建立一棵排序二叉 樹，再按中序遍歷輸出廣義表形式。參考程序Program bst_creat_out;Type tree=node;node=Record key:Integer;left

27、,right,p:tree;End;Var bst,s:tree;n:Integer;procedure insert(var T:tree;z:tree);var x,y:tree;beginy:=nil;x:=T;while xnil dobeginy:=x;if z.keyx.key t hen x:=x.lef telse x:=x.righ t;end;z .p：=y;if y=nil then T:=zelse if z.key y.key t hen y.lef t:=z else y.righ t:二z; end;procedure out(root:tree);beginwr

28、ite();if root .lef tnil t hen out(root .lef t);writ e(r oot .key);if root.rightnil then out(root.right); write();end;Beginbst:=Nil;Writeln(input data(if 0 then over!):);RepeatRead(n);if n=0 ThenbeginNew(s); s.key:=n;s.left:=Nil;s.right:=Nil;s.p:=NIL; insert(bst,s);end;Until n0;Writeln(output sorted

29、data:);out(bst);Writeln;End.例 2 ：在上面例 1 的基礎上再刪除一個指定關鍵字的結點。參考程序Program bst_delete;Type tree=node;node=Record key:Integer; left,right,p:tree;End;Var bst,s:tree;n:Integer;function min(x:tree):tree;beginwhile x.lef tnil do x:= x.lef t; min:=x;end;function search(T:tree;k:integer):tree; beginwhile (Tnil)

30、 and (kT.key) do beginif kT.key t hen T:= T.lef telse T:= T.righ t; end;search:=T;end;function succ(x:tree):tree;var y:tree;BeginIf x.righ tnilthen begin x:二min(x.right);y:二x;end else beginy：= x .p;While (y.pnil) and (x=y.righ t) doBegin x:=y;y:=y.p;end;end;succ:=y;End;procedure insert(var T:tree;z:

31、tree);var x,y:tree;beginy:=nil;x:=T;while xnil dobeginy:=x;if z.keyx.key t hen x:=x.lef telse x:=x.righ t;end;z.p:=y;if y=nil then T:=zelse if z.key y.key t hen y.lef t:=z else y .right:二z;end;procedure delete(var T:tree;z:tree);var x,y:tree;beginif (z.lef t二nil) or (z.righ t二nil) t hen y:=zelse y:=

32、succ(z);if y.lef tnil t hen x:二y.lef telse x:=y.righ t;if xnil t hen x.p:二y.p;if y.p=nil then T:=xelse if y=y.p.lef t t hen y.p.lef t:=xelse y.p.righ t: =x; if yz t hen z.key:二y.key;dispose(y);end;procedure out(root:tree);beginwrite();if root .lef tnil t hen out(root .lef t);writ e(r oot .key);if ro

33、ot.rightnil then out(root.right); write();end;Beginbst:=Nil;Writeln(input data(if 0 then over!):);RepeatRead(n);if n=0 ThenbeginNew(s); s.key:=n;s.left:=Nil;s.right:=Nil;s.p:=NIL; insert(bst,s);end;Until n0;Writeln(output sorted data:);out(bst);writeln;writeln(input a key to delete:);readln(n);delet

34、e(bst,search(bst,n);out(bst);Writeln;End.* 思考：若存在相同關鍵字的結點，則如何改進排序二叉樹？* 總結：排序二叉樹不一定是平衡樹，它在最壞的情況下，插入和查找等操作的復雜度會退化達到0(n)。例 3 、鏟雪車問題問題描述大雪履蓋了整個城市，市政府要求冬季服務部門盡快將一些街道(列在一份清單中)的 積雪清除掉以恢復交通，整個城市由許多交叉路口和街道構成，當然任意兩個交叉路口都是 直接或間接連通的，清單給出了最少的街道，使得這些街道的積雪清除后任意兩個交叉路口 之間有且僅有一條通路，冬季服務部門只有一輛鏟雪車及一名司機，這輛鏟雪車的出發點位 于某個交叉路

35、口。無論街道上有沒有積雪，鏟雪車每前進一米都要消耗一升燃料，冬季服務部門要求司機 在鏟除清單上的所有街道的積雪的前提下，要求消耗燃料最少，積雪鏟完后車可以停在任意 的交叉路口。輸入格式輸入文件名為one.in,第一行包含兩個整數N和S, 1WNW100000, 1WSWN。N為交 叉路口的總數；S為鏟雪車出發的路口序號。路口的標號為1N。接下來的N-1行為清單上的街道，每一行包含三個用空格隔開的整數A、B、C,表示一 條從交叉路口 A到交叉路口 B的街道，C為該街道的長度，單位為米，1WCW1000。輸出格式輸出文件名為one.out,僅一行包含一個整數表示清除所有積雪所需的最少的燃料數量。樣

36、例輸入5112813103410457樣例輸出43問題分析在樹的基本概念中，我們知道“一棵樹中的任意兩個不同結點之間一定存在著一條唯一 的路徑，不論是直接的或間接的。圖論意義上的路徑概念”。在本題中，我們把每個路口作 為一個結點的話，則整個街道就是一棵樹，而且鏟雪車出發點正好就是樹根，而題目中“任 意兩個交叉路口之間有且僅有一條通路”這個條件正好符合上述概念。所以本題就變成了一 個樹的遍歷問題，只不過是一個“加權樹權為街道的長度、也即清除本街道積雪所需要 的燃料數量”，而且滿足“每條邊至少被訪問一次”和“權的和最小”。對于上述的樣例，我 們可以畫出如下圖所示的樹型結構，現在的問題就轉變成“求遍

37、歷整棵樹中的所有結點的權 值之和的最小值”這個問題結果等價于total*2-maxt,其中total=整棵樹的權值之和； maxt=根結點深度遍歷到每個葉結點的權值之和的最大值”，如樣例中total=8+10+10+7=35, maxt=max8,10+10+7=27，所以結果為 35*2-27=43。數據結構方面：因為本題的樹型結構是多叉樹，而且結點數目巨大，存儲和操作起來都 很麻煩，所以我們把它轉換成二叉樹的形式。而且處理時沒有用鄰接矩陣的方法，而是轉換 成類似于稀疏矩陣的存儲方法。參考程序Program one(Input, Output)；Const maxn = 100000；max

38、v = (maxn-1)*2；Type vtype=Recordb,c,p:Longint； 每個結點的左孩子、左鄰接邊上的權值、右孩子End；Var n,s,i,a,b,c,total:Longint；v:Array1.maxv Of vtype； 存儲結點相鄰信息的線性表list:Array1.maxn Of Longint； 動態存儲各個結點的當前鄰接點的線性表p:Array1.maxn Of Boolean； 標志結點是否被訪問過Function try(x : Longint) : Longint 找一條路徑，使得從根結點深度遍歷到葉結點的Var d, max : Longint；權

39、值之和為最大值y : Longint；Beginpx:=True；y:=listx；max:=0；While y0 Do有子結點，則繼續遍歷BeginIf Not(pvy.b) Then d:=vy.c + try(vy.b)遞歸遍歷孩子結點Else d:=0；If dmax Then max:=d； 打擂臺y:=vy.p；End；try:=max；End；Begin mainAssign(Input, one.in)； Assign(Output, one.out)；Reset(Input)；Rewrite(Output)；Readln(n, s)；total := 0；For i:=1 T

40、o n Do listi:=0；For i:=1 To n-1 Do 讀入和初始化BeginReadln(a, b, c)；total:=total+c； 累加權值 vi*2-1.b:=b； 記錄左結點 vi*2-1.c:=c； 記錄右結點 vi*2-1.p:=lista； 記錄當前邊上的權值 lista:=i*2-1；vi*2.b:=a； 考慮邊的對稱性，交換一條邊的起點和終點 vi*2.c:=c；vi*2.p:=listb； listb:=i*2；End；For i:=1 To n Do pi:=False；total:=total*2-try(s)；Write(total)；Close(

41、Input)； Close(Output)；End.例 4 、鳥語字典 問題描述Robin是一只極其聰明的鳥，他著迷于人類豐富多彩的語言。經過長時間的摸索，Robin 模仿人類的英語創造了鳥類的語言。與英語類似，這種鳥語的基本單位(我們不妨也稱其為 字母)也是由26個小寫英文字母a至z組成的。同時，若干個字母組成一個單詞，用來表 達一定的意思(和英語一樣？！)，相鄰兩個單詞由一個空格隔開。Robin為他新發明的鳥語 創造了豐富的詞匯，并花費大量精力寫成一本鳥語字典。正如你所想的那樣，Robin想把一 些英文的書籍(如時間簡史、物種起源等，翻譯成鳥語。但是，這項工作實在是太浩 大了，以至于Rob

42、in無法完成。聰明的Robin想到使用計算機，他編寫了一個自動翻譯的程 序來翻譯這些書籍。但是很快，他發現，有很多詞匯是他原先所沒有想到的(。例如，時間 簡史中的“夸克”，厚厚的鳥語字典里并沒有這個詞。，對于這種情況，他的自動翻譯程序 將會不對其做翻譯，而是直接放入譯文中。下面是一個例子，表1表示字典中只有4個英文單詞及其鳥語含義。給出下列一個英文句子：I am a clever bird. 翻譯后的鳥語語句為： op dg a clever myself.對于沒有在字典中出現的單詞clever，自動翻譯程序直接將其放入譯文中。表 1 給定的一個字典序號英文鳥語1Iop2amdg3aa4bir

43、dmyself現在，Robin已經翻譯了一些著作，他希望補充他的鳥語字典。因此，他想知道有多少 單詞在他的鳥語字典里是沒有的，并且，他想統計出在這些沒有出現在他的鳥語字典中的單 詞中，出現次數最多的單詞是哪一個。輸入鳥語字典來自文件Die. txt。其中，第一行為一個正整數n（lWnWlOOOO）表示字典內的 單詞的數目。接下來的n行，每行有一個單詞（沒有多余空格）。字典中沒有重復的單詞。輸入數據來自文件Input.txt。輸入文件中是一段文本，由若干鳥語（英語）單詞組成， 相鄰兩個單詞之間用至少一個空格隔開，文本中可能存在某些標點及其他符號。（文本中的 單詞數目不超過10000。）輸出輸出文

44、件名為Output.txt。輸出文件的第一行是一個整數m，表示有m個單詞沒有在鳥 語字典中出現。接下來的若干行每行一個單詞，表示那個沒有出現在鳥語字典當中，且出現 次數最多的單詞（有幾個輸出幾個）。輸入輸出樣例Dic.txt:3aejdopqInput.txtae jd . jda opq jda ae. ld jd opq!Output.txt2 jda問題分析本題的實質是：給定兩組字符串A和B （字典和要翻譯的文章），統計出在字符串組B 中出現而在字符串組A中未出現的字符串的個數，并輸出這些字符串中在字符串組B中出現 次數最多的一個（或多個）。了解了本題的實質之后，可以輕松得到本題的大致算

45、法：在字符串組A中查找每一個出 現在字符串組B的字符串，若沒有找到，就記錄下這個字符串及其出現次數。最后，就可以 統計出滿足上述條件的字符串的個數及出現次數最多的字符串了。注意到程序的主要耗時花費在字符串組A中查找字符串，所以，提高在字符串組A中查 找字符串的效率尤為重要。因此，解決效率問題的關鍵在于數據結構的選擇。我們可以采用線性表來解決：時刻保持字符串組A中的字符串的有序性(對字符串進行 比較大小還是比較容易辦到的)，使用二分查找，從而把查找字符串的時間效率限制在 O(log2n)的等級上。但是，值得注意的是，我們還是經常要對字符串組A進行插入操作的： 一開始生成有序的字符串組不說，為了正

46、確的統計沒有在字符串組A中出現的字符串，也需 要在適當的時候將這些字符串添加進入字符串組A (當然，我們要對這些新的字符串做上記 號，以區別于其他的字符串)。對有序表的插入算法的時間復雜度為0(n)。由于n比較大， 這樣的數量級就已經令人頭疼了，所以，我們還需要更為有效的算法：二叉排序樹。我們完全可以把字符串組A中的字符串插入一個二叉排序樹中，下面所需要做的只是對 這個二叉排序樹進行查找和添加工作。二叉排序樹的查找效率為O(log2n)，而其插入效率也 為O(log2n)。由于n比較大，n和log2n的差距很大，這種算法的效率較前一種相比有了較 大的提高。下面通過列表來比較兩種算法的效率(測試

47、環境為PIII800,128MB)：表2序號數據量(n)基于線性表的算法基于二叉排序樹的算法110001.15s0.27s220004.12s0.44s3500018.85s0.88s410000Long1.98s可以看出，雖然只是由O(n)降到O(log2n)，但效果卻是很明顯的。其實，本題還有再改進的余地：二叉排序樹的缺點就是對數據沒有選擇性，它的效率在 很大程度上依賴于插入的順序，如果輸入的數據本身就是有序的，二叉排序樹將不幸的蛻變 為線性表。因此，如果在對二叉排序樹進行插入的過程中，時刻注意保持二叉排序樹的平衡 性，也可以有效提高算法的效率。至于具體如何二叉保持樹的平衡性，由于篇幅限制，這里 不多加討論，