二k叉樹及其應(yīng)用雅禮

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

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

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

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

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

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

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

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

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

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

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

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

13、前要插入 (實際上是不斷向上調(diào)整的過程)PROC heapdown(k:longint);把第k個結(jié)點往下調(diào)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;插入 (實際上是不斷向上調(diào)整的過程)PROC heapdow堆的構(gòu)造就是不斷插入到堆的過程 62351分別插入權(quán)為6,2,3,5,1的元素6(1)6(2)26(3)236(4)2356(5)2351堆的構(gòu)造就是不斷插入到堆

14、的過程 62351分別插入權(quán)為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); 添合并果子在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯觯械墓咏?jīng)過n-1次合并之后，就只剩下

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

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

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

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

19、它左右子樹分別為二叉排序樹。二叉排序樹(Binary Sort Tree) 二叉排序樹又BST的特點（1） 二叉排序樹中任一結(jié)點x，其左(右)子樹中任一結(jié)點y(若存在)的關(guān)鍵字必小(大)于x的關(guān)鍵字。（2） 二叉排序樹中，各結(jié)點關(guān)鍵字是惟一的。實際應(yīng)用中，不能保證被查找的數(shù)據(jù)集中各元素的關(guān)鍵字互不相同，所以可將二叉排序樹定義中BST性質(zhì)(1)里的小于改為大于等于，或?qū)ST性質(zhì)(2)里的大于改為小于等于，甚至可同時修改這兩個性質(zhì)。（3） 按中序遍歷該樹所得到的中序序列是一個遞增有序序列。BST的特點（1） 二叉排序樹中任一結(jié)點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的插入在二叉排序樹中插入新結(jié)點，要保證插入后仍滿足BST性質(zhì)。其插入過程是：(a)若二叉排序樹T為空，則為待插入的關(guān)鍵字key申請一個新結(jié)點，并令其為根；(b)若二叉排序樹T不為空，則將key和根的關(guān)鍵字比較：(i)二者相等，則說明樹中已有此關(guān)鍵字key，無須插入。 (ii)keyTkey，則將它插入根的右子樹中。子樹中的插入過程與上述的樹中插入過程相同。如此進行下去，直到將key作為一個新的葉結(jié)點的關(guān)鍵字插入到二叉排序樹中，或者直到發(fā)現(xiàn)樹中已有此關(guān)鍵字為止。BST的插入在二叉排序樹中插入新結(jié)點，要保證插入后仍滿足BSBST插入的遞歸算法PRO