數據結構第6章二叉樹

1、佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University1重點重點：二叉樹的性質、遍歷；二叉：二叉樹的性質、遍歷；二叉樹與森林樹與森林( (樹樹) )的相互轉換的相互轉換難點難點：樹和二叉樹應用的算法設計：樹和二叉樹應用的算法設計 佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University26.1 樹的定義和基本術語樹的定義和基本術語6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.6 赫夫曼樹及其應用赫夫曼樹及其應用佛山科學技術學院佛山科學技術學院 Fo

2、shan UniversityFoshan University3 樹的定義樹的定義(遞歸定義遞歸定義)：樹是：樹是n(n0)個結點個結點(元素元素)的有限集。的有限集。l若若 n=0，稱為，稱為空樹空樹。l若若 n 0，則，則l有且僅有一個特定的稱為有且僅有一個特定的稱為根根的結點的結點root；l當當n 1時，除根以外的其他結點劃分為時，除根以外的其他結點劃分為m(m0) 個互不相交的有限集個互不相交的有限集T1, T2, Tm，其中每一個，其中每一個集合本身又是一棵樹，并且稱為根的集合本身又是一棵樹，并且稱為根的子樹子樹。且。且對任意的對任意的i(mi1), Ti存在惟一的結點存在惟一的

3、結點xi , 有有H，H為樹中元素之間的二元關系為樹中元素之間的二元關系集。集。佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University4樹的表示樹的表示AABCDEFGHIJKL佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University5樹的其他表示樹的其他表示-嵌套集合、凹入表示嵌套集合、凹入表示GCABDHIJEKFLA* B* E* F* K* L* C* G* D* H* I* J*佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University6結點結點結

4、點的度結點的度結點的層次結點的層次終端結點終端結點(葉子葉子)非終端結點非終端結點(分支結點分支結點)內部結點內部結點基本術語基本術語ABCDEFGHIJKL第第1層層第第2層層第第3層層第第4層層高度為高度為4孩子孩子雙親雙親兄弟兄弟祖先祖先子孫子孫堂兄弟堂兄弟樹的度樹的度樹的深度樹的深度/高度高度有序樹有序樹無序樹無序樹森林森林佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University7基本操作基本操作： InitTree( &T) 操作結果：構造空樹操作結果：構造空樹T。 DestroyTree( &T ) 初始條件：樹初始條件：樹T已存在。已

5、存在。 操作結果：銷毀樹操作結果：銷毀樹T。 ClearTree( &T ) 初始條件：樹初始條件：樹T已存在。已存在。 操作結果：將樹操作結果：將樹T清為空樹。清為空樹。 TreeEmpty( T ) 初始條件：樹初始條件：樹T已存在已存在 操作結果：若操作結果：若T為空樹則返回為空樹則返回TRUE，否則，否則FALSE。佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University8 TreeDepth( T ) 初始條件：樹初始條件：樹T已存在已存在 操作結果：返回樹操作結果：返回樹T的深度。的深度。 Root( T ) 初始條件：樹初始條件：樹T

6、已存在。已存在。 操作結果：返回操作結果：返回T的根。的根。 Value( T, cur_e ) 初始條件：樹初始條件：樹T已存在，已存在，cur_e是是T中的某個結點。中的某個結點。 操作結果：返回操作結果：返回cur_e的值；的值； Assign( T, &cur_e, value ) 初始條件：樹初始條件：樹T已存在，已存在，cur_e是是T中的某個節(jié)點。中的某個節(jié)點。 操作結果：結點操作結果：結點cur_e賦值為賦值為value。佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University9 Parent( T, cur_e ) 初始條件：樹初

7、始條件：樹T已存在，已存在，cur_e是是T中的某個結點。中的某個結點。 操作結果：若操作結果：若cur_e是是T的非根結點，則返回它的雙親，的非根結點，則返回它的雙親， 否則函數值為否則函數值為“空空”。 LeftChild( T, cur_e ) 初始條件：樹初始條件：樹T已存在，已存在，cur_e是是T中的某個結點。中的某個結點。 操作結果：若操作結果：若cur_e是是T的非葉子結點，則返回它的最左的非葉子結點，則返回它的最左 孩子，否則返回孩子，否則返回“空空”。 RightSibling( T, cur_e ) 初始條件：樹初始條件：樹T已存在，已存在，cur_e是是T中某個結點。中

