數(shù)據(jù)結(jié)構(gòu)課件：10 第四章 樹3[新]

1、4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應(yīng)用第四章 樹4.4.1樹與二叉樹的轉(zhuǎn)換4.4.2樹的順序存儲(chǔ)4.4.3樹的鏈接存儲(chǔ)4.4.4樹和森林的遍歷4.4 樹和森林4.4.1樹與二叉樹的轉(zhuǎn)換 1) 樹轉(zhuǎn)換成二叉樹 2) 森林轉(zhuǎn)換成二叉樹 3) 二叉樹轉(zhuǎn)換成樹 4) 二叉樹轉(zhuǎn)換成森林1）樹轉(zhuǎn)換成二叉樹 所有兄弟結(jié)點(diǎn)之間加一線； 對(duì)每個(gè)結(jié)點(diǎn)，除了保留與其長(zhǎng)子的連線外，去掉該結(jié)點(diǎn)與其他孩子的連線。 按順時(shí)針方向?qū)⑺D(zhuǎn)45。 ACBFDEACBFDE樹由樹轉(zhuǎn)換的二叉樹 把森林中第一棵樹T1的根作為整個(gè)森林的根； 把森林中其它樹的根依次作為T1的兄弟結(jié)點(diǎn)

2、。2）森林轉(zhuǎn)換成二叉樹 二叉樹GJHIFEACBDACBDFEGJHI3)二叉樹轉(zhuǎn)換成樹ACBFDE由二叉樹轉(zhuǎn)換的樹ACBFDE二叉樹 GJHIFEACBDACBDFEGJHI4）二叉樹轉(zhuǎn)成森林4.4.1樹與二叉樹的轉(zhuǎn)換4.4.2樹的順序存儲(chǔ)4.4.3樹的鏈接存儲(chǔ)4.4.4樹和森林的遍歷4.4 樹和森林樹的順序存儲(chǔ)結(jié)構(gòu)1)先根序列及結(jié)點(diǎn)次數(shù)表示法2)后根序列及結(jié)點(diǎn)次數(shù)表示法3)層次序列及結(jié)點(diǎn)次數(shù)表示法4)層次序列及Father數(shù)組表示法1) 樹的先根序列及結(jié)點(diǎn)次數(shù)表示法樹的先根遍歷的定義（1）訪問根結(jié)點(diǎn)（2）從左到右依次先根次序遍歷樹的諸子樹RADEFCBGKH先根序列RADEBCFGHK定理

3、4.2 如果已知一個(gè)樹的先根序列和每個(gè)結(jié)點(diǎn)相應(yīng)的次數(shù)，則能唯一確定該樹的結(jié)構(gòu)。證明：用數(shù)學(xué)歸納法1. 若樹中只有一個(gè)結(jié)點(diǎn)，定理顯然成立。2. 假設(shè)樹中結(jié)點(diǎn)個(gè)數(shù)小于n(n2)時(shí)定理成立。3. 當(dāng)樹中有n個(gè)結(jié)點(diǎn)時(shí)，由樹的先根序列可知，第一個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)的次數(shù)為k, k1，因此根結(jié)點(diǎn)有k個(gè)子樹。第一個(gè)子樹排在最前面，第k個(gè)子樹排在最后面，并且每個(gè)子樹的結(jié)點(diǎn)個(gè)數(shù)小于n，由歸納假設(shè)可知，每個(gè)子樹可以唯一確定，從而整棵樹的樹形可以唯一確定。證畢。 例：先根序列： A B C D E F G H I J K L 結(jié)點(diǎn)的次數(shù): 4 0 3 0 0 0 0 2 2 0 0 0 2) 后根序列和結(jié)點(diǎn)次數(shù)

4、表示法后根序列 B D E F C G J K I L H A結(jié)點(diǎn)的次數(shù) 0 0 0 0 3 0 0 0 2 0 2 43) 層次序列和結(jié)點(diǎn)次數(shù)表示法已知一個(gè)樹的層次序列和每個(gè)結(jié)點(diǎn)次數(shù)，則能唯一確定該樹的結(jié)構(gòu)。層次序列 A B C D E F結(jié)點(diǎn)的次數(shù) 3 0 2 0 0 04) 層次序列和Father數(shù)組表示法便于涉及祖先的操作，求結(jié)點(diǎn)的孩子時(shí)需要遍歷整棵樹。4.4.1樹與二叉樹的轉(zhuǎn)換4.4.2樹的順序存儲(chǔ)4.4.3樹的鏈接存儲(chǔ)4.4.4樹和森林的遍歷4.4 樹和森林 (1) Father鏈接結(jié)構(gòu):ACBFDEACBDFEFather鏈接提供了“向上”訪問的能力，但很難確定一個(gè)結(jié)點(diǎn)是否為葉結(jié)

