1、u 內(nèi)容提要本講首先簡(jiǎn)要介紹了樹的幾種常見的存貯結(jié)構(gòu)、森林和二叉樹的相互轉(zhuǎn)換。接著介紹了二叉排序樹(通過對(duì)二叉排序樹進(jìn)一次中序遍歷，即可將無序數(shù)據(jù)排列成有序序列)，堆及堆排序(堆排序使用的輔助空間較少，僅增加一個(gè)記錄空間用于交換，同時(shí)關(guān)鍵字比較的次數(shù)和樹形選擇排序相當(dāng))。重點(diǎn)之一：闡述二叉排序樹的概念，討論二叉排序樹的生成，二叉排序樹的插入、刪除，及二叉排序樹的應(yīng)用。重點(diǎn)之二：闡述堆的概念，討論堆的存儲(chǔ)、堆排序的基本思想，介紹堆排序的過程，堆的插入、刪除操作，堆排序的應(yīng)用。u 知識(shí)講解和實(shí)例分析一、樹和森林：1、樹的存貯結(jié)構(gòu)(1)、雙親表示法利用每個(gè)結(jié)點(diǎn)(除根結(jié)點(diǎn)外)只有唯一雙親的特點(diǎn)，用二維

2、數(shù)組來存貯一棵一般樹。這種結(jié)構(gòu)對(duì)于尋求某結(jié)點(diǎn)的雙親及求樹的根結(jié)點(diǎn)等操作是很方便的，但用于求結(jié)點(diǎn)的孩子時(shí)比較麻煩，需要遍歷整個(gè)數(shù)組。(2)、孩子表不法用多重鏈表來存貯一般樹。在多重鏈表中，每個(gè)結(jié)點(diǎn)有多個(gè)指針域，每個(gè)指針域指向一棵子樹的根結(jié)點(diǎn)，此時(shí)有兩種結(jié)點(diǎn)結(jié)構(gòu)：A、多重鏈表中的結(jié)點(diǎn)是同構(gòu)的，則會(huì)浪費(fèi)較多的存貯空間；B、多重鏈表中的結(jié)點(diǎn)是不同構(gòu)的，雖然節(jié)約存貯空間，但操作不方便。(3)、孩子兄弟表示法最常用的存儲(chǔ)方法是孩子兄弟表示法。即以二叉樹鏈表作為樹的鏈表。鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別指向該結(jié)點(diǎn)的第一個(gè)孩子和下一個(gè)兄弟結(jié)點(diǎn)。2、森林和二叉樹的轉(zhuǎn)換：(1)、森林轉(zhuǎn)換為二叉樹：如果 F=T1,T2,

3、，Tm是森林，則可按下列規(guī)則轉(zhuǎn)換成二叉樹 B=root,LB,RB(i)、若 F 為空，即 m=Q 則 B 為空樹。(ii)、若 F 不為空，即 m 不為 0,則 B 的根即為森林中第一棵樹的根；B 的左子樹 LB 是從森林 F1=T11,T12T1m轉(zhuǎn)換而成的二叉樹；其右子樹 RB 是從森林 F=T2,T3,Tm 并專換而成的二叉樹。(2)、二叉樹轉(zhuǎn)換為森林：(i)、若 B 為空，則 F 為空。(ii)、若 B 非空，則 F 中第一棵樹 T1 的根 ROOT(T1)即為二叉樹 B 的根 root;T1 中根的子樹森林 F1 是由 B 的左子樹LB 轉(zhuǎn)換而成的森林；F 中除 T1 之外，其余樹

4、組成的森林 F=T2,T3,Tm是由 B 的右子樹 RB 轉(zhuǎn)換擊成的森林。二、二叉排序樹：1、二叉排序樹的定義：二叉排序樹或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：(1)、若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；(2)、若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；(3)、它的左、右子樹也分別是二叉排序樹。2、二叉排序樹的查找：在二叉排序樹 b 中查找 x 的過程為：(1)、若 b 是空樹，則搜索失敗；否則(2)、若 x 等于 b 的根結(jié)點(diǎn)的數(shù)據(jù)域的值，則查找成功；否則(3)、若 x 小于 b 的根結(jié)點(diǎn)的數(shù)據(jù)域的值，則搜索左子樹；否則(4)、搜索右子樹funct