8、某個結點。 操作結果：若操作結果：若cur_e有右兄弟，則返回它的右兄弟，否則有右兄弟，則返回它的右兄弟，否則 返回返回“空空”。佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University10 InsertChild( &T, p, i, c ) 初始條件：樹初始條件：樹T已存在，已存在，p指向指向T中某個結點，中某個結點，1 i p所指所指 結點的度結點的度+1，非空樹，非空樹c于于T不相交。不相交。 操作結果：插入操作結果：插入c為為T中中p所指結點的第所指結點的第i棵子樹?？米訕洹?DeleteChild( &T, p, i ) 初始條件：樹初

9、始條件：樹T已存在，已存在，p指向指向T中的某個結點，中的某個結點，1 i p所所 指結點的度指結點的度。 操作結果：刪除操作結果：刪除T中中p所指結點的第所指結點的第i棵子樹。棵子樹。 TraverseTree( T, visit() ) 初始條件：樹初始條件：樹T已存在，已存在，visit()是對結點操作的應用函數。是對結點操作的應用函數。 操作結果：按某種次序對操作結果：按某種次序對T 的每個結點調用函數的每個結點調用函數visit()一一 次且至多一次。一旦次且至多一次。一旦visit()失敗，則操作失敗。失敗，則操作失敗。佛山科學技術學院佛山科學技術學院 Foshan Univers

10、ityFoshan University116.1 樹的定義和基本術語樹的定義和基本術語6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.6 赫夫曼樹及其應用赫夫曼樹及其應用佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University12二叉樹的定義二叉樹的定義(遞歸定義遞歸定義)l特點：每個結點特點：每個結點至多只有兩棵子樹至多只有兩棵子樹，子樹有，子樹有左左右右之分之分l二叉樹二叉樹 : 度不大于度不大于2的有序樹的有序樹lADT BinaryTree二叉樹二叉樹無序樹無序樹佛山科學技術學院佛山科學

11、技術學院 Foshan UniversityFoshan University13 二叉樹或為空樹，或是由一個根結點加上兩棵分二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為別稱為左子樹左子樹和和右子樹右子樹的、的、互不交的互不交的二叉樹組成。二叉樹組成。ABCDEFGHK根結點左子樹右子樹佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University14二叉樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：P空樹空樹只含根結點只含根結點PPPLRR右子樹為空樹右子樹為空樹L左子樹為空樹左子樹為空樹左右子樹左右子樹均不為空均不為空樹樹佛山科學技術學院佛山科學技術學

12、院 Foshan UniversityFoshan University15二叉樹的性質二叉樹的性質l性質性質1：二叉樹的第：二叉樹的第i層至多有層至多有2i-1個結點個結點(i1)l性質性質2：深度為：深度為h的二叉樹至多有的二叉樹至多有2h 1個結點個結點(h1) 思考：性質思考：性質1和性質和性質2推廣到推廣到k叉樹，結果會如何？叉樹，結果會如何？l性質性質3：n0 = n2 + 1結點總數結點總數 n = n0 + n1 + n2分支數分支數 n-1 = n1 + 2n2ki- -1(kh- -1)/(k- -1)佛山科學技術學院佛山科學技術學院 Foshan UniversityFo

13、shan University16定義定義1 滿二叉樹滿二叉樹 (Full Binary Tree) 一棵深度為一棵深度為k且有且有2 k-1個結點的二叉樹稱為滿個結點的二叉樹稱為滿二叉樹。二叉樹。62175438910 1113 14 1512滿二叉樹滿二叉樹佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University17215436 7216543非完全二叉樹非完全二叉樹定義定義2 完全二叉樹完全二叉樹 (Complete Binary Tree) 若設二叉樹的高度為若設二叉樹的高度為h，則共有，則共有h層。除第層。除第 h 層外，層外，其它各層其

