1、主要教學目標：了解查找樹，掌握堆和堆排序的過程和算法；掌握平衡樹的構造原理；掌握建立哈夫曼樹和哈夫曼編碼的方法。教學方法及教學手段：理論講授與上機實踐相結合教學重點及難點：建堆，堆排序，構造平衡樹，構造哈夫曼樹第六章 樹的查找和樹的應用6.1 查找樹定義查找樹，或是一棵空樹，或具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值若它的右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值它的左、右子樹也分別為二叉排序樹二叉排序樹的插入插入原則：若二叉排序樹為空，則插入結點應為新的根結點；否則，繼續(xù)在其左、右子樹上查找，直至某個葉子結點的左子樹或右子樹為空為止

2、，則插入結點應為該葉子結點的左孩子或右孩子二叉排序樹生成：從空樹出發(fā)，經過一系列的查找、插入操作之后，可生成一棵二叉排序樹例 10， 18， 3， 8， 12， 2， 7， 31010181018310183810183812101838122101838122710183812273中序遍歷二叉排序樹可得到一個關鍵字的有序序列查找樹的刪除要刪除查找樹中的p結點，分三種情況：p為葉子結點，只需修改p雙親f的指針f-lchild=NULL f-rchild=NULLp只有左子樹或右子樹p只有左子樹，用p的左孩子代替p (1)(2)p只有右子樹，用p的右孩子代替p (3)(4)p左、右子樹均非空沿

3、p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹成為S的雙親Q的右子樹，用S取代p (5)若C無右子樹，用C取代p (6)SQPLP中序遍歷：Q S PL PSQPL中序遍歷：Q S PL(2)SPPLQ中序遍歷：PL P S QSPLQ中序遍歷：PL S Q(1)中序遍歷：P PR S QSPRQ中序遍歷：PR S Q(3)SPPRQ中序遍歷：Q S P PRSQPR中序遍歷：Q S PR(4)SQPRPFPCPRCLQQLSSL中序遍歷：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍歷：CL C QL Q SL S PR F(5)FPCPRCL中序遍

4、歷：CL C P PR FFCPRCL中序遍歷：CL C PR F(6)例805012060110150557053刪除508060120110150557053刪除60805512011015053701042581354刪除1084255134刪除584254131042581354刪除1084255134刪除5842541330 78 53 6 18 10 11 20 4947 15 34 56 90 61 5 20 87 416.2 滿樹、擬滿樹和豐滿樹定義滿樹：每層結點數達到最大個數擬滿樹：深度為k的二叉樹，前k-1層是滿樹，第k層從左到右依次排列豐滿樹：深度為k的二叉樹，前k-1層

5、是滿樹，第k層任意排列6.3 堆和堆排序堆的定義：n個元素的序列(k1,k2,kn)，當且僅當滿足下列關系時，稱之為堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）962791138831327384965765097可將堆序列看成擬滿樹，則堆頂元素（擬滿樹的根）必為序列中n個元素的最小值或最大值堆排序：將無序序列建成一個堆，得到關鍵字最?。ɑ蜃畲螅┑挠涗?；輸出堆頂的最小（大）值后，使剩余的n-1個元素重又建成一個堆，則可得到n個元素的次小值；重復執(zhí)行，得到一個有序序列，這

6、個過程叫堆排序需解決的兩個問題：如何由一個無序序列建成一個堆？如何在輸出堆頂元素之后，調整剩余元素，使之成為一個新的堆？第二個問題解決方法篩選方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結點值與左、右子樹的根結點值進行比較，并與其中小者進行交換；重復上述操作，直至葉子結點，將得到新的堆，稱這個從堆頂至葉子的調整過程為“篩選”例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13 273849502765769713輸出：13 276549502738769713輸出：13 2

7、7 384965502738769713輸出：13 27 387665502738499713輸出：13 27 38 495065762738499713輸出：13 27 38 499765762738495013輸出：13 27 38 49 506597762738495013輸出：13 27 38 49 509765762738495013輸出：13 27 38 49 50 657665972738495013輸出：13 27 38 49 50 659765762738495013輸出：13 27 38 49 50 65 769765762738495013輸出：13 27 38 49 5

