1、二k叉樹及其應用雅禮二k叉樹及其應用雅禮二叉樹二叉樹是一種特殊的樹型結構，它的特點是每個節點至多只有兩個子節點。二叉樹每個節點的子樹有左右之分，其次序不能任意顛倒。二叉樹也有特殊形式，例如滿二叉樹、完全二叉樹等。例如右圖就是一棵二叉樹，并且是一棵完全二叉樹。二叉樹二叉樹是一種特殊的樹型結構，它的特點是每個節點至多只有二叉樹的存儲結構常用的存儲結構 type bitree=node node=record data :datatype; lchild,rchild:bitree; end;二叉樹的存儲結構常用的存儲結構 type bitre二叉樹的遍歷遍歷( 先序遍歷, 中序遍歷, 后序遍歷)P

2、roc preorder(bt:bitree); if btNil then visit(bt) preorder(bt.lchild); preorder(bt.rchild); endP二叉樹的遍歷遍歷( 先序遍歷, 中序遍歷, 后序遍歷)二叉樹的性質在二叉樹的第i層上最多有2i-1個結點深度為K的二叉樹最多有2k-1個結點在二叉樹中,葉子結點的總數總比為度數為2的結點多1有n個結點的完全二叉樹的結點按層序編號,則對任意一結點i,有(1)如果i=1,則結點i是二查樹的根，無雙親；如果i1，則雙親是i/2(2)如果2in，則結點i無左孩子，否則左孩子為2i(3)如果2i+1n，則結點i無右孩

3、子，否則右孩子為2i+1二叉樹的性質在二叉樹的第i層上最多有2i-1個結點樹、森林轉化為二叉樹用“孩子兄弟表示法”可以將任意一棵樹轉化為二叉樹的形式 森林轉化為二叉樹 如果F=T1, T2, ,Tm是森林，則可按如下規則轉化為一棵二叉樹。 1)若F為空，即m=0,則B為空樹 2)若F非空，即m0,則B的根root即為森林中第一棵樹的根root(T1),B的左子樹為從T1中子樹森林F1=T11, T12, ,T1i轉換而成的二叉樹；其右子樹Rb 是從森林F=T2, ,Tm中轉換出來的二叉樹樹、森林轉化為二叉樹用“孩子兄弟表示法”可以將任意一棵樹轉化樹的兒子兄弟表示法在一棵樹中，擁有同一個父結點的

4、結點互稱為兄弟。我們不妨假設樹中每個結點的子結點是有序的（就像二叉樹一樣），則我們可以將一棵樹這樣轉化成二叉樹：二叉樹中每個結點對應原樹的每個結點對于二叉樹中的某個結點它的左子結點對應原樹中該結點的第一個子結點；它的右子結點對應原樹中該結點的下一個兄弟。樹的兒子兄弟表示法在一棵樹中，擁有同一個父結點的結點互稱為兄原樹轉化后的樹樹的兒子兄弟表示法原樹轉化后的樹樹的兒子兄弟表示法這樣我們可以類似于二叉樹的鏈式結構寫出樹的兒子兄弟表示法的存儲結構： TYPE tree = node; node = record data : datatype; parent, child, brother : tr

5、ee; / 分別記錄父親、第一個兒子、下一個兄弟 end;樹的兒子兄弟表示法這樣我們可以類似于二叉樹的鏈式結構寫出樹的兒子兄弟表示法的存給定m個實數w1, w2, wm,(m=2) ,要求一個具有m個外部節點的擴充二叉樹，每個外部ki節點有一個wi與之對應，作為它的權,使得帶權外部路徑長度 最小，其中li是從根到外部節點的路徑長度。最優二叉樹(哈夫曼樹)給定m個實數w1, w2, wm,(m=2) ,要求一算法1.構造m個只有1個節點的樹2.找兩個最小的權3.以這兩個節點為左右兒子構造一個二叉樹，并將該數的根節點權之為左右兒子權值之和4.繼續第二步，直到剩下一棵樹為止算法1.構造m個只有1個節

6、點的樹討論最優k叉樹就是指在一個節點最多可以有k個葉子節點的時候，假設有n（n=k）個權值w1,w2,.wn,試構造出一棵有個葉子節點的k叉樹。每個葉子節點有一個不同的權值i。其中樹的帶權路徑長度最小的那棵樹叫做最優k叉樹。怎么構造?討論最優k叉樹就是指在一個節點最多可以有k個葉子節點的時候，分析最優k叉樹必須具備的性質：每個節點如果不是葉子節點，那么一定有k個兒子節點。權值大的節點不能在比權值小的節點下方。就是權值大的節點到樹根的長度要小于等于權值小的節點到樹根的長度。分析最優k叉樹必須具備的性質：算法根據給定的n個權值wl，w2，wn構成n棵k叉樹的森林F=T1，T2，Tn，其中每棵k叉樹