5、ionsearch(b:btree;x:integer):btree;beginIf(b=nil)thensearch:=nilElsebeginIf(bA.data=x)thensearch:=b;If(xIf(xbA.data)thensearch:=search(bA.right,x);end;end;3、二叉排序樹的生成：首先討論向一棵二叉排序樹 b 中插入一個(gè)結(jié)點(diǎn) s 的算法，其過程為：(1)、若 b 是空樹，則將 s 作為根結(jié)點(diǎn)插入；否則(2)、若 sA.data 等于 b 的根結(jié)點(diǎn)的數(shù)據(jù)域之值，則返回；否則(3)、若 sA.data 小于 b 的根結(jié)點(diǎn)的數(shù)據(jù)域之值，則把 s 結(jié)點(diǎn)

6、插入到左子樹中；否則(4)、把 s 結(jié)點(diǎn)插入到右子樹中。向一棵二叉排序樹 b 中插入一個(gè)結(jié)點(diǎn) s 的過程如下：procedureinsert(varb:btree;s:btree);beginif(b=nil)thenb:=selseif(sA.dataelseif(sA.databA.data)theninsert(bA.right,s)end;生成二叉排序樹的過程是先有一個(gè)空樹 b,然后逐個(gè)向該空樹中插入結(jié)點(diǎn)實(shí)現(xiàn)的。因此根據(jù)用戶輸入的一系列正整數(shù)(一 1 表示結(jié)束)生成一棵二叉排序樹的過程如下：procedurecreat(varb:btree);varx:integer;s:btree;

7、beginb:=nil;read(x);whilex=-1dobeginnew(s);sA.data:=x;sA.left:=nil;sA.right:=nil;insert(b,s);read(x);endend;4、二叉排序樹的刪除：刪除二叉排序樹 b 中一個(gè)數(shù)據(jù)域?yàn)?x 的結(jié)點(diǎn)的過程為：(1)、首先查找到數(shù)據(jù)域?yàn)?x 的結(jié)點(diǎn) p(2)、若結(jié)點(diǎn) p 沒有左子樹，則用右子樹的根代替被刪除的結(jié)點(diǎn)(3)、若結(jié)點(diǎn) p 有左子樹，則在其左子樹中找到最右結(jié)點(diǎn) r,將 p 的右子樹置為 r 的右子樹，再將 p 的左子樹的根結(jié)點(diǎn)代替被刪除的結(jié)點(diǎn) p過程如下：proceduredelnode(varb:bt

8、ree;x:integer);varp,q,r,t:btree;beginp:=b;q:=nil;while(pnilandqA.datax)doif(xbeginq：=p;p:=pA.leftendelsebeginq:=p;p:=pA.rightend;if(p=nil)thenwriteln(notfind)elseif(pA.left=nil)thenif(q=nil)thent:=pA.rightelseif(qA.left=p)thenqA.left:=pA.rightelseqA.right:=pA.right;elsebeginr:=pA.left;while(pA.right

9、nil)dor:=rA.right;rA.right:=pA.right;if(q=nil)thent:=pA.leftelseif(qA.left=p)thenqA.left:=pA.leftelseqA.right:=pA.leftend;end;三、堆及其操作：1、堆的定義：堆是由 n 個(gè)關(guān)鍵字組成的序列K1,K2,，Kn,當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆。KiK2i、KiK2i、KiK2i+1(稱為最大堆)其中 1=1,2,，Ln/2堆可以看成是對(duì)一棵以 K1 為根的完全二叉樹進(jìn)行按廣度優(yōu)先遍歷所得到的結(jié)點(diǎn)序列。按照堆的定義，在這棵完全二叉樹中，任一結(jié)點(diǎn)的值都不大于(或不小于)它的兩個(gè)

10、孩子結(jié)點(diǎn)的值(因?yàn)楫?dāng) I5/2時(shí)完全二叉樹的第 I 結(jié)點(diǎn)不存在孩子結(jié)點(diǎn))，因此在堆中根結(jié)點(diǎn) K1 是最小的，并且二叉樹中任一子樹都是一個(gè)堆。2、堆的存儲(chǔ)：由于它是一棵完全二叉樹，所以可以把它象完全二叉樹一樣簡(jiǎn)單地儲(chǔ)存在數(shù)組中，根據(jù)完全二叉樹的性質(zhì)可以對(duì)于下標(biāo)為 i 的結(jié)點(diǎn)，其子結(jié)點(diǎn)下標(biāo)為 2i、2i+1o 所以對(duì)于最大堆來說，數(shù)組中元素的值滿足：KiK2i、KiK2i+1、KiAi/23、堆排序的基本思想：對(duì)一組待排序的記錄的關(guān)鍵字，首先把它們按堆的定義排列成一個(gè)序列(稱為初始建堆)，同時(shí)也就找到了最小關(guān)鍵字，然后將最小關(guān)鍵字輸出。對(duì)剩余的關(guān)鍵字再建堆，便得到次小的關(guān)鍵字，如此反復(fù)進(jìn)行，直到全