14、它各層 (1 h-1) 的結點數都達到最大個數，第的結點數都達到最大個數，第 h 層層從右向左從右向左連續(xù)缺若干結點，這就是完全二叉樹。連續(xù)缺若干結點，這就是完全二叉樹。621754389 10 11 12完全二叉樹完全二叉樹佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University18l滿二叉樹滿二叉樹：一棵深度為：一棵深度為k且有且有2k 1個結點的二叉樹個結點的二叉樹(k0)l完全二叉樹完全二叉樹：對于深度為：對于深度為k的完全二叉樹，則的完全二叉樹，則1) 前前k-1層為滿二叉樹；層為滿二叉樹；2) 第第k層結點依次占據最左邊的位置；層結點依

15、次占據最左邊的位置；3) 一個結點有右孩子，則它必有左孩子；一個結點有右孩子，則它必有左孩子；4) 度為度為1的結點個數為的結點個數為0或或15) 葉子結點只可能在層次最大的兩層上出現；葉子結點只可能在層次最大的兩層上出現；6) 對任一結點，若其右分支下的子孫的最大層次對任一結點，若其右分支下的子孫的最大層次為為l, 則其左分支下的子孫的最大層次必為則其左分支下的子孫的最大層次必為l或或l+1。佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University19性質性質4：具有：具有n個結點的完全二叉樹的深度為個結點的完全二叉樹的深度為 由性質由性質2 2

16、k-1-1 n 2k-1 或或 2k-1 n 2k 于是于是 k-1 log2n k即即 log2n1, 則其雙親是結點則其雙親是結點 ；(2) 如果如果2i n，則結點，則結點i無左孩子無左孩子(結點結點i為葉子結為葉子結點點)；否則其左孩子是結點；否則其左孩子是結點2i ；(3) 如果如果2i + 1 n，則結點，則結點i無右孩子；否則其右孩無右孩子；否則其右孩子是結點子是結點2i + 1。1log2n2/ i佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University221.已知完全二叉樹有已知完全二叉樹有100個結點，則該二叉樹有多少個結點，則

17、該二叉樹有多少個葉子結點個葉子結點？答：若認為每個結點均已編號，則最大的編號為答：若認為每個結點均已編號，則最大的編號為100，其父結點編號為其父結點編號為50（見右下圖），從（見右下圖），從51到到100均為葉均為葉子，因此葉子數為子，因此葉子數為100-50=50。佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University23已知完全二叉樹有已知完全二叉樹有50個葉子結點，則該二叉樹個葉子結點，則該二叉樹的總結點數至少應有多少個？的總結點數至少應有多少個？方法方法1： 假設完全二叉樹的最大非葉結點編號假設完全二叉樹的最大非葉結點編號為為m，則最大

18、葉結點編號為，則最大葉結點編號為2m+1,(2m+1)-m=50 m=49總結點數目總結點數目=2m+1=99方法方法2： 由性質由性質3：n0=n2+1 即：即：50=n2+1 所以：所以：n2=49 令令n1=0得：得：n= n0 + n2=99佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University24l二叉樹的順序存儲結構l類型定義typedef ElemType SqBiTreeMAX_TREE_SIZE; /0號單元存儲根結點 1) 依據性質5，用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結點元素；結點在存儲區(qū)中的相

19、對位置反映它們邏輯上的關系2) 僅適用于完全二叉樹l一般二叉樹的順序存儲方法通過補虛結點，將一般的二叉樹變成完全二叉樹空間開銷大！佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University25完全二叉樹的順序表示完全二叉樹的順序表示11 2 3 4 5 6 7 8 9102489 105673佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University26l空間利用率問題： 在最壞情況下，一個深度為k且只有k個結點的單支樹(樹中不存在度為2的結點)，則需要長度為2k-1的一維數組。12345671 2 3 4