8、0 65 76 97第一個問題解決方法方法：構造一棵擬滿樹，從最后一個根開始調整成堆結構，直至到根例 含8個元素的無序序列（49，38，65，97，76，13，27，50）496538271376975049653827137650974913382765765097491338276576509713273849657650976.4 平衡樹定義樹的高度 設T是一棵二叉樹,h(T)表示樹T的高度.則 h(T)=maxh(Tl,Tr)+1平衡度(k)=h(Tkr)-h(Tkl)平衡樹 二叉樹中每個結點k都有|(k)= |1平衡查找樹 樹T既是查找樹,又是平衡樹 1、按查找樹插入2、調整LL型

9、新結點插入a結點的左孩子b的左子樹中，使a失去平衡，則 ，其余結點按查找樹調整abba1、按查找樹插入2、調整RR型 新結點插入a結點的右孩子b的右子樹中，使a失去平衡，則 ，其余結點按查找樹調整abba1、按查找樹插入2、調整LR型 新結點插入a結點的左孩子b的右子樹中，使a失去平衡，則 ，其余結點按查找樹調整abb的右孩子ab1、按查找樹插入2、調整RL型 新結點插入a結點的右孩子b的左子樹中，使a失去平衡，則 ，其余結點按查找樹調整abb的左孩子ba例：按G,F,A,D,C,E,B的順序構造一棵平衡查找樹G0G-1F0G-2F-1A0A1F-1D0G0F0A0G0A2F-2D-1G0C0

10、F-1C0G0A0D0例：按G,F,A,D,C,E,B的順序構造一棵平衡查找樹F-2C1G0A0D1E0D0C-1A0F0E0G0D-1C-2A1F0E0G0B0C0A0B0F0E0G0D06.5 最佳查找樹Cij=Wij+Cik-1+Ckj=Wij+minCit-1+Ctj (ik j)Wij=Wij-1+pj+qj其中,Cii=0,rii=0,Wii=qi則左子樹Tlij=Tit，右子樹Trij=Ttj，rij=kit j6.6 二叉樹的應用哈夫曼樹(Huffman)帶權路徑長度最短的樹定義路徑：從樹中一個結點到另一個結點之間的分支構成這兩個結點間的路徑長度：路徑上的分支數樹的路徑長度：從

11、樹根到每一個結點的路徑長度之和樹的帶權路徑長度：樹中所有帶權結點的路徑長度之和Huffman樹設有n個權值w1,w2,wn，構造一棵有n個葉子結點的二叉樹，每個葉子的權值為wi,則wpl最小的二叉樹叫例 有4個結點，權值分別為7，5，2，4，構造有4個葉子結點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35構造Huffman樹的方法Huffman算法構造Huffman樹步驟根據給定的n個權值w1,w2,wn，構造n棵只有根結點的二叉樹，令起權值為wj在森林

12、中選取兩棵根結點權值最小的樹作左右子樹，構造一棵新的二叉樹，置新二叉樹根結點權值為其左右子樹根結點權值之和在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中重復上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例 w=5, 29, 7, 8, 14, 23, 3, 115142978233111429782311358871514292335811113581914292387151135819292314871529291487152911358192342113581923422914871529581135

13、8192342291487152958100lc data rc pa1 2 3 4 5 6 70 0 0 0 0 0 07 5 2 4 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0(1)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 0 07 5 2 4 6 0 00 0 0 0 4 0 00 0 5 5 0 0 0kx1=3,x2=4m1=2,m2=4(2)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 07 5 2 4 6 11 00 0 0 0 4 5 00 6 5 5 6 0 0kx1=2,x2=5m1=5,m2=

14、6(3)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 17 5 2 4 6 11 180 0 0 0 4 5 67 6 5 5 6 7 0kx1=1,x2=6m1=7,m2=11(4)Huffman樹應用最佳判定樹等級分數段比例ABCDE059606970798089901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60a90EYNDYNCYNBYNAHuffman編碼：數據通信用的二進制編碼思想：根據字符出現頻率編碼，使電文總長

15、最短編碼：根據字符出現頻率構造Huffman樹，然后將樹中結點引向其左孩子的分支標“0”，引向其右孩子的分支標“1”；每個字符的編碼即為從根到每個葉子的路徑上得到的0、1序列例 要傳輸的字符集 D=C,A,S,T, ; 字符出現頻率 w=2,4,2,3,3CS3364224814T;A00110110T : 00; : 01A : 10C : 110S : 111譯碼：從Huffman樹根開始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編碼是“1”，則向右走，一旦到達葉子結點，則譯出一個字符；再重新從根出發(fā)，直到電文結束例 電文是CAS;CAT;SAT;AT 其編碼 “110101110111010000111