11、部關(guān)鍵字有序?yàn)橹梗赐瓿闪硕雅判蜻^程。(1)、將以 Ki 為根的子樹建成堆(最小堆為例)：設(shè)有關(guān)鍵字集合K1,K2,，Kn,若對(duì) I=L+1,L+2,，n 均滿足堆的定義(其中 L=匚 n/2)，現(xiàn)在對(duì) I=L 進(jìn)行篩選建堆：Proceduresift(L,n:integer;VARheap:ARRAY1.nOFnode);VARI,j:integer;X:node;BeginI:=L;J:=2*I;X:=heapI;Whilejheapj.keyThenBeginHeapI:=heapj;子樹結(jié)點(diǎn)上調(diào)I:=j;J:=2*I下沉一層endelsej:=n+1;跳出循環(huán)end;heapI:=xe

12、nd;(2)、堆排序過程：對(duì)一個(gè)已知的關(guān)鍵字序列K1,K2,，Kn,只要使上述算法中的變量 L 從n/2開始直到 L=1 為止,反復(fù)調(diào)用 sift(L,n,heap)算法就得到一個(gè)滿足堆定義的對(duì)應(yīng)關(guān)鍵字序列。即建成了堆，并找到了最小關(guān)鍵字。輸出最小關(guān)鍵字之后，是否還需要對(duì)剩余的 n-1 個(gè)關(guān)鍵字從頭開始重新建堆呢？不需要。因?yàn)檩敵鲎钚￡P(guān)鍵字 K1 之后，它的左、右子樹的根 K2 和 K3 仍具有堆的特性，所以把 Kn 放到 K1 位置，再次調(diào)用一次 sift(L,n-1,heap),便可得到剩余 n-1 個(gè)關(guān)鍵字的新堆，從而得到剩余 n-1 個(gè)關(guān)鍵字中的最小關(guān)鍵字。為了節(jié)省空間，我們可以把第一

13、次輸出的最小關(guān)鍵字放在 Kn 的位置上，把第二次輸出的最小關(guān)鍵字存放在 Kn-1的位置上，。如此反復(fù)執(zhí)行 n-1 次，便完成了排序過程。Procedureheapsort(n:integer;VARheap:ARRAY1.nOFnode);VARI:integer;BeginForI:=(ndiv2)downto1doSift(I,n,heap);Whilen1dobiginHeap0:=heap1;Heap1:=heapn;Heapn:=heap0;N:=n-1;Sift(1,n,heap)endend;由上述算法可見，堆排序僅需一個(gè)記錄大小的輔助空間供交換使用。堆排序的運(yùn)行時(shí)間主要消耗在初

14、始建堆和調(diào)整時(shí)的反復(fù)篩選重新建堆上，對(duì)于 n 個(gè)關(guān)鍵字集合進(jìn)行堆排序的時(shí)間復(fù)雜度為 O(nlog2n)。它適用于 n 較大的情況。4、最大堆的插入操作：根據(jù)最大堆的定義及性質(zhì)可知，插入一個(gè)結(jié)點(diǎn)后還是一棵完全二叉樹，所以該結(jié)點(diǎn)必插入在數(shù)組的最后，插入后，比較它和父結(jié)點(diǎn)的關(guān)系，若大于父結(jié)點(diǎn)則和其交換，再和上一層比較，這樣一直做下去。過程如下：procedureinsert(x:integer);varI:integer;beginheapsize:=heapsize+1;I:=heapsize;While(I1)and(xheapIdiv2)doBeginHeapI:=heapIdiv2;I:=I