20、 5 0 0 0 0 6 7一般二叉樹的順序表示一般二叉樹的順序表示佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University27l二叉樹的鏈式存儲結構l引入輔助空間表示結點之間的關系：雙親-孩子二叉鏈表(左、右孩子鏈域)三叉鏈表(雙親及左、右孩子鏈域)l二叉鏈的類型定義(動態(tài)鏈表)typedef struct BiTNodel ElemType data; struct BiTNode *lchild, *rchild;/ 左右孩子指針 BiTNode, *BiTree;若有n個結點，則共有2n個鏈域；其中n-1不為空，指向孩子；另外n+1個為空鏈

21、域（為何？）佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University28鏈表表示鏈表表示lChild data rChilddatalChildrChild二叉鏈表含兩個指針域的結點結含兩個指針域的結點結構構lChild data parent rChild含三個指針域的結點結構含三個指針域的結點結構parentdatalChildrChild三叉鏈表佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University29二叉樹鏈表表示的示例二叉樹鏈表表示的示例 AAABBBCCCDDDFFFEEErootroot

22、root二叉樹 二叉鏈表 三叉鏈表佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University30l遍歷二叉樹l基于先/中/后序遍歷算法的應用l為什么強調使用函數調用的結果l先/中/后序遍歷的非遞歸算法l層次遍歷算法及其應用l二叉樹的創(chuàng)建方法l線索二叉樹佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University31l遍歷二叉樹按一定的搜索路徑對樹中的每一結點訪問且僅訪問一次l遍歷時的搜索路線(約定：先左后右，D-根,L-左子樹,R-右子樹)l先(根)序遍歷：1 2 4 5 6 7 3 (DLR) l中(根)序

23、遍歷：4 2 6 5 7 1 3 (LDR)l后(根)序遍歷：4 6 7 5 2 3 1 (LRD)l層次遍歷：1 2 3 4 5 6 71234567佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University32練習：如圖所示為一棵二叉樹，試分別寫練習：如圖所示為一棵二叉樹，試分別寫出此樹的中序、先序及后序序列。出此樹的中序、先序及后序序列。D E C B H G F AD E C B H G F AA B C D E F G HA B C D E F G HB D C E A F H GB D C E A F H G佛山科學技術學院佛山科學技術學

24、院 Foshan UniversityFoshan University33如圖所示為一棵二叉樹，試分別寫出如圖所示為一棵二叉樹，試分別寫出此樹的中序、先序及后序序列。此樹的中序、先序及后序序列。中序序列：中序序列：BDCEAFHGBDCEAFHG先序：先序：ABCDEFGHABCDEFGH后序：后序：DECBHGFADECBHGFA佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University34l先/中/后序遍歷的區(qū)別如右圖，三者經過的搜索路線是相同的；只是訪問結點的時機不同。每一結點在整個搜索路線中會經過3次：l第一次進入到該結點此時訪問該結點，稱

25、為先序遍歷l由左子樹回溯到該結點此時訪問該結點，稱為中序遍歷l由右子樹回溯到該結點此時訪問該結點，稱為后序遍歷佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University35l遍歷算法的遞歸實現l二叉樹的遞歸定義性質，決定了它的很多算法都可用遞歸實現，遍歷算法就是其中之一。l對于二叉樹的遍歷，可以不去具體考慮各子問題(左子樹、根、右子樹)的遍歷結果是什么，而去考慮如何由各子問題的求解結果構成原問題(二叉樹)的遍歷結果遞歸規(guī)律的確定。必須注意的是，當二叉樹小到一定程度，即空樹時，應直接給出解答遞歸結束條件及處理。 佛山科學技術學院佛山科學技術學院 Fos

26、han UniversityFoshan University36先序遍歷Status PreOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ) if ( T != NULL ) if ( Visit(T-data) ) if ( PreOrderTraverse( T-lchild, Visit ) ) if ( PreOrderTraverse( T-rchild, Visit ) ) return OK; return ERROR; else return OK;佛山科學技術學院佛山科學技術學院 Foshan Univers

