數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程修訂版.ppt

1,數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版),配套課件,2,第6章 二叉樹(shù)和樹(shù),前面的章節(jié)主要討論的是線性結(jié)構(gòu)，二叉樹(shù)和樹(shù)屬于非線性的結(jié)構(gòu)。遍歷非線性結(jié)構(gòu)比線性結(jié)構(gòu)要麻煩。 二叉樹(shù)及樹(shù)的遍歷技術(shù)是本章各種算法的核心，而且大多是以遞歸的形式表現(xiàn)的，閱讀和編寫(xiě)遞歸算法是學(xué)習(xí)本章的難點(diǎn)。 講授本章課程大約需8課時(shí)。,3,6.4 樹(shù)的應(yīng)用,一、堆排序的實(shí)現(xiàn) 二、二叉排序樹(shù) 三、赫夫曼樹(shù)及其應(yīng)用,4,一、堆排序的實(shí)現(xiàn),5,堆是滿足下列性質(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章排序,6,ri,r2i,r2i+1,若將該數(shù)列視作完全二叉樹(shù)， 則 r2i 是 ri 的左孩子; r2i+1 是 ri 的右孩子。,12,36,27,65,49,81,73,55,40,34,98,例如:,是堆,14,不,7,如何“建堆”？,兩個(gè)問(wèn)題:,如何“篩選”？,定義堆類(lèi)型為:,typedef SqList HeapType; / 堆采用順序表表示之,HeapAdjust (., ., .);,8,所謂“篩選”指的是，對(duì)一棵左/右子樹(shù) 均為堆的完全二叉樹(shù)，“調(diào)整”根結(jié)點(diǎn) 使整個(gè)二叉樹(shù)也成為一個(gè)堆。,篩選,9,98,81,49,73,55,64,12,36,27,40,例如:,是大頂堆,12,但在 98 和 12 進(jìn)行互換之后，它就不是堆了,因此，需要對(duì)它進(jìn)行“篩選”,98,12,81,73,64,12,98,比較,比較,10,void HeapAdjust (RcdType &R, int s, int m) / 已知 Rsm中記錄的關(guān)鍵字除 Rs 之外均 / 滿足堆的特征，本函數(shù)自上而下調(diào)整 Rs 的 / 關(guān)鍵字，使 Rsm 也成為一個(gè)大頂堆 / HeapAdjust,rc = Rs; / 暫存 Rs,for ( j=2*s; j=m; j*=2 ) / j 初值指向左孩子 自上而下的篩選過(guò)程; ,Rs = rc; / 將調(diào)整前的堆頂記錄插入到 s 位置,11,if ( rc.key = Rj.key ) break; / 再作“根”和“子樹(shù)根”之間的比較， / 若“=”成立，則說(shuō)明已找到 rc 的插 / 入位置 s ，不需要繼續(xù)往下調(diào)整,Rs = Rj; s = j; / 否則記錄上移，尚需繼續(xù)往下調(diào)整,if ( jm / 左/右“子樹(shù)根”之間先進(jìn)行相互比較 / 令 j 指示關(guān)鍵字較大記錄的位置,自上而下的篩選過(guò)程的代碼段：,12,建堆是一個(gè)從下往上進(jìn)行“篩選”的反復(fù)過(guò)程,40,55,49,73,81,64,36,12,27,98,例如: 排序之前的關(guān)鍵字序列為,12,36,81,73,49,98,81,73,55,現(xiàn)在，左/右子樹(shù)都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹(shù)是個(gè)“堆”即可。,98,49,40,64,36,12,27,13,void HeapSort ( HeapType &H ) / 對(duì)順序表 H 進(jìn)行堆排序。 / HeapSort,for ( i=H.length/2; i0; -i ) / 建大頂堆 HeapAdjust ( H.r, i, H.length );,for ( i=H.length; i1; -i ) / 調(diào)整堆來(lái)實(shí)現(xiàn)排序 H.r1H.ri; / 將堆頂記錄和當(dāng)前未經(jīng)排序子序列 / H.r1i中最后一個(gè)記錄相互交換 HeapAdjust(H.r, 1, i-1); / 對(duì) H.r1 進(jìn)行篩選 ,14,堆排序的邏輯結(jié)構(gòu)是一棵完全二叉樹(shù)，而實(shí)現(xiàn)的空間則是順序表。以數(shù)據(jù)模型演示數(shù)據(jù)在順序空間的動(dòng)態(tài)變化。,初始堆的建立過(guò)程：,初始堆的建立過(guò)程有比較大的消耗，可達(dá)4n,15,堆排序第一趟：,81,堆排序第二趟：,73,堆排序第三趟：,64,可以看出，每趟的調(diào)整只牽涉少量的數(shù)據(jù),16,堆排序的時(shí)間復(fù)雜度分析( 建堆+ n-1 次調(diào)整)：,以后的每次調(diào)整，耗費(fèi)將顯著減少。因?yàn)檫@樣調(diào)整所耗用的比較操作次數(shù)都不超過(guò)堆的樹(shù)深，是一種消耗很少的局部調(diào)整。,初始堆的建立過(guò)程:O (n),建成深度為 h = (log2n+1) 的堆,需要調(diào)整n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過(guò) 2*(log2(n-1)+ log2(n-2)+ +log22) 2n(log2n),因此，堆排序的時(shí)間復(fù)雜度為O(nlogn),17,二、二叉排序樹(shù),18,（1）若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；,1二叉排序的定義：,二叉排序樹(shù)或者是一棵空樹(shù)；或者是具有如下特性的二叉樹(shù)：,（3）它的左、右子樹(shù)也都分別是二叉排序樹(shù)。,（2）若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；,19,50,30,80,20,90,10,85,40,35,25,23,88,例如:,是二叉排序樹(shù)。,66,不,20,（49，38，65，76，49，13，27，52）,構(gòu)造二叉排序樹(shù),構(gòu)建二叉排序樹(shù)的過(guò)程，是一個(gè)從空樹(shù)起不斷插入結(jié)點(diǎn)的過(guò)程。每插入一個(gè)結(jié)點(diǎn)都應(yīng)保證遵從二叉排序樹(shù)的定義。,21,（ ， ， ， ， ， ， ， ）,13,27,38,49,49,52,65,76,中序遍歷二叉排序樹(shù),如果中序遍歷二叉排序樹(shù)，所得序列將是有序的，即實(shí)現(xiàn)了對(duì)原始數(shù)據(jù)的排序，二叉排序樹(shù)即由此得名。,22,有關(guān)二叉排序樹(shù)更詳細(xì)的討論及算法，請(qǐng)見(jiàn)第8章查找表的二叉查找樹(shù)一節(jié),23,三、赫夫曼樹(shù)及其應(yīng)用,最優(yōu)樹(shù)的定義 如何構(gòu)造最優(yōu)樹(shù) 前綴編碼,24,最優(yōu)樹(shù)的定義,樹(shù)的路徑長(zhǎng)度定義為： 樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。,結(jié)點(diǎn)的路徑長(zhǎng)度定義為： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上 分支的數(shù)目。,25,樹(shù)的帶權(quán)路徑長(zhǎng)度定義為： 樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 WPL(T) = wklk (對(duì)所有葉子結(jié)點(diǎn))。,在所有含 n 個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán) 值的 m 叉樹(shù)中, 必存在一棵其帶權(quán)路徑 長(zhǎng)度取最小值的樹(shù)，稱為“最優(yōu)樹(shù)”。,例如：,26,2,7 9,7,5,4,9,2,WPL(T)= 72+52+23+43+92 =60,WPL(T)= 74+94+53+42+21 =89,5,4,27,根據(jù)給定的 n 個(gè)權(quán)值 w1, w2, , wn， 構(gòu)造 n 棵二叉樹(shù)的集合 F = T1, T2, , Tn， 其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值 為 wi 的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù)；,如何構(gòu)造最優(yōu)樹(shù),(1),(赫夫曼算法) 以二叉樹(shù)為例：,28,在 F 中選取其根結(jié)點(diǎn)的權(quán)值為最小 的兩棵二叉樹(shù)，分別作為左、右子 樹(shù)構(gòu)造一棵新的二叉樹(shù)，并置這棵 新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、 右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；,(2),29,從F中刪去這兩棵樹(shù)，同時(shí)加入 剛生成的新樹(shù)；,重復(fù) (2) 和 (3) 兩步，直至 F 中只 含一棵樹(shù)為止。,(3),(4),30,9,例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 ,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,31,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,32,指的是，任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。,前綴編碼,利用赫夫曼樹(shù)可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短。,33,出現(xiàn)頻度: 5, 6, 2, 9, 7,編碼: 101, 00, 100, 11, 01,字母集: s, t, a, e, i,電文: eat,編碼 : e a t,11,100,00,譯電文: eat,符合前綴編碼規(guī)則才能按唯一性進(jìn)行譯碼,34,本章學(xué)習(xí)要點(diǎn),35,1. 熟練掌握二叉樹(shù)的結(jié)構(gòu)特性，了解相應(yīng)性質(zhì)的證明方法。 2. 熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。 3. 遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。,36,4. 理解二叉樹(shù)線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟悉二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹(shù)的線索化過(guò)程是基于對(duì)二叉樹(shù)進(jìn)行遍歷，而線索二叉樹(shù)上的線索又為相應(yīng)的遍歷提供了方便。,37,5. 熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握 1 至 2 種建立二叉樹(shù)和樹(shù)的存儲(chǔ)結(jié)構(gòu)的方法。 6. 學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法。 7. 深刻理解二叉排序樹(shù)的定義及特性。 8. 熟練掌握堆排序的算法。 9.了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和哈夫曼編碼的方法。,38,習(xí)題解答實(shí)例,39,算法設(shè)計(jì)題6-20 將二叉排序樹(shù)輸出到一個(gè)空的循環(huán)鏈表，要求： （1）使鏈表結(jié)點(diǎn)的值按降序排列； （2）使鏈表結(jié)點(diǎn)的值按升序排列。,按中序遍歷二叉排序樹(shù)，可以得到按升序排列的輸出。如果從鏈表的前部逐一插入就得到降序排列。,40,void degression (BSTree T, LinkList ,new(s); s-data = T -data; s-next = head-next; head-next = s;,38,（1）使鏈表結(jié)點(diǎn)的值按降序排列算法：,插入結(jié)點(diǎn)的指針操作,41,49,38,13,40,13,38,40,76,49,降序排列的動(dòng)態(tài)模型演示,42,要利用從前部插入操作操作簡(jiǎn)單的優(yōu)點(diǎn)，又要得到升序排列的結(jié)構(gòu)，就要求輸出的序列本身為降序。只需在中序遍歷二叉排序樹(shù)時(shí)改變“先左后右”的次序，按“先右后左”進(jìn)行遍歷。,43,void increase (BSTree T, LinkList ,T -rchild,T -lchild,調(diào)換了遍歷的次序,（2）使鏈表結(jié)點(diǎn)的值按升序排列算法：,44,49,38,13,40,76,49,40,13,38,升序排列的動(dòng)態(tài)模型演示,45,算法設(shè)計(jì)題6-24 以廣義表的字符串的形式輸出“孩子-兄弟鏈表”作存儲(chǔ)結(jié)構(gòu)的樹(shù)。,前序遍歷“孩子-兄弟鏈表”表示的樹(shù)，在該算法中的適當(dāng)位置加入輸出“（”、“）”和“，”的語(yǔ)句，即可實(shí)現(xiàn)廣義表的字符串的形式輸出。,46,A,B,C,D,E,G,F,F,void preOrderTree (CSTree T) if (T) visit (T); / 訪問(wèn)當(dāng)前的根結(jié)點(diǎn) for (p= T-firstchild; p; p= p-nextsibling ) preOrderTree (p); ,存儲(chǔ)表示為“孩子-兄弟鏈表” 樹(shù)的前序遍歷,47,void outputTree (CSTree T) if (T) printf(“%c“,T-data); / 輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域值 if (T-firstchild) printf(“(“); / 左孩子不空打印左括弧“（” for(p= T-firstchild; p; p=