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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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