a1數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版)配套課件數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第1頁。a2第6章二叉樹和樹

前面的章節(jié)主要討論的是線性結(jié)構(gòu)，二叉樹和樹屬于非線性的結(jié)構(gòu)。遍歷非線性結(jié)構(gòu)比線性結(jié)構(gòu)要麻煩。二叉樹及樹的遍歷技術(shù)是本章各種算法的核心，而且大多是以遞歸的形式表現(xiàn)的，閱讀和編寫遞歸算法是學(xué)習(xí)本章的難點(diǎn)。講授本章課程大約需8課時(shí)。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第2頁。a3

6.4樹的應(yīng)用

一、堆排序的實(shí)現(xiàn)二、二叉排序樹三、赫夫曼樹及其應(yīng)用數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第3頁。a4一、堆排序的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第4頁。a5堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)復(fù)習(xí)第4章排序數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第5頁。a6rir2ir2i+1

若將該數(shù)列視作完全二叉樹，則r2i

是ri

的左孩子;r2i+1

是

ri

的右孩子。1236276549817355403498例如:是堆14不數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第6頁。a7如何“建堆”？?jī)蓚€(gè)問題:如何“篩選”？定義堆類型為:typedef

SqListHeapType;//堆采用順序表表示之HeapAdjust(.,.,.);數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第7頁。a8

所謂“篩選”指的是，對(duì)一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹也成為一個(gè)堆。

篩選堆堆數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第8頁。a998814973556412362740例如:是大頂堆12但在98

和12

進(jìn)行互換之后，它就不是堆了因此，需要對(duì)它進(jìn)行“篩選”98128173641298比較比較數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第9頁。a10void

HeapAdjust(RcdType&R[],int

s,int

m){//已知R[s..m]中記錄的關(guān)鍵字除R[s]之外均

//滿足堆的特征，本函數(shù)自上而下調(diào)整R[s]的

//關(guān)鍵字，使R[s..m]也成為一個(gè)大頂堆}//HeapAdjustrc=R[s];//暫存R[s]for

(j=2*s;j<=m;j*=2

){//j初值指向左孩子

自上而下的篩選過程;}R[s]=rc;

//將調(diào)整前的堆頂記錄插入到s位置數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第10頁。a11if(rc.key>=R[j].key)break;//再作“根”和“子樹根”之間的比較，

//若“>=”成立，則說明已找到rc的插

//入位置s，不需要繼續(xù)往下調(diào)整R[s]=R[j];s=j;

//否則記錄上移，尚需繼續(xù)往下調(diào)整if(j<m

&&R[j].key<R[j+1].key)++j;//左/右“子樹根”之間先進(jìn)行相互比較

//令j指示關(guān)鍵字較大記錄的位置自上而下的篩選過程的代碼段：數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第11頁。a12

建堆是一個(gè)從下往上進(jìn)行“篩選”的反復(fù)過程40554973816436122798例如:排序之前的關(guān)鍵字序列為123681734998817355

現(xiàn)在，左/右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹是個(gè)“堆”即可。98494064361227數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第12頁。a13voidHeapSort(HeapType&H){

//對(duì)順序表H進(jìn)行堆排序。}

//HeapSortfor

(i=H.length/2;i>0;--i)

//建大頂堆

HeapAdjust(H.r,i,H.length);

for(i=H.length;i>1;--i)

{//調(diào)整堆來實(shí)現(xiàn)排序

H.r[1]←→H.r[i];

//將堆頂記錄和當(dāng)前未經(jīng)排序子序列//H.r[1..i]中最后一個(gè)記錄相互交換

HeapAdjust(H.r,1,i-1);

//對(duì)H.r[1]進(jìn)行篩選}數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第13頁。a1412345678910405549731227988164363612738181559849557340984049

堆排序的邏輯結(jié)構(gòu)是一棵完全二叉樹，而實(shí)現(xiàn)的空間則是順序表。以數(shù)據(jù)模型演示數(shù)據(jù)在順序空間的動(dòng)態(tài)變化。初始堆的建立過程：初始堆的建立過程有比較大的消耗，可達(dá)4n數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第14頁。a15堆排序第一趟：1234567891098814973362740556412129881127312641281堆排序第二趟：123456789108173496436274055121298128112731264125573堆排序第三趟：1234567891073644955362740128112988173121264125564可以看出，每趟的調(diào)整只牽涉少量的數(shù)據(jù)……

有序段數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第15頁。a16堆排序的時(shí)間復(fù)雜度分析(建堆+

n-1

次調(diào)整)：

以后的每次調(diào)整，耗費(fèi)將顯著減少。因?yàn)檫@樣調(diào)整所耗用的比較操作次數(shù)都不超過堆的樹深，是一種消耗很少的局部調(diào)整。

初始堆的建立過程:O(n)建成深度為

h=(log2n+1)的堆,需要調(diào)整n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過

2*(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)

因此，堆排序的時(shí)間復(fù)雜度為O(nlogn)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第16頁。a17二、二叉排序樹

數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第17頁。a18（1）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；1．二叉排序的定義：

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（3）它的左、右子樹也都分別是二叉排序樹。（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第18頁。a19503080209010854035252388例如:是二叉排序樹。66不數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第19頁。a20（49，38，65，76，49，13，27，52）4938657649132752構(gòu)造二叉排序樹

構(gòu)建二叉排序樹的過程，是一個(gè)從空樹起不斷插入結(jié)點(diǎn)的過程。每插入一個(gè)結(jié)點(diǎn)都應(yīng)保證遵從二叉排序樹的定義。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第20頁。a21（，，，，，，，）1327384949526576（49，38，65，76，49，13，27，52）原始序列數(shù)據(jù)4938657649132752構(gòu)造的二叉排序樹中序遍歷二叉排序樹

如果中序遍歷二叉排序樹，所得序列將是有序的，即實(shí)現(xiàn)了對(duì)原始數(shù)據(jù)的排序，二叉排序樹即由此得名。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第21頁。a22

有關(guān)二叉排序樹更詳細(xì)的討論及算法，請(qǐng)見第8章查找表的二叉查找樹一節(jié)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第22頁。a23三、赫夫曼樹及其應(yīng)用最優(yōu)樹的定義如何構(gòu)造最優(yōu)樹前綴編碼數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第23頁。a24

最優(yōu)樹的定義樹的路徑長(zhǎng)度定義為：

樹中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。

結(jié)點(diǎn)的路徑長(zhǎng)度定義為：

從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第24頁。a25

樹的帶權(quán)路徑長(zhǎng)度定義為：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和

WPL(T)=wklk(對(duì)所有葉子結(jié)點(diǎn))。

在所有含n個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的m叉樹中,必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的樹，稱為“最優(yōu)樹”。例如：數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第25頁。a2627975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第26頁。a27

根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合

F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空樹；如何構(gòu)造最優(yōu)樹(1)(赫夫曼算法)以二叉樹為例：數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第27頁。a28

在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；(2)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第28頁。a29

從F中刪去這兩棵樹，同時(shí)加入剛生成的新樹；

重復(fù)(2)

和(3)

兩步，直至F中只含一棵樹為止。(3)(4)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第29頁。a309例如:已知權(quán)值W={

5,6,2,9,7

}562752769767139527數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第30頁。a316713952795271667132900001111000110110111數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第31頁。a32

指的是，任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。前綴編碼

利用赫夫曼樹可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第32頁。a33出現(xiàn)頻度:5,6,2,9,7編碼:

101,00,100,11,01字母集:

s,t,a,e,i電文:eat編碼:eat111000025701100101911160167130100012901tiase譯電文:eat

符合前綴編碼規(guī)則才能按唯一性進(jìn)行譯碼數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第33頁。a34本章學(xué)習(xí)要點(diǎn)數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第34頁。a35

1.熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)性質(zhì)的證明方法。

