數(shù)據(jù)結(jié)構(gòu)第六章哈夫曼樹PPT學(xué)習(xí)教案

1、會計學(xué)1數(shù)據(jù)結(jié)構(gòu)第六章哈夫曼樹數(shù)據(jù)結(jié)構(gòu)第六章哈夫曼樹遠(yuǎn)程通信中的一個問題遠(yuǎn)程通信中的一個問題1 最優(yōu)二叉樹最優(yōu)二叉樹Huffman樹樹2Huffman編碼及其實現(xiàn)編碼及其實現(xiàn)3第1頁/共43頁信道信道發(fā)送端（編碼）發(fā)送端（編碼）對對接收端（接收端（解解碼）碼）第2頁/共43頁第3頁/共43頁第4頁/共43頁n4樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度（WPL）n樹的帶權(quán)路徑長度規(guī)定為所有葉子樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和。結(jié)點的帶權(quán)路徑長度之和。第5頁/共43頁 2 475 (b) 7524(c) 754(a)2第6頁/共43頁最佳判定樹最佳判定樹考試成績分布表考試成績分布表 第

2、7頁/共43頁60?70?80?90?0.100.150.250.350.15WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4 = 3.15 對對10000個成績，則總共需要個成績，則總共需要31500次比較。次比較。第8頁/共43頁WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 = 0.3+0.45+0.5+0.7+0.3 = 2.25 對對10000個成績，則總共需要個成績，則總共需要22500次比較。次比較。60?70?80?90?0.100.150.250.350.15第9頁/共43頁在在F中選擇兩棵根結(jié)點權(quán)值最小的樹作

3、為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為左、右子樹上根結(jié)點的權(quán)值之和。中選擇兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為左、右子樹上根結(jié)點的權(quán)值之和。根據(jù)給定的根據(jù)給定的n個權(quán)值個權(quán)值w1,w2,wn構(gòu)成構(gòu)成n棵二叉樹的集合棵二叉樹的集合F=T1，T2，Tn),其中每棵二叉樹其中每棵二叉樹Ti中只有一個帶權(quán)為中只有一個帶權(quán)為wi的根結(jié)點的根結(jié)點,左右子樹為空。左右子樹為空。在在F中刪除這兩棵樹，同時將新得到的二叉樹加入中刪除這兩棵樹，同時將新得到的二叉樹加入F中。中。重復(fù)，直到重復(fù)，直到F中只含一棵樹為止。這棵樹就是中只含一棵樹為止。

4、這棵樹就是Huffman樹。樹。初始化初始化選擇選擇合并合并第10頁/共43頁12（1）42571213（2）457（3）2135477213745712（4）213745712 （5）19以以7，2，1，4，5為權(quán)值集合構(gòu)造為權(quán)值集合構(gòu)造Huffman樹。樹。第11頁/共43頁13第12頁/共43頁回到最初的問題，傳輸：回到最初的問題，傳輸： A：7T：5C：2E：1S：4CE3AST7121972145第13頁/共43頁將將Huffman樹的左子樹置樹的左子樹置0，右子樹置右子樹置1，這樣每個葉，這樣每個葉子都獲得一個碼字：子都獲得一個碼字：A(7)：0T(5)：10C(2)：1100E(

5、1)：1101S(4)：111WPL=71+52+24+14+43=41這里的這里的WPL就是編碼的總長度。就是編碼的總長度。CE3AST712190000111172145第14頁/共43頁CE3AST712190000111172145第15頁/共43頁17Huffman編碼算法實現(xiàn)編碼算法實現(xiàn)1.有有n個葉結(jié)點的個葉結(jié)點的Huffman樹中共有樹中共有m2n1個結(jié)點，可個結(jié)點，可將這些結(jié)點存儲在一個一維數(shù)組中。將這些結(jié)點存儲在一個一維數(shù)組中。結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)weight parent lchildrchildtypedef structunsigned int weight;unsign