5、點(diǎn)，也很難求結(jié)點(diǎn)的子結(jié)點(diǎn)，且不易實(shí)現(xiàn)遍歷操作。(2)孩子鏈接結(jié)構(gòu)*會(huì)出現(xiàn)大量指針為空的情況，浪費(fèi)空間。 *節(jié)省了空間，但給操作和管理帶來不便。(3)孩子鏈表表示法*孩子鏈表表示法是為樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈表，并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)數(shù)組中。孩子結(jié)點(diǎn)的數(shù)據(jù)域僅存放了它們?cè)跀?shù)組空間的下標(biāo)。*與Father鏈接表示法相反，孩子鏈表表示便于實(shí)現(xiàn)涉及孩子及其子孫的運(yùn)算，但不便于實(shí)現(xiàn)與父結(jié)點(diǎn)有關(guān)的操作。 (4)父親孩子鏈表表示*將Father數(shù)組表示法和孩子鏈表表示法結(jié)合起來，可形成父親孩子鏈表表示法。 結(jié)點(diǎn)結(jié)構(gòu)firstChildnextBrotherData(5)左孩子-右兄

6、弟鏈接結(jié)構(gòu)（二叉樹表示法）*這種存儲(chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是：它和二叉樹的二叉鏈表表示完全一樣?？衫枚鏄涞乃惴▉韺?shí)現(xiàn)對(duì)樹的操作。RADEFCBGKHRADECHFGBK左孩子-右兄弟表示法示例：樹的左孩子右兄弟表示法的實(shí)現(xiàn)結(jié)點(diǎn)類TreeNodetemplate class TreeNode friend class Tree ; private: T data ; TreeNode *firstChild，*nextBrother ; pulic: TreeNode(T value , TreeNode*L, TreeNode *R ) / 構(gòu)造函數(shù) TreeNode( ) ；樹類Tree的聲明t

7、emplateclass Tree private : TreeNode *root ;/ 根結(jié)點(diǎn) public : Tree ( ); / 構(gòu)造函數(shù) Tree ( ); / 析構(gòu)函數(shù) TreeNode * FirstChild (TreeNode *p); /返回結(jié)點(diǎn)p的大兒子結(jié)點(diǎn) TreeNode * NextBrother ( TreeNode *p); /返回結(jié)點(diǎn)p的下一個(gè)兄弟結(jié)點(diǎn) TreeNode * FindFather ( TreeNode *t , TreeNode *p ); /在樹t中搜索p的父結(jié)點(diǎn)TreeNode * FindTarget ( TreeNode *t ,

8、T target ); /在樹t中搜索值為target的結(jié)點(diǎn) void DelSubtree ( TreeNode *t ,TreeNode *p ); /在樹t中刪除以p為根的子樹 void Del ( TreeNode *p ); void PreOrder (TreeNode * t); /先根遍歷以t為根結(jié)點(diǎn)的樹 void NorecPreOrder (TreeNode * t ); /非遞歸先根遍歷以t為根結(jié)點(diǎn)的樹 void LevelOrder ( TreeNode * t ); /層次遍歷以t為根結(jié)點(diǎn)的樹 ;FindFather(t, p)算法思想：令q指向t的大兒子結(jié)點(diǎn)，若q=