27、ityFoshan University376.1 樹的定義和基本術語樹的定義和基本術語6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.6 赫夫曼樹及其應用赫夫曼樹及其應用佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University38l最優(yōu)樹最優(yōu)樹l路徑路徑：從樹中一個結點到另一個結點之間的分支：從樹中一個結點到另一個結點之間的分支l路徑長度路徑長度：路徑上的分支數目：路徑上的分支數目l樹的路徑長度樹的路徑長度：樹根到每一結點的路徑長度之和：樹根到每一結點的路徑長度之和完全二叉樹是這種路徑長度最短的

28、二叉樹完全二叉樹是這種路徑長度最短的二叉樹l結點的帶權路徑長度結點的帶權路徑長度：該結點到樹根之間的路徑長度與：該結點到樹根之間的路徑長度與結點上權的乘積結點上權的乘積l樹的帶權路徑長度樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和之和l最優(yōu)二叉樹或赫夫曼樹最優(yōu)二叉樹或赫夫曼樹：樹的帶權路徑長度最小的二叉：樹的帶權路徑長度最小的二叉樹樹niiilwWPL1佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University39abcd010011000111cdbaWPL = 2*(7+5+2+4)=36WPL=1*7+2

29、*5+3*(2+4)=35佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University40赫夫曼樹的應用赫夫曼樹的應用最佳判定算法最佳判定算法分數分數05960697079808990100比例比例0.050.150.400.300.10等級等級不及格不及格及格及格中等中等良好良好優(yōu)秀優(yōu)秀a60?0.050.150.400.300.10a70?a80?a90?WPL=3.15佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University41赫夫曼樹的應用赫夫曼樹的應用最佳判定算法最佳判定算法0.050.150.4

30、00.300.10WPL=2.0570a8080a9060a70a60佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University4260?70?80?0 )，則樹中，則樹中 最多有最多有 2h-1 個結點個結點滿二叉樹滿二叉樹 最少有最少有2h-1個結點個結點佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University45l問題描述問題描述：已知電文中出現的一組字符及出現頻率，試：已知電文中出現的一組字符及出現頻率，試為該組字符編碼以使得電文總長最短。為該組字符編碼以使得電文總長最短。l前綴編碼前綴編碼：某字

31、符的編碼不是其他字符編碼的前綴。：某字符的編碼不是其他字符編碼的前綴。l赫夫曼編碼過程赫夫曼編碼過程：1) 由由n個權值，形成包含有個權值，形成包含有2n-1個結點的赫夫曼樹個結點的赫夫曼樹2) 約定赫夫曼樹的左分支表示字符約定赫夫曼樹的左分支表示字符0，右分支表示字符，右分支表示字符1，則從根結點到葉子結點的路徑上的分支字符組成的，則從根結點到葉子結點的路徑上的分支字符組成的字符串作為該葉子結點字符的編碼。字符串作為該葉子結點字符的編碼。佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University46赫夫曼樹和赫夫曼編碼的存儲結構選取赫夫曼樹和赫夫曼

32、編碼的存儲結構選取l由權值數由權值數n唯一確定樹中的結點數為唯一確定樹中的結點數為 (2n - 1)一次性分配結點空間一次性分配結點空間l編碼：從葉子到根的路徑編碼：從葉子到根的路徑快速訪問雙親快速訪問雙親l譯碼：從根到葉子的路徑譯碼：從根到葉子的路徑快速訪問孩子快速訪問孩子赫夫曼編碼赫夫曼編碼: 按實際長度動態(tài)分配空間，按實際長度動態(tài)分配空間， 需要一需要一個求編碼的工作空間個求編碼的工作空間,長度為長度為n赫夫曼樹：赫夫曼樹：三叉靜態(tài)鏈表三叉靜態(tài)鏈表佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University47平均碼長平均碼長 = (0.23+0

33、.29)*2+ (0.11+0.14)*3+ (0.05+0.03+0.07+0.08)*4 = 1.04+0.75+0.92 = 2.71若電文有若電文有1000個字符，則電文的個字符，則電文的碼長為碼長為2.71*1000 = 271081iiilpl赫夫曼編碼的算法赫夫曼編碼的算法5381119234278151429295810000000001111111佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University48 /* 赫夫曼樹和赫夫曼編碼的存儲表示赫夫曼樹和赫夫曼編碼的存儲表示 */ typedef struct unsigned i

