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

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

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

4、組成的森林 F=T2,T3,Tm是由 B 的右子樹 RB 轉換擊成的森林。二、二叉排序樹：1、二叉排序樹的定義：二叉排序樹或者是一棵空樹，或者是具有如下性質的二叉樹：(1)、若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值；(2)、若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值；(3)、它的左、右子樹也分別是二叉排序樹。2、二叉排序樹的查找：在二叉排序樹 b 中查找 x 的過程為：(1)、若 b 是空樹，則搜索失敗；否則(2)、若 x 等于 b 的根結點的數據域的值，則查找成功；否則(3)、若 x 小于 b 的根結點的數據域的值，則搜索左子樹；否則(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 中插入一個結點 s 的算法，其過程為：(1)、若 b 是空樹，則將 s 作為根結點插入；否則(2)、若 sA.data 等于 b 的根結點的數據域之值，則返回；否則(3)、若 sA.data 小于 b 的根結點的數據域之值，則把 s 結點

6、插入到左子樹中；否則(4)、把 s 結點插入到右子樹中。向一棵二叉排序樹 b 中插入一個結點 s 的過程如下：procedureinsert(varb:btree;s:btree);beginif(b=nil)thenb:=selseif(sA.dataelseif(sA.databA.data)theninsert(bA.right,s)end;生成二叉排序樹的過程是先有一個空樹 b,然后逐個向該空樹中插入結點實現的。因此根據用戶輸入的一系列正整數(一 1 表示結束)生成一棵二叉排序樹的過程如下：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 中一個數據域為 x 的結點的過程為：(1)、首先查找到數據域為 x 的結點 p(2)、若結點 p 沒有左子樹，則用右子樹的根代替被刪除的結點(3)、若結點 p 有左子樹，則在其左子樹中找到最右結點 r,將 p 的右子樹置為 r 的右子樹，再將 p 的左子樹的根結點代替被刪除的結點 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 個關鍵字組成的序列K1,K2,，Kn,當且僅當滿足下列關系時，稱之為堆。KiK2i、KiK2i、KiK2i+1(稱為最大堆)其中 1=1,2,，Ln/2堆可以看成是對一棵以 K1 為根的完全二叉樹進行按廣度優先遍歷所得到的結點序列。按照堆的定義，在這棵完全二叉樹中，任一結點的值都不大于(或不小于)它的兩個

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

11、部關鍵字有序為止，即完成了堆排序過程。(1)、將以 Ki 為根的子樹建成堆(最小堆為例)：設有關鍵字集合K1,K2,，Kn,若對 I=L+1,L+2,，n 均滿足堆的定義(其中 L=匚 n/2)，現在對 I=L 進行篩選建堆：Proceduresift(L,n:integer;VARheap:ARRAY1.nOFnode);VARI,j:integer;X:node;BeginI:=L;J:=2*I;X:=heapI;Whilejheapj.keyThenBeginHeapI:=heapj;子樹結點上調I:=j;J:=2*I下沉一層endelsej:=n+1;跳出循環end;heapI:=xe

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

13、次輸出的最小關鍵字放在 Kn 的位置上，把第二次輸出的最小關鍵字存放在 Kn-1的位置上，。如此反復執行 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;由上述算法可見，堆排序僅需一個記錄大小的輔助空間供交換使用。堆排序的運行時間主要消耗在初

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

15、div2;End;HeapI:=xEnd;5、最大堆元素的刪除操作：在最大堆中刪除一個元素后，堆的容量減少 1,明顯最后一個元素該取代被刪除元素的位置，取代后還要考慮它和孩子的關系，若大于它的孩子則取代成功，否則它要和它的最大的孩子交換位置，再和新位置的孩子比較大小關系，這樣一直做下去。刪除 I 個元素的過程如下：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 舉例及應用：1、已知圖 a 中的二叉排序樹的各個結點的值分別為 1 至 9,并且各自不相同，請標出各結點的值。解：該二叉樹各結點的值如圖 b 所示。圖(a)圖(b)2、設非空二叉排序樹采用二叉鏈表儲存結構，根結點的指針為 To 請寫一算法，找出該二叉樹中值最小的結點。算法分析：由二叉排序樹的定義可以知道，非空二叉排序樹中值最小的結點是二叉排序樹最左邊那個結點。因此，只須設置一個指針變量，首先令它指向二叉排序樹的根結點，然后讓它沿著它左子樹方向一直找下去，直到某一時刻，該變量所指的結點的左子樹為空，此

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

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