1/39,哈夫曼樹構(gòu)造及其編碼,主講人: 程玉勝,2013.11.29,數(shù)據(jù)結(jié)構(gòu)精品資源共享課,2/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,3/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,4/39,二叉樹、樹、森林,N個結(jié)點的二叉樹中結(jié)點空域的個數(shù)是【 ？】,證明的方法：從結(jié)點數(shù)和分支數(shù)兩個角度來證明。,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,在一棵度為3的樹中，其中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為 個,思考,樹、森林到二叉樹的相互轉(zhuǎn)換,5/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,6/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,7/39,成績判定問題 1,把下面成績轉(zhuǎn)換為5分制，計算不同的if語句比較的次數(shù)，假設(shè)100個學(xué)生。,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,第一種寫法：if(cj<6) cout<<“不及格” elseif(cj<70) cout<<“及格” elseif(cj<80) cout<<“中等” elseif(cj<90)cout<<“良好” else cout<<“優(yōu)秀”,8/39,成績判定問題 2,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,對應(yīng)的流程圖：,(1)、計算2種方法在比較次數(shù)上的時間差異性：,1*5+2*15+3*40+4*30+4*10=315,3*5+3*15+2*40+2*30+2*20=220,(2)、哪個二叉樹好？怎樣保證比較次數(shù)最少呢？,最好的 最優(yōu)二叉樹,9/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,10/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,11/39,哈夫曼樹的相關(guān)定義,樹的帶權(quán)路徑長度定義為： 樹中所有葉子結(jié)點的帶權(quán)路徑長度之和 WPL(T) = wklk (對所有葉子結(jié)點),復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,最優(yōu)二叉樹（哈夫曼樹） 使 WPL最小的二叉樹,WPL(T)=72+52+23+43+92 =60,12/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,13/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,14/39,構(gòu)造方法 1,假設(shè)給定n個權(quán)值的結(jié)點構(gòu)造：,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,（1）：n個結(jié)點看成n顆樹F （2）：在F中選取兩個最小的結(jié)點，作為左 右子樹，且根結(jié)點的權(quán)值等于左右子 樹權(quán)值之和 （3）：在F中刪除這兩顆樹，并把剛得到的 二叉樹加入F中 （4）：重復(fù)（2）-（3），一棵樹結(jié)束,15/39,構(gòu)造方法 2,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,例,已知權(quán)值 W= 5, 6, 2, 9, 7 ,9,5,6,2,7,5,2,7,6,9,7,6,7,13,9,16/39,構(gòu)造方法 3,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,例,9,16,29,5個葉子結(jié)點，構(gòu)造后有多少個結(jié)點？,17/39,構(gòu)造算法 1,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,思考,有度為1的結(jié)點嗎？，n個葉子結(jié)點構(gòu)造的哈夫曼樹有多少結(jié)點？,算法,數(shù)組 HT1m 存放結(jié)點 其中 m=2n-1 前n 個(1 n)為葉結(jié)點 最后一個為根結(jié)點 數(shù)組 HC 1n 存放編碼,18/39,構(gòu)造算法 2,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,算法,void HuffmanCoding (HuffmanTree ,例:設(shè)n=5, w=5,6,2,9,7，試設(shè)計 huffman (m=2*5-1=9),19/39,構(gòu)造算法 2,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,5,2,7,6,9,7,6,7,13,9,1,3,6,1,3,6,7,3,1,2,5,7,20/39,構(gòu)造算法 3,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,1,9,16,29,3,6,2,5,7,4,8,9,7 8 1 3,13 9 2 5,16 9 4 6,29 0 7 8,6 7 6 8 7,21/39,構(gòu)造算法 4,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,for( i=n+1;i<=m;+i) /構(gòu)造 Huffman樹 Select(HT,i-1, s1, s2); /在HTk(1ki-1)中選擇兩個其雙親域為0, / 且權(quán)值最小的結(jié)點, / 并返回它們在HT中的序號s1和s2 HTs1.parent=i; HTs2 .parent=i; /表示從F中刪除s1,s2 HTi.lch=s1; HTi.rch=s2 ; /s1,s2分別作為i的左右孩子 HTi.weight=HTs1.weight + HTs2 .weight; /i 的權(quán)值為左右孩子權(quán)值之和 ,22/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,23/39,內(nèi)容提要,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,24/39,HFM編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,9,16,29,0,0,0,0,1,1,1,1,00,01,11,100,101,25/39,HFM編碼,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,/從葉子到根逆向求每個字符的哈夫曼編碼 HC=new CodeNoden+1;cd=new charn; cdn-1=0;/編碼結(jié)束符 for(i=1;i<=n;+i) /依次求各葉子的編碼 start=n-1;/編碼起始位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lch=c)cd-start=0; else cd-start=1; HCi.bits=new charn-start; /為第i個葉子分配空間 strcpy(HCi.bits, ,26/39,哈夫曼應(yīng)用,復(fù)習(xí) 知識點引入 哈夫曼樹相關(guān)定義 哈夫曼樹構(gòu)造 哈夫曼編碼,已知某相同在通信聯(lián)絡(luò)中只可能出現(xiàn)8種可能字符，其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11.假設(shè)待發(fā)報文長度為100個字符，請選擇最短報文，并計算發(fā)送報文的長度。,例,27/39,謝謝 !,歡迎通過數(shù)據(jù)結(jié)構(gòu)精品課程網(wǎng)站 http:/210.45.168.34:8080/08/sjjg/Learning/SelfLearningDS/index.asp,Thanks for Your Attention,