6、ed int parent,lchild,rchild;HTNode,*HuffmanTree;2.可以采用動態(tài)分配的一維數(shù)組存儲編碼表?？梢圆捎脛討B(tài)分配的一維數(shù)組存儲編碼表。typedef char * HuffmanCode;第16頁/共43頁18例：以例：以7，5，2，4為為權(quán)值集合構(gòu)造哈夫曼樹。權(quán)值集合構(gòu)造哈夫曼樹。weight parent lchild rchild170002500032000440005-0006-0007-000（1）24571234第17頁/共43頁19weight parent lchild rchild17000250003250044500560346

7、-0007-000（2）2457612345第18頁/共43頁20weight parent lchild rchild17000256003250044500566346110257-000（3）24576111 23456 第19頁/共43頁21（4）2457611181234567weight parent lchild rchild17700256003250044500566346117257 18016第20頁/共43頁22權(quán)值= 5, 29, 7, 8, 14, 23, 3, 11 512927384236371181451.HT的初態(tài)的初態(tài)weightparentlchildr

8、child150002290003700048000514000623000710008110009-00010-0001112-000-00013-00014-00015-000第21頁/共43頁2021-10-16indexweightparentlchildrchild1500022900037000480005140006230007300081100090000100000110000120000130000140000150000i = n+1 = 9在在前前 i -1 = 8 個個元素中元素中找找無父結(jié)點無父結(jié)點且有且有最小及最小及次小權(quán)值次小權(quán)值元素的下標(biāo)元素的下標(biāo)s1 = 7

9、s2 = 1 構(gòu)造構(gòu)造新結(jié)點，新結(jié)點，存儲于存儲于下標(biāo)為下標(biāo)為 i = 9 的元素中的元素中權(quán)值權(quán)值=最小及次小權(quán)和最小及次小權(quán)和 = 5 + 3 = 8構(gòu)造構(gòu)造以元素以元素9為根的子為根的子二叉樹二叉樹99871第22頁/共43頁2021-10-16noweightparentlchildrchild1590022900037100048100051400062300073900811000980711015034110000120000130000140000150000i + 1 = 10在在前前 i -1 = 9 個元素中個元素中找找無父結(jié)點無父結(jié)點且有且有最小及最小及次小權(quán)值次小權(quán)值

10、元素的下標(biāo)元素的下標(biāo)s1 = 3s2 = 4 新結(jié)點新結(jié)點存儲于存儲于元素元素10權(quán)值權(quán)值 = 7 + 8 = 15構(gòu)造構(gòu)造元素元素10的子二叉樹的子二叉樹第23頁/共43頁2021-10-16noweightparentlchildrchild1590022900037100048100051400062300073900811110098117110150341119098120000130000140000150000i + 1= 11在前在前 i -1 = 10 個元素中個元素中找找無父結(jié)點無父結(jié)點且有且有最小及最小及次小權(quán)值次小權(quán)值元素的下標(biāo)元素的下標(biāo)s1 = 9s2 = 8 新結(jié)點

11、新結(jié)點存儲于存儲于元素元素11權(quán)值權(quán)值 = 8 + 11 = 19構(gòu)造構(gòu)造元素元素11的子二叉樹的子二叉樹第24頁/共43頁2021-10-16noweightparentlchildrchild15900229000371000481000514120062300073900811110098117110151234111909812290510130000140000150000i + 1 = 12在前在前 i -1 = 11 個元素中個元素中找找無父結(jié)點無父結(jié)點且有且有最小及最小及次小權(quán)值次小權(quán)值元素的下標(biāo)元素的下標(biāo)s1 = 5s2 = 10 新結(jié)點新結(jié)點存儲于存儲于元素元素12權(quán)值權(quán)值

12、 = 14 + 15 = 29構(gòu)造構(gòu)造元素元素12的子二叉樹的子二叉樹第25頁/共43頁2021-10-16noweightparentlchildrchild159002290003710004810005141200623130073900811110098117110151234111913981229051013420116140000150000i + 1= 13在前在前 i -1 = 12 個元素中個元素中找找無父結(jié)點無父結(jié)點且有且有最小及最小及次小權(quán)值次小權(quán)值元素的下標(biāo)元素的下標(biāo)s1 = 11s2 = 6 新結(jié)點新結(jié)點存儲于存儲于元素元素13權(quán)值權(quán)值 = 19 + 23 = 42