34、nt weight; unsigned int parent, lchild, rchild; HTNode,*HuffmanTree; /* 動態(tài)分配數組存儲赫夫動態(tài)分配數組存儲赫夫曼樹曼樹 */ typedef char *HuffmanCode; /* 動態(tài)分配數組存儲動態(tài)分配數組存儲赫夫曼編碼表赫夫曼編碼表 */佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University49void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) m=2*n-1; HT=(HuffmanT

35、ree)malloc(m+1)*sizeof(HTNode); /* 0號號單元未用單元未用 */ for(p=HT+1,i=1;i=n;+i,+p,+w) *p = *w, 0, 0, 0 ; for( ;i=m;+i,+p) *p = 0, 0, 0, 0 ; for(i=n+1;i=m;+i) /* 建赫夫曼樹建赫夫曼樹 */ 佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University50/* 在在HT1i-1中選擇中選擇parent為為0且且weight最小的兩最小的兩個結點，其序號分別為個結點，其序號分別為s1和和s2 */ select(

36、*HT,i-1,&s1,&s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; 佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University51/* 從葉子到根逆向求每個字符的赫夫曼編碼從葉子到根逆向求每個字符的赫夫曼編碼 */*HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/* 分配分配n個字符編碼的頭指針向量個字符編碼的頭指針向量(0不用不用) */cd=(char*)m

37、alloc(n*sizeof(char); /* 分配求編碼的工作空分配求編碼的工作空間間 */cdn-1=0; /* 編碼結束符編碼結束符 */for(i=1;i=n;i+) /* 逐個字符求赫夫曼編碼逐個字符求赫夫曼編碼 */ start=n-1; /* 編碼結束符位置編碼結束符位置 */ for(c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) 佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University52/* 從葉子到根逆向求編碼從葉子到根逆向求編碼 */ if(HTf.lchild=c) cd-star

38、t=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); /* 為第為第i個字符編碼分配空間個字符編碼分配空間 */ strcpy(HCi,&cdstart); /* 從從cd復制編碼復制編碼(串串)到到HC */ free(cd); /* 釋放工作空間釋放工作空間 */佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University5351429 7823 3111429 7823 1135887151429233581111358191429238715佛山科學技術學院佛山科學技術學院

39、 Foshan UniversityFoshan University54113581929 2314871529291487152911358192342佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University55例例 w=5, 29, 7, 8, 14, 23, 3, 11見見P1481135819234229148715295811358192342291487152958100佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University56例：例：假設用于通信的電文由字符集假設用于通信的電文由字符集

40、a，b，c，d，e，f，g，h中的字母構成，這中的字母構成，這8個字母在電文中出現的概率個字母在電文中出現的概率分別為分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 (1) 為這為這8個字母設計哈夫曼編碼。個字母設計哈夫曼編碼。 (2) 若用這三位二進制數對這若用這三位二進制數對這8個字母進行等長編碼個字母進行等長編碼，則哈夫曼編碼的平均碼長是等長編碼的百分之幾，則哈夫曼編碼的平均碼長是等長編碼的百分之幾?它使電文總長平均壓縮多少它使電文總長平均壓縮多少?佛山科學技術學院佛山科學技術學院 Foshan UniversityFoshan University57解：解：(1)哈夫曼編碼圖見題圖哈夫曼編碼圖見題圖根據上圖可得編碼表：根據上圖可得編碼表： a:0010b:10 c:00000 d:0001 e:01 f:00001g:11 h:0011(2) 用三位二進行數進行的等長編碼平均長度為用三位二進行數進行的等長編碼平均長度為3，而根據哈，而根據哈夫曼樹編碼的平均碼長為：夫曼樹編碼的平均碼長為：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10