15、div2;End;HeapI:=xEnd;5、最大堆元素的刪除操作：在最大堆中刪除一個(gè)元素后，堆的容量減少 1,明顯最后一個(gè)元素該取代被刪除元素的位置，取代后還要考慮它和孩子的關(guān)系，若大于它的孩子則取代成功，否則它要和它的最大的孩子交換位置，再和新位置的孩子比較大小關(guān)系，這樣一直做下去。刪除 I 個(gè)元素的過程如下：proceduredelete(I:integer);varx:integer;beginx:=heapheapsize;heapsize:=heapsize-1;son:=2*I;while(son=heapsize)dobeginif(sonheapsonthenbreak;he

16、apI:=heapson;I:=son;Son:=2*I;End;HeapI:=x;End;u 舉例及應(yīng)用：1、已知圖 a 中的二叉排序樹的各個(gè)結(jié)點(diǎn)的值分別為 1 至 9,并且各自不相同，請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。解：該二叉樹各結(jié)點(diǎn)的值如圖 b 所示。圖(a)圖(b)2、設(shè)非空二叉排序樹采用二叉鏈表儲(chǔ)存結(jié)構(gòu)，根結(jié)點(diǎn)的指針為 To 請(qǐng)寫一算法，找出該二叉樹中值最小的結(jié)點(diǎn)。算法分析：由二叉排序樹的定義可以知道，非空二叉排序樹中值最小的結(jié)點(diǎn)是二叉排序樹最左邊那個(gè)結(jié)點(diǎn)。因此，只須設(shè)置一個(gè)指針變量，首先令它指向二叉排序樹的根結(jié)點(diǎn)，然后讓它沿著它左子樹方向一直找下去，直到某一時(shí)刻，該變量所指的結(jié)點(diǎn)的左子樹為空，此

17、時(shí)，該結(jié)點(diǎn)就是二叉樹中值最小的結(jié)點(diǎn)。Functionminnode(T)beginP:=tWhile(pA.leftnil)doP:=pAleftminnode:=pend3、已知序列(35,78,12,26,90,41,66,58),請(qǐng)寫出對(duì)該序列采用堆排序方法進(jìn)行升序排序時(shí)各趟的結(jié)果。L 從n/2開始直到 L=1 為止，反復(fù)調(diào)用 sift(L,n,heap)算法就得到一個(gè)滿足堆定義的對(duì)應(yīng)關(guān)鍵字序列。即建成了堆，并找到了最小關(guān)鍵字。輸出最小關(guān)鍵字之后，把 Kn 放到 K1 位置，再次調(diào)用一次 sift(L,n-1,heap),便可得到剩余 n-1 個(gè)關(guān)鍵字的新堆，從而得到剩余 n-1 個(gè)關(guān)鍵

18、字中的最小關(guān)鍵字。如此反復(fù)執(zhí)行 n-1 次，便完成了排序過程。程序清單：參照 sift(L,n,heap)及 heapsort(n,heap)u 習(xí)題：解：原始序列：35,第一趟后：26,第二趟后：12,第三趟后：12,第四趟后：12,第五趟后：26,第六趟后：12,第七趟后：12,7812267866585866265841263541263512412635412635419041665835411290354178903566789058667890586678905866789058667890算法分析：對(duì)于該序列，只要使變量1、將一段英文中出現(xiàn)的單詞按詞典的順序打印出來，并統(tǒng)計(jì)出每個(gè)單詞在文章中出現(xiàn)的次數(shù)。數(shù)據(jù)輸入：任意的一段英文句子數(shù)據(jù)輸出：先按詞典的順序打印出所有出現(xiàn)的單詞，再輸出每個(gè)單詞出現(xiàn)的次數(shù)樣例輸入 1:Thisisabeautifulhouse.樣例輸出 1:abeautifulhouseisThisa：1beautiful:1house：1is：1This:12、我們知道給定一個(gè) 1 至 n 的 n 個(gè)數(shù)的任意序列，唯一確定一棵二叉排序樹，但根據(jù)這棵二叉排序樹，往往不能唯一確定 n