9、p，t就是p的父結(jié)點(diǎn)；否則，在以q為根的子樹中找p的父結(jié)點(diǎn)，即 FindFather(q,p);若未找到，令q指向t的下一個(gè)兒子結(jié)點(diǎn)，即q的右兄弟結(jié)點(diǎn)，重復(fù)上述步驟，直至找到p的父結(jié)點(diǎn)或找完t的所有兒子結(jié)點(diǎn)。 搜索父結(jié)點(diǎn) 算法FindFather( t, p. result)FF1尋找t的第一棵子樹 IF t OR p THEN RETURN result ELSE qFistChild (t).FF2從t的第一棵子樹開始搜索，若搜索到，則返回；否則，搜索t的下一棵子樹 WHILE q AND qp DO ( FindFather( q , p. result) IF result THEN

10、qNextBrother(q) ELSE RETURN result . )FF3遞歸出口：若p是t的一個(gè)子結(jié)點(diǎn)，令指針 result 指向t IF q p THEN RETURN result t . ELSE RETURN result . ACBFDEACBFDEFindTarget (t , target )算法思想：若t的數(shù)據(jù)域?yàn)閠arget，則指針result指向t；否則，p指向t的大兒子結(jié)點(diǎn)，在以p為根的樹中進(jìn)行搜索(遞歸調(diào)用)若在以p為根的樹中搜索失敗，p指向其右兄弟結(jié)點(diǎn)，繼續(xù)進(jìn)行上述搜索，直到找到數(shù)據(jù)域等于target的結(jié)點(diǎn)或p為空。 搜索指定數(shù)據(jù)域的結(jié)點(diǎn)算法FindTarg

11、et(t, target. result)FT1t不存在或?yàn)樗?IF t THEN RETURN result . IF Data (t) target THEN ( RETURN result t . )FT2從t的第一棵子樹開始搜索 p FistChild ( t ) . WHILE p DO ( FindTarget (p , target. result). IF result THEN pNextBrother( p ) ELSE RETURN result . )FT3在以t為根的樹中，沒有搜索到數(shù)據(jù)成員等于target的結(jié)點(diǎn) RETURN result . 搜索大兒子結(jié)點(diǎn)和大兄

12、弟結(jié)點(diǎn)算法GFC(p. q)GFC1. 指針p所指結(jié)點(diǎn)存在，并且存在大兒子結(jié)點(diǎn) IF p AND FistChild (p ) THEN RETURN q FistChild (p ) . GFC2. 大兒子結(jié)點(diǎn)不存在 RETURN q . 算法GNB ( p . q )GNB1. 指針p所指結(jié)點(diǎn)存在，并且存在下一個(gè)兄弟結(jié)點(diǎn) IF p AND NextBrother (p ) THEN RETURN q NextBrother (p ). GNB2. 大兒子結(jié)點(diǎn)不存在 RETRUN q . 三種情況：1、刪除以根結(jié)點(diǎn)R為根的樹2、刪除以大兒子結(jié)點(diǎn)A為根的子樹3、刪除以結(jié)點(diǎn)B或C(非大兒子)為根

13、的子樹RADEFCBGKH 刪除子樹 刪除子樹算法DS (t, p ) /修改p的父結(jié)點(diǎn)指針域DS1. t或p不存在 IF t OR p THEN RETURN.DS2. 確定p所指結(jié)點(diǎn)的父結(jié)點(diǎn)是否存在 FindFather( t , p . result). IF result THEN Del(p) RETURN.DS3. 若p所指結(jié)點(diǎn)的父結(jié)點(diǎn)存在，并且p是其父結(jié)點(diǎn)的大兒子結(jié)點(diǎn) IF FistChild ( result ) p THEN (FistChild ( result ) NextBrother ( p ). Del ( p ). RETURN. )DS4. 若p所指結(jié)點(diǎn)的父結(jié)點(diǎn)

14、存在，并且p不是其父結(jié)點(diǎn)的大兒子結(jié)點(diǎn)，則搜索p的前一個(gè)兄弟結(jié)點(diǎn)q q FistChild ( result ). WHILE NextBrother ( q ) p DO q NextBrother ( q ). NextBrother ( q ) NextBrother ( p ). Del ( p ). RETURN. 算法Del ( p )/*釋放根為p的子樹所占用的空間 */ Del1. 指針p所指結(jié)點(diǎn)不存在，則返回 IF p THEN RETURN.Del2. 從左到右刪除p的子樹 q FistChild ( p ). WHILE q DO ( next NextBrother (

15、q ) . Del ( q ) . q next . ) AVAIL p . ACBFDEACBFDE4.4.1樹與二叉樹的轉(zhuǎn)換4.4.2樹的順序存儲(chǔ)4.4.3樹的鏈接存儲(chǔ)4.4.4樹和森林的遍歷4.4 樹和森林1、樹的遍歷 先根遍歷：先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷每棵子樹。先根遍歷序列：A B C E F DACBFDE后根遍歷：先依次后根遍歷每棵子樹，然后訪問樹的根結(jié)點(diǎn)。 后根遍歷序列：B E F C D AACBFDE 2、森林的遍歷先根遍歷 訪問森林中第一棵樹的根結(jié)點(diǎn)； 先序遍歷第一棵樹中的諸子樹； 先序遍歷其余的諸樹。ACBDFEGJHI森林的先根遍歷序列：A B C D E F