7、Ti中都只有一個權值為wi的根結點，其左右子樹均空。在森林F中選出k棵根結點權值最小的樹(當這樣的樹不止k棵樹時，可以從中任選k棵)，將這k棵樹合并成一棵新樹，為了保證新樹仍是k叉樹，需要增加一個新結點作為新樹的根，并將所選的k棵樹的根分別作為新根的左右孩子，將這k個孩子的權值之和作為新樹根的權值。對新的森林F重復(2)，直到森林F中只剩下一棵樹為止。這棵樹便是最優k叉樹。算法根據給定的n個權值wl，w2，wn構成n棵k叉樹的森反例假設k=3,當n=5時，這樣做是對的。但是當n=4時，用剛才的方法得到的“最優3叉樹”，但是，明顯右圖的那顆樹會比左圖的那顆樹優。 反例假設k=3,當n=5時，這樣

8、做是對的。但是當n=4時，用分析原因錯誤的原因：主要是左邊的這棵樹它并沒有排滿。可以把第3層的一個節點拉到第2層去，而這樣做肯定會讓WPL更小。那么肯定要讓第一次合并的時候，少合并幾個點，后面的操作就和上面所說得算法一樣。并且讓最后一次合并能合并n棵樹。從而讓上面排滿。那么第一次要合并多少個點呢？首先每次合并會讓樹的總數減少k-1棵，而最后還有n棵。那么完成了第一次合并后，剩下的樹的個數正好模k-1后等于1。那么第一次合并的樹的個數就應該是(n-2) mod (k-1) + 2。 而當k=2時，k-1=1，此時第一次合并的個數總是為2。分析原因錯誤的原因：主要是左邊的這棵樹它并沒有排滿。可以把

9、第改進算法根據給定的n個權值wl，w2，wn構成n棵k叉樹的森林F=T1，T2，Tn。其中每棵k叉樹Ti中都只有一個權值為wi的根結點，其左右子樹均空。進行第一次合并操作選出最小的(n-2)mod(k-1)+2顆根節點權值最小的樹進行合并成一棵新樹,該樹根的權值為選出來的樹的權值之和。在森林F中選出k棵根結點權值最小的樹(當這樣的樹不止k棵樹時，可以從中任選出k棵），將這k棵樹合并成一棵新樹，為了保證新樹仍是k叉樹，需要增加一個新結點作為新樹的根，并將所選的k棵樹的根分別作為新根的孩子，將這k個孩子的權值之和作為新樹根的權值。對新的森林F重復(2)，直到森林F中只剩下一棵樹為止。這棵樹便是最優

10、k叉樹。改進算法根據給定的n個權值wl，w2，wn構成n棵k叉樹二叉堆定義堆是一棵完全二叉樹，對于每一個非葉子結點，它的權值都不大于（或不小于）左右孩子的權值，我們稱這樣的堆為小根堆（或大根堆）。描述如下:n個元素的序列k1,k2,kn，當且僅當滿足 ki=k2i 并且 ki =k2i 并且 ki = k2i+1 二叉堆肯定是一顆完全二叉樹二叉堆定義在堆中插入元素x首先將元素x放到堆中的最后一個位置（即最底層最右邊的位置），然后不斷地把x往上調整，直到x調不動為止（即大于它現在的父親，或者x處于根結點）。定義一個堆:Var st:array1.maxn of longint; /存儲堆 n:l

11、ongint; /堆中元素個數在堆中插入元素x首先將元素x放到堆中的最后一個位置（即最底層13545 786213557864(1)將新節點插到最后(2)把新節點和父親進行交換1557864(3)繼續交換，直到重新滿足堆的性質32213545 786213557864(1)將新節點插到最后插入 (實際上是不斷向上調整的過程)PROC heapup (k:longint); 把第k個結點上調begin while k1 do begin i:=k div 2; i是k的父親 if stistk then begin swap(i,k); k:=i; 交換結點i和k end else exit;

12、end;end;插入 (實際上是不斷向上調整的過程)PROC heapup 在堆中刪除任意一個元素 這里說指的刪除任意一個元素，是指在當前堆中位置為w的元素。過程如下：首先把位置w的元素和最后一個位置的元素交換，然后刪去最后一個位置，這樣w上的元素就被刪除了。接著把位置w上的新元素不斷下調，直到滿足堆的性質。 在堆中刪除任意一個元素 這里說指的刪除任意一個元素，是指在當155786431557864315578634(1)當前要刪除的節點是根節點的左兒子(2)將根節點的左兒子和最后一個節點交換(3)將新的節點不斷下調，直到滿足堆的性質22155786431557864315578634(1)當

13、前要插入 (實際上是不斷向上調整的過程)PROC heapdown(k:longint);把第k個結點往下調begin while k+k=n do begin i:=min 2k,2k+1; 如果2k+1不存在直接返回k+k否則返回2個中間的值較小的元素 if stistk then begin swap(i,k); k:=i; end else exit end;end;插入 (實際上是不斷向上調整的過程)PROC heapdow堆的構造就是不斷插入到堆的過程 62351分別插入權為6,2,3,5,1的元素6(1)6(2)26(3)236(4)2356(5)2351堆的構造就是不斷插入到堆

14、的過程 62351分別插入權為6,2堆的插入.刪除PROC add(x:longint); 添加一個值為x的元素begin inc(n); stn:=x; up(n)end;PROC add(x:longint); 添加一個值為x的元素begin inc(n); stn:=x; up(n)end;堆的插入.刪除PROC add(x:longint); 添合并果子在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經過n-1次合并之后，就只剩下

15、一堆了。多多在合并果子時總共消耗的體力等于每次合并所消耗體力之和。因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節省體力。假定每個果子重量都為1，并且已知果子的種類數和每種果子的數目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。例如有3種果子，數目依次為1，2，9。可以先將1、2堆合并，新堆數目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數目為12，耗費體力為12。所以多多總共耗費體力=3+12=15?？梢宰C明15為最小的體力耗費值。合并果子在一個果園里，多多已經將所有的果子打了下來，而且按果【輸入文件】輸入文件fr

16、uit.in包括兩行， 第一行是一個整數n(1=n=10000),表示果子的種類數。第二行包含n個整數，用空格分隔，第i個ai(1=ai=20000)是第i個果子的數目?！据敵鑫募枯敵鑫募ruit.out包括一行，這一行只包含一個整數，也就是最小的體力耗費值。輸入數據保證這個值小于231。【樣例輸入】31 2 9【樣例輸出】15【數據規?！繉τ?0%的數據，保證有n=1000;對于50%的數據，保證有n=5000;對于全部的數據，保證有n=10000?！据斎胛募亢喜⒐影押铣啥押蟮拿慷训墓尤匀豢闯上鄬Κ毩⒌?，那么定義timesi等于第i堆果子被合并的次數，ai為第i堆數字權值。則 To

17、talcost= ，目標求得是 minTotalcost。建立一棵二叉樹，每堆果子分別為該樹的葉節點，一種二叉樹形態對應一種合并方案（2堆果子合并則有共同父結點），所以該方案的Totalcost =depthi*vi ，i是葉節點。解法是每次取出最小的兩個節點，并從節點集合中刪除，然后合并這兩點后再加入節點集合；重復，直到只剩一個節點； 合并果子把合成堆后的每堆的果子仍然看成相對獨立的，那么定義t由于每次要取出最小的兩個節點。（一般做法是每更新一次集合，重新排序，時間是O(n2)）。由于nTi而且jCi+1那么根據定理1，將K,i+1替換后肯定更優。于是得到了一個算法的基本流程：1.將任務按照

18、Ti排序。2.從小到大枚舉i。維護當前最優方案的集合U。每次將當前的任務I加入U后。如果不滿足條件了，那么刪去U中耗時最長的任務。3.輸出最優方案即可。因此我們需要使用一種數據結構，它能快速刪除耗時最長的任務，同時快速的插入一個新元素。顯然，使用大根堆即能滿足題目要求。分析考慮排序后前i個任務組成的最優方案集合是i。下面看第i二叉排序樹(Binary Sort Tree) 二叉排序樹又稱為二叉查找(搜索)樹(BST)它或者是一顆空樹，或者是具有如下性質的二叉樹：1)若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值2) 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值3)