13、構(gòu)造構(gòu)造元素元素13的子二叉樹的子二叉樹第26頁/共43頁2021-10-16noweightparentlchildrchild1590022914003710004810005141200623130073900811110098117110151234111913981229145101342011614580212150000i + 1 = 14在前在前 i -1 = 13 個元素中個元素中找找無父結(jié)點無父結(jié)點且有且有最小及最小及次小權(quán)值次小權(quán)值元素的下標(biāo)元素的下標(biāo)s1 = 2s2 = 12 新結(jié)點新結(jié)點存儲于存儲于元素元素14權(quán)值權(quán)值 = 29 + 29 = 58構(gòu)造構(gòu)造元素元素14

14、的子二叉樹的子二叉樹第27頁/共43頁2021-10-16noweightparentlchildrchild1590022914003710004810005141200623130073900811110098117110151234111913981229145101342151161458152121510001314i + 1 = 15在前在前 i -1 = 14 個元素中個元素中找找無父結(jié)點無父結(jié)點且有且有最小及最小及次小權(quán)值次小權(quán)值元素的下標(biāo)元素的下標(biāo)s1 = 13s2 = 14 新結(jié)點新結(jié)點存儲于存儲于元素元素15權(quán)值權(quán)值 = 42 + 58 = 100構(gòu)造構(gòu)造元素元素15的子

15、二叉樹的子二叉樹第28頁/共43頁30513714 573841188915102922912581419114213236100 15weightparentlchildrchild15900229140037100048100051412006231300719008111100981117101512341112191389291451013421561114581521215100013142.HT的終態(tài)的終態(tài)第29頁/共43頁2021-10-16int Huffman( HuffmanTree HT, int *w , int n ) for( i = 1 ; i 2*n ;i+)

16、/ 初始化初始化 HTi.parent = HTi.lchild = HTi.rchild = 0; if (i = n) HTi.weight = wi-1; / 前前 n 個結(jié)點賦權(quán)值個結(jié)點賦權(quán)值 else HTi.weight = 0; / 后后 n-1 個結(jié)點預(yù)留個結(jié)點預(yù)留 /初始化結(jié)束初始化結(jié)束/ 待續(xù)待續(xù)第30頁/共43頁2021-10-16int Huffman( HuffmanTree HT, int *w , int n ) / 續(xù)續(xù) for ( i = n+1 ; i =2*n-1 ; i+) / 構(gòu)造構(gòu)造 HUFFMAN樹樹 Select ( HT , i - 1 , &

17、s1, &s2 ) ; / 最小及次小權(quán)元下標(biāo)最小及次小權(quán)元下標(biāo) HTs1.parent = i; / 設(shè)置新根結(jié)點設(shè)置新根結(jié)點 HTs2.parent = i; HTi.weight = HTs1.weight + HTs2.weight ; / 權(quán)值和權(quán)值和 HTi.lchild = s1; / 根結(jié)點與子結(jié)點鏈接根結(jié)點與子結(jié)點鏈接 HTi.rchild = s2; /結(jié)束構(gòu)造結(jié)束構(gòu)造第31頁/共43頁33第32頁/共43頁34第33頁/共43頁35第34頁/共43頁問題問題1Huffman樹的不唯一性是否會影響到Huffman編碼？問題問題3方法能否擴(kuò)展到k元Huffman編碼？Huffman樹的構(gòu)造中最困難的部分是什么？問題問題2第35頁/共43頁371.定義和性質(zhì)定義和性質(zhì)2.存儲結(jié)構(gòu)存儲結(jié)構(gòu)3.遍歷遍歷4.線索化線索化順序結(jié)構(gòu)順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)二叉鏈表二叉鏈表三叉鏈表三叉鏈表先序線索樹先序線索樹中序線索樹中序線索樹后序線索樹后序線索樹樹樹二叉樹二叉樹森林森林Huffman編碼編碼先先序序