16、 G H I J GJHIFEACBD二叉樹的先根序列：A B C D E F G H I J 后根遍歷森林： 后序遍歷第一棵樹的諸子樹； 訪問森林中第一棵樹的根結(jié)點(diǎn)； 后序遍歷其余的諸樹。 森林的后根遍歷序列： B C D A F E H J I GGJHIFEACBDACBDFEGJHI二叉樹的中根序列： B C D A F E H J I G遞歸算法先根遍歷以t為根的樹算法PreOrder( t )PreOrder1. 若t為空返回 IF t = THEN RETURN.PreOrder2. 訪問t所指結(jié)點(diǎn) PRINT(Data ( t ) ).PreOrder3. 將指針 t 定位到它

17、所指結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn) GFC( t . child );PreOrder4. 先根遍歷t所指結(jié)點(diǎn)的諸子樹 WHILE child DO ( PreOrder (child). GNB(child . child). ) ACBFDE首先，將結(jié)點(diǎn)p設(shè)為根結(jié)點(diǎn)。(1)若結(jié)點(diǎn)p不為空，訪問結(jié)點(diǎn)p，將結(jié)點(diǎn)p壓入棧，并將其大兒子結(jié)點(diǎn)設(shè)為結(jié)點(diǎn)p；反復(fù)執(zhí)行(1)，直至結(jié)點(diǎn)p為空。(2)從棧中彈出一個(gè)結(jié)點(diǎn)，若它有大兄弟結(jié)點(diǎn)，則訪問該結(jié)點(diǎn)，并將其大兄弟結(jié)點(diǎn)壓入棧；否則，反復(fù)執(zhí)行(2)，直至彈出的結(jié)點(diǎn)有大兄弟結(jié)點(diǎn)或?？?。(3)反復(fù)執(zhí)行(1)(2)，直至棧為空。 迭代算法先根遍歷以t為根的樹算法NPO( t )N

18、PO1. 初始化堆棧S S AVAILNPO2. 保存根指針 p t .NPO3. 若p所指結(jié)點(diǎn)不為空，訪問p所指結(jié)點(diǎn)，將p壓入棧，并將其FistChild指針設(shè)為p. WHILE p DO (PRINT ( Data ( p ) ). Push (S , p ). p FistChild (p ). ) 迭代算法先根遍歷以t為根的樹NPO4. 從棧中彈出指針，直至彈出的指針?biāo)附Y(jié)點(diǎn)有大兄弟結(jié)點(diǎn)或棧空以至無結(jié)點(diǎn)可彈出。 WHILE p = AND S非空 DO ( Pop ( S . p ). p NextBrother ( p ). )NPO5. 重復(fù)上述過程 IF S非空 THEN GOT