2.熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。

3.遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第35頁。a36

4.理解二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟悉二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對(duì)二叉樹進(jìn)行遍歷，而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第36頁。a37

5.熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握1至2種建立二叉樹和樹的存儲(chǔ)結(jié)構(gòu)的方法。

6.學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。

7.深刻理解二叉排序樹的定義及特性。

8.熟練掌握堆排序的算法。

9.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第37頁。a38習(xí)題解答實(shí)例數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第38頁。a39

算法設(shè)計(jì)題6-20

將二叉排序樹輸出到一個(gè)空的循環(huán)鏈表，要求：（1）使鏈表結(jié)點(diǎn)的值按降序排列；（2）使鏈表結(jié)點(diǎn)的值按升序排列。

按中序遍歷二叉排序樹，可以得到按升序排列的輸出。如果從鏈表的前部逐一插入就得到降序排列。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第39頁。a40void

degression(BSTreeT,LinkList&head)

{if（T）{

degression(T->lchild);

degression(T->rchild);

}}new(s);s->data=T->data;s->next=head->next;head->next=s;s13head38（1）使鏈表結(jié)點(diǎn)的值按降序排列算法：

插入結(jié)點(diǎn)的指針操作數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第40頁。a4149387613401313381338401338404976133840491338407649降序排列的動(dòng)態(tài)模型演示數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第41頁。a42

要利用從前部插入操作操作簡(jiǎn)單的優(yōu)點(diǎn)，又要得到升序排列的結(jié)構(gòu)，就要求輸出的序列本身為降序。只需在中序遍歷二叉排序樹時(shí)改變“先左后右”的次序，按“先右后左”進(jìn)行遍歷。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第42頁。a43void

increase(BSTreeT,LinkList&head)

{if（T）{

increase();

new(s);s->data=T->data;s->next=head->next;head->next=s;

increase();

}}T->rchildT->lchild

調(diào)換了遍歷的次序（2）使鏈表結(jié)點(diǎn)的值按升序排列算法：數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第43頁。a4449387613407676497649407649403813764940387649401338升序排列的動(dòng)態(tài)模型演示數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第44頁。a45

算法設(shè)計(jì)題6-24

以廣義表的字符串的形式輸出“孩子-兄弟鏈表”作存儲(chǔ)結(jié)構(gòu)的樹。

前序遍歷“孩子-兄弟鏈表”表示的樹，在該算法中的適當(dāng)位置加入輸出“（”、“）”和“，”的語句，即可實(shí)現(xiàn)廣義表的字符串的形式輸出。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第45頁。a46ABCDEGFFABCDEFHGvoidpreOrderTree(CSTreeT)

{

if

(T)

{

visit(T);

//訪問當(dāng)前的根結(jié)點(diǎn)

for(p=T->firstchild;p;p=p->nextsibling)

preOrderTree(p);

}}存儲(chǔ)表示為“孩子-兄弟鏈表”樹的前序遍歷數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版全文共49頁，當(dāng)前為第46頁。a47voidoutputTree(CSTreeT){

if(T){printf("%c",T->data);//輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域值

if(T->firstchild){

printf("(");//左孩子不空打印左括弧“（”

for(p=T->firstchild;p;