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

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