19、它左右子樹分別為二叉排序樹。二叉排序樹(Binary Sort Tree) 二叉排序樹又BST的特點（1） 二叉排序樹中任一結點x，其左(右)子樹中任一結點y(若存在)的關鍵字必小(大)于x的關鍵字。（2） 二叉排序樹中，各結點關鍵字是惟一的。實際應用中，不能保證被查找的數據集中各元素的關鍵字互不相同，所以可將二叉排序樹定義中BST性質(1)里的小于改為大于等于，或將BST性質(2)里的大于改為小于等于，甚至可同時修改這兩個性質。（3） 按中序遍歷該樹所得到的中序序列是一個遞增有序序列。BST的特點（1） 二叉排序樹中任一結點x，其左(右)子樹實例實例BST的查找FUNC bstsrch(t:

20、bitreptr;K:keytype):bitree if (t=nil) or (t.key=K) then return(t) else if t.keyK then return(bstsrch(t.lchild,k) else return(bstsrch(t.rchild,k)endFBST的查找FUNC bstsrch(t:bitreptr;BST的插入在二叉排序樹中插入新結點，要保證插入后仍滿足BST性質。其插入過程是：(a)若二叉排序樹T為空，則為待插入的關鍵字key申請一個新結點，并令其為根；(b)若二叉排序樹T不為空，則將key和根的關鍵字比較：(i)二者相等，則說明樹中已有此關鍵字key，無須插入。 (ii)keyTkey，則將它插入根的右子樹中。子樹中的插入過程與上述的樹中插入過程相同。如此進行下去，直到將key作為一個新的葉結點的關鍵字插入到二叉排序樹中，或者直到發現樹中已有此關鍵字為止。BST的插入在二叉排序樹中插入新結點，要保證插入后仍滿足BSBST插入的遞歸算法PRO