19、O NPO3. 樹和森林的層次遍歷例 ACBDFEGJHI森林的層次遍歷序列： A E G B C D F H I J樹和森林的層次遍歷 是沿NextBrother鏈訪問的過程，指針 FirstChild起承上啟下的作用，可以使用隊(duì)列輔助存儲(chǔ)。森林的層次遍歷序列： A E G B C D F H I JGJHIFEACBD算法LevelOrder（t）/ 指針t指向與森林自然對(duì)應(yīng)的二叉樹的根L1 創(chuàng)建一個(gè)輔助隊(duì)列CREATE(Q).L2 根結(jié)點(diǎn)入隊(duì)Q t . /根結(jié)點(diǎn)入隊(duì)列L3 利用隊(duì)列進(jìn)行層次遍歷WHILE NOT(IsEmpty(Q) DO ( p Q . WHILE pNULL DO (

20、 PRINT(data(p). IF FirstChild(p)NULL THEN Q FirstChild(p). pNextBrother(p) . ) ) GJHIFEACBD4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應(yīng)用第四章 樹4.5.1文件編碼4.5.2擴(kuò)充二叉樹4.5.3哈夫曼樹與哈夫曼編碼4.5 壓縮與哈夫曼樹 數(shù)據(jù)壓縮是計(jì)算機(jī)科學(xué)中的重要技術(shù)。數(shù)據(jù)壓縮過程稱為編碼，即將文件中的每個(gè)字符均轉(zhuǎn)換為一個(gè)唯一的二進(jìn)制位串。 數(shù)據(jù)解壓過程稱為解碼，即將二進(jìn)制位串轉(zhuǎn)換為對(duì)應(yīng)的字符。壓縮的關(guān)鍵在于編碼的方法，哈夫曼編碼是一種最常用無損壓縮編碼方

21、法。4.5.1 文件編碼 假設(shè)有一個(gè)文件僅包含7個(gè)字符：a、e、i、s、t、sp（空格）和nl（換行），且文件中有10個(gè)a，15個(gè)e，12個(gè)i，3個(gè)s，4個(gè)t，13個(gè)sp，1個(gè)nl。 因?yàn)閘og27 = 3，所以，每個(gè)字符都至少由一個(gè)3位的二進(jìn)制串表示。于是文件的總位數(shù)至少應(yīng)該是： 103 + 153 + 123 + 33 + 43 + 133 + 13 = 174 . 在實(shí)際應(yīng)用的一些大文件中，字符被使用的比率是非平均的，即有些字符出現(xiàn)的次數(shù)多，而有些字符出現(xiàn)的次數(shù)卻非常少。如果所有字符都由等長(zhǎng)的二進(jìn)制碼表示，那么將造成空間浪費(fèi)。 如何才能減少不必要的空間浪費(fèi)呢？文件壓縮的通常策略是：采用不

22、等長(zhǎng)的二進(jìn)制碼，令文件中出現(xiàn)頻率高的字符的編碼盡可能短。但是，采用不等長(zhǎng)編碼又可能會(huì)產(chǎn)生多義性。例如：如果用01表示a，10表示b，1001表示c，那么對(duì)于編碼1001，我們無法確定它表示字符c ，還是表示字符串ba ，其原因是b的編碼與c的編碼的開始（前綴）部分相同。為了避免出現(xiàn)多義性，就必須要求字符集中任何字符的編碼都不是其它字符的編碼的前綴，滿足這個(gè)條件的編碼被稱為前綴碼。顯然，等長(zhǎng)編碼是前綴碼。怎樣的前綴碼才能使文件的總編碼長(zhǎng)度最短？設(shè)組成文件的字符集A=a1,a2,an，其中，ai的編碼長(zhǎng)度為li；ai出現(xiàn)的次數(shù)為ci 。要使文件的總編碼最短，就必須要確定li，使 取最小值.如何設(shè)計(jì)

23、出使上式最小的前綴碼？Huffman于1952年提出了哈夫曼算法。4.5.1文件編碼4.5.2擴(kuò)充二叉樹4.5.3哈夫曼樹與哈夫曼編碼4.5 壓縮與哈夫曼樹4.5.2 擴(kuò)充二叉樹定義4.9 為了使問題的處理更為方便，每當(dāng)原二叉樹中出現(xiàn)空子樹時(shí)，就增加特殊的結(jié)點(diǎn)空樹葉，由此生成的二叉樹稱為擴(kuò)充二叉樹。 擴(kuò)充二叉樹每一個(gè)圓形結(jié)點(diǎn)都有兩個(gè)兒子，每一個(gè)方形結(jié)點(diǎn)沒有兒子。 規(guī)定空二叉樹的擴(kuò)充二叉樹只有一個(gè)方形結(jié)點(diǎn)。圓形結(jié)點(diǎn)稱為內(nèi)結(jié)點(diǎn)，方形結(jié)點(diǎn)稱為外結(jié)點(diǎn)。 (a) (b)二叉樹和它的擴(kuò)充二叉樹定義4.10 擴(kuò)充二叉樹的外通路長(zhǎng)度定義為從根到每個(gè)外結(jié)點(diǎn)的路徑長(zhǎng)度之和，內(nèi)通路長(zhǎng)度定義為從根到每個(gè)內(nèi)結(jié)點(diǎn)的路徑長(zhǎng)

24、度之和。外通路長(zhǎng)度為 3 3 2 3 4 4 3 3=25內(nèi)通路長(zhǎng)度為 2 1 0 2 3 12=11.定義4.11 給擴(kuò)充二叉樹中n個(gè)外結(jié)點(diǎn)賦上一個(gè)實(shí)數(shù)，稱為該結(jié)點(diǎn)的權(quán)。樹的加權(quán)外通路長(zhǎng)度定義為WPL： 其中，n表示外結(jié)點(diǎn)的個(gè)數(shù)，wi和Li分別表示外結(jié)點(diǎn)ki的權(quán)值和根到ki之間的路徑長(zhǎng)度。 加權(quán)外通路長(zhǎng)度分別是4*2+2*3+3*3+11*1=343*2+4*3+11*3+2*1=53和2*2+11*2+3*2+4*2=40定義4.12 在外結(jié)點(diǎn)權(quán)值分別為w0,w1,wn-1的擴(kuò)充二叉樹中，加權(quán)外通路長(zhǎng)度最小的擴(kuò)充二叉樹稱為最優(yōu)二叉樹 。4.5.1文件編碼4.5.2擴(kuò)充二叉樹4.5.3哈夫曼

25、樹與哈夫曼編碼4.5 壓縮與哈夫曼樹文件編碼問題就變成構(gòu)造最優(yōu)二叉樹問題，每個(gè)外結(jié)點(diǎn)代表一個(gè)字符，該字符的頻率作為其權(quán)值，從根到外結(jié)點(diǎn)的路徑長(zhǎng)度就是該字符的編碼長(zhǎng)度 .為求得最優(yōu)二叉樹，哈夫曼巧妙的設(shè)計(jì)了哈夫曼算法，通過哈夫曼算法可以建立一棵哈夫曼樹，從而為壓縮文本文件建立哈夫曼編碼。哈夫曼算法基本思想： 把每個(gè)結(jié)點(diǎn)都作為一棵二叉樹的根結(jié)點(diǎn)，這n個(gè)根結(jié)點(diǎn)就組成了一個(gè)森林。我們把結(jié)點(diǎn)在文件中出現(xiàn)的次數(shù)定義為該結(jié)點(diǎn)的權(quán)值。 (1) 在森林中取權(quán)值最小的兩個(gè)根結(jié)點(diǎn)s和nl，合并成一棵二叉樹，并生成一個(gè)新結(jié)點(diǎn)T1，作為這兩個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，T1的權(quán)值是它的兩個(gè)子結(jié)點(diǎn)的權(quán)值之和。顯然，T1成為新的根結(jié)點(diǎn)，

26、而s和nl成為T1的子結(jié)點(diǎn)，同時(shí)，森林中減少了一棵樹。 (2) 對(duì)新森林重復(fù)上一步操作，直至森林中只有唯一的根結(jié)點(diǎn)時(shí)，終止操作。 由上述方法構(gòu)造出的二叉樹，被稱為“哈夫曼樹”。 例: F=7,5,2,4 2475116187524752647524116文件編碼假設(shè)有一個(gè)文件僅包含7個(gè)字符：a、e、i、s、t、sp(空格)和nl(換行)，且文件中有10個(gè)a，15個(gè)e，12個(gè)i，3個(gè)s，4個(gè)t，13個(gè)sp，1個(gè)nl。 定理4.3 在外結(jié)點(diǎn)權(quán)值分別為w0,w1,wn-1的擴(kuò)充二叉樹中，由哈夫曼算法構(gòu)造出的哈夫曼樹的帶權(quán)路徑長(zhǎng)度最小，因此哈夫曼樹為最優(yōu)二叉樹。由觀察可知，字符集中的字符所在的結(jié)點(diǎn)均是

27、哈夫曼樹中的外結(jié)點(diǎn)。哈夫曼樹中沒有度為1的結(jié)點(diǎn)。哈夫曼編碼：將哈夫曼樹每個(gè)分支結(jié)點(diǎn)的左分支標(biāo)上0，右分支標(biāo)上1，把從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑上的標(biāo)號(hào)連接起來，作為該葉結(jié)點(diǎn)所代表的字符的編碼，這樣得到的編碼稱為哈夫曼編碼。根據(jù)定理4.3知道，對(duì)于所有的編碼，哈夫曼編碼使文件的總編碼長(zhǎng)度最短。實(shí)際上，哈夫曼算法的應(yīng)用很廣，這里只是以哈夫曼編碼為例來說明哈夫曼算法。哈夫曼編碼 哈夫曼編碼的主要用途是實(shí)現(xiàn)數(shù)據(jù)壓縮。 設(shè)給出一段報(bào)文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T 若給每個(gè)字符以等長(zhǎng)編碼 A : 00 T : 10 C : 01 S : 11 0100

28、1110 01001110 110010 0010 00 10001100 則總編碼長(zhǎng)度為 18 * 2 = 36.例 哈夫曼編碼報(bào)文：CAST CAST SAT AT A TASA字符集合是 C, A, S, T ，各個(gè)字符出現(xiàn)的頻度(次數(shù))是 W 2, 7, 4, 5 7542011100TACS編碼 A (0) T (10) C (110) S (111)61118總編碼長(zhǎng)度：1*7+2*5+3*2+3*4=35在構(gòu)造哈夫曼樹的過程中，沒有一片樹葉是其他樹葉的祖先，所以每個(gè)葉結(jié)點(diǎn)對(duì)應(yīng)的編碼不可能是其他葉結(jié)點(diǎn)對(duì)應(yīng)的編碼的前綴，由此可知哈夫曼編碼是二進(jìn)制的前綴碼。哈夫曼編碼是否唯一？哈夫曼樹

29、中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：其中，LLINK和RLINK為鏈接域，INFO為信息域，Weight為該結(jié)點(diǎn)的權(quán)值。LLINKINFOWeightRLINKHuffman算法假設(shè)給定m個(gè)實(shí)數(shù)（權(quán)值）所在結(jié)點(diǎn)的地址存于一維數(shù)組H1:m+1中，該數(shù)組按每個(gè)結(jié)點(diǎn)的Weight域已經(jīng)排序，即Weight(H1)Weight(Hm) Weight(Hm+1)=+算法Huffman(H, m)Huffman1. 初始化 FOR i1 TO m DO LLINK(Hi) RLINK(Hi) .Huffman2. 組合過程 FOR i1 TO m-1 DO ( t AVAIL. P1 Hi. P2 Hi+1. Weigh

30、t(t) Weight(P1 ) Weight(P2 ). LLINK(t) P1 . RLINK(t) P2 . p t ./*把新結(jié)點(diǎn)p插入到數(shù)組H中Hj位置*/j i 2 .WHILE Weight(p)Weight(Hj) DO ( Hj-1 Hj . j j 1. ) Hj-1 p. )編碼：依次將數(shù)據(jù)文件中的字符按哈夫曼樹轉(zhuǎn)換成哈夫曼編碼。解碼：依次讀入文件的二進(jìn)制碼，從哈夫曼樹的根結(jié)點(diǎn)出發(fā)，若當(dāng)前讀入0，則走向其左孩子，否則走向其右孩子，到達(dá)某一葉結(jié)點(diǎn)時(shí)，便可以譯出相應(yīng)的字符。 4.1樹的基本概念4.2二叉樹4.3線索二叉樹4.4樹和森林4.5壓縮與哈夫曼樹4.6 應(yīng)用第四章 樹

31、4.6.1 表達(dá)式求值問題1、表達(dá)式樹的建立 表達(dá)式求值是程序設(shè)計(jì)語(yǔ)言編譯的一個(gè)基本問題。 表達(dá)式有一個(gè)內(nèi)在二叉樹結(jié)構(gòu)，表達(dá)式(ab)(cd)e對(duì)應(yīng)的二叉樹如下圖所示，二叉樹中葉結(jié)點(diǎn)是表達(dá)式中的變量或常數(shù)（如：a, b），非葉結(jié)點(diǎn)是操作符。eabcd對(duì)表達(dá)式樹做后根遍歷可以得到后綴表達(dá)式：ab+cd-*e- 由于中綴表達(dá)式存在運(yùn)算符的優(yōu)先級(jí)，計(jì)算機(jī)處理中綴表達(dá)式比較復(fù)雜。一個(gè)中綴表達(dá)式中有多少個(gè)運(yùn)算符，原則上就得對(duì)表達(dá)式掃描多少遍，才能完成計(jì)算。 在編譯系統(tǒng)中，常把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，然后對(duì)后綴式表達(dá)式進(jìn)行處理。 如果不考慮一元操作符負(fù)號(hào)，可以用后綴表達(dá)式構(gòu)造表達(dá)式對(duì)應(yīng)的二叉樹。二叉樹

32、的建立過程如下： 從左向右依次掃描后綴表達(dá)式中各個(gè)符號(hào)，1）如果當(dāng)前被掃描的符號(hào)是操作數(shù)，則生成一個(gè)新結(jié)點(diǎn)，以此操作數(shù)作為該結(jié)點(diǎn)的數(shù)據(jù)域，將此結(jié)點(diǎn)作為新二叉樹的根結(jié)點(diǎn)壓入堆棧中。2）如果當(dāng)前被掃描的符號(hào)為二元操作符，則生成一個(gè)新結(jié)點(diǎn)，并以此操作符作為該結(jié)點(diǎn)的數(shù)據(jù)域，從棧頂彈出兩個(gè)結(jié)點(diǎn)，創(chuàng)造一棵以新生成結(jié)點(diǎn)為根、以彈出的兩個(gè)結(jié)點(diǎn)為其右子結(jié)點(diǎn)和左子結(jié)點(diǎn)的新二叉樹，將新樹根壓入堆棧。 按照上述方法處理完表達(dá)式中所有符號(hào)后，堆棧中僅包含一個(gè)結(jié)點(diǎn)，即所求二叉樹的根結(jié)點(diǎn)。算法 CET(expr . t)/*算法CET利用輔助堆棧S構(gòu)造表達(dá)式expr對(duì)應(yīng)的二叉樹, 算法結(jié)束時(shí)指針t 指向二叉樹根結(jié)點(diǎn)；CET

33、是CreatExpressTree之縮寫*/CET1. 創(chuàng)建一個(gè)輔助堆棧 CREATE ( S ). Read ( op ). /讀入表達(dá)式序列中的一個(gè)符號(hào)CET2. 掃描表達(dá)式 WHILE op # DO ( IF op= OR op= OR op= OR op= THEN ( rpr S. lpr S. pAVAIL. Data(p)op. Left(p)lpr. Right(p)rpr. Sp . ) ELSE ( pAVAIL. Data(p)op. Left(p). Right(p). Sp . ) Read ( op ). /讀入表達(dá)式序列中的一個(gè)符號(hào) )CET3 指針t 指向二叉

34、樹根結(jié)點(diǎn) t S. 練習(xí)：構(gòu)造后綴表達(dá)式 ab+cde+*-f-gh+* 對(duì)應(yīng)的二叉樹2、后綴表達(dá)式求值的方法： 若已知后綴表達(dá)式，從左到右讀入后綴表達(dá)式的各個(gè)符號(hào)， 若讀到的是操作數(shù)，將它壓入堆棧。 若讀到的是運(yùn)算符，就從棧中連續(xù)彈出兩個(gè)元素，進(jìn)行相應(yīng)的運(yùn)算，并將結(jié)果壓入棧。 讀入結(jié)束符時(shí)，棧頂元素就是計(jì)算結(jié)果。 操作 后綴表達(dá)式 棧T2 =A/T1 T2 DE*+AC*- =; T2 DET3 =D*E T2T3 +AC*- =; T2 T3 T4=T2+T3 T4AC*- =; T4ACT5 =A*C T4 T5 - =; T4 T5 T6 =T4- T5 =; T6T1=B*C AT1/DE*+AC*- =; AT1 ABC*/DE*+AC*- =; ABC例 計(jì)算后綴表達(dá)式ABC*/DE*+AC*- 在表達(dá)式樹的基礎(chǔ)上，通過后根遍歷，可以計(jì)算表達(dá)式的值：當(dāng)訪問一個(gè)葉結(jié)點(diǎn)時(shí)，把對(duì)應(yīng)的值壓入堆棧中；當(dāng)訪問一個(gè)非葉結(jié)點(diǎn)時(shí)，從堆棧中連續(xù)彈出兩個(gè)值，按此結(jié)點(diǎn)規(guī)定的操作進(jìn)行運(yùn)算，并且結(jié)果壓回到堆棧中；當(dāng)遍歷終止時(shí)，堆棧中只有一個(gè)值，它就是表達(dá)式的值。 算法 GetValue( t . value)/*t為表達(dá)式對(duì)應(yīng)二叉樹根指針,value為求得的表達(dá)式值。利用輔助堆棧S和calculator求