4-7最優(yōu)二叉樹v第四章樹和二叉樹哈夫曼算法學(xué)什么？哈夫曼編碼最優(yōu)二叉樹（哈夫曼樹）的基本概念最優(yōu)二叉樹葉子結(jié)點(diǎn)的權(quán)值：對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量二叉樹的帶權(quán)路徑長(zhǎng)度：從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和取決于具體問題第k個(gè)葉子的權(quán)值從根結(jié)點(diǎn)到第k個(gè)葉子的路徑長(zhǎng)度最優(yōu)二叉樹（哈夫曼樹）：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹323428324552345432最優(yōu)二叉樹最優(yōu)二叉樹有什么特點(diǎn)?（1）權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)（2）只有度為0和度為2的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn)4-7-1哈夫曼算法v第四章樹和二叉樹哈夫曼算法【問題】給定一組權(quán)值，構(gòu)造最優(yōu)二叉樹1.初始化：由n個(gè)權(quán)值構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，得到一個(gè)二叉樹集合F＝{T1，T2，…，Tn}；2.重復(fù)下述操作，直到集合F中只剩下一棵二叉樹

2.1選取與合并：在F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹分別作為左右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹根結(jié)點(diǎn)的權(quán)值之和；

2.2刪除與加入：在F中刪除作為左右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；【想法——哈夫曼算法的基本思想】例給定權(quán)值集合{2，4，5，3}初始化選取與合并刪除與加入245323

54523

5運(yùn)行實(shí)例23

545

923

545

914【算法——數(shù)據(jù)表示】如何存儲(chǔ)哈夫曼樹呢？23

545

914采用數(shù)組還是鏈表呢？

n

個(gè)葉子結(jié)點(diǎn)合并

n-1次n-1個(gè)分支結(jié)點(diǎn)哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)設(shè)數(shù)組huffTree[2n-1]須存儲(chǔ)哪些關(guān)系呢？選取根結(jié)點(diǎn)權(quán)值最小的二叉樹存儲(chǔ)parent信息作為左右子樹進(jìn)行合并存儲(chǔ)lchild和rchild信息weightlchildrchildparent哈夫曼算法23

545

914weightlchildrchildparentstructElemType{

intweight;/*假定權(quán)值為整數(shù)*/

intparent,lchild,rchild;};函數(shù)原型：voidHuffmanTree(ElemTypehuffTree[],intw[],intn)哈夫曼算法【算法——數(shù)據(jù)表示】如何存儲(chǔ)哈夫曼樹呢？【算法——數(shù)據(jù)處理過程】-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1例給定權(quán)值集合{2，4，5，3}24530123456weightparentlchildrchildfor(i=0;i<2*n-1;i++){huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}算法描述：哈夫曼算法-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-124530123456weightparentlchildrchildfor(i=0;i<n;i++)huffTree[i].weight=w[i];算法描述：例給定權(quán)值集合{2，4，5，3}哈夫曼算法【算法——數(shù)據(jù)處理過程】2453-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-124530123456weightparentlchildrchild4523

5i1i25huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;算法描述：k例給定權(quán)值集合{2，4，5，3}哈夫曼算法【算法——數(shù)據(jù)處理過程】2453-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1245324530123456weightparentlchildrchild4523

5i1i250344huffTree[i1].parent=k;huffTree[i2].parent=k;huffTree[k].lchild=i1;huffTree[k].rchild=i2;算法描述：k例給定權(quán)值集合{2，4，5，3}哈夫曼算法【算法——數(shù)據(jù)處理過程】【程序】voidHuffmanTree(ElemTypehuffTree[],intw[],intn){inti,k,i1,i2;

}for(i=0;i<2*n-1;i++)/*初始化，所有結(jié)點(diǎn)均沒有雙親和孩子*/{huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}for(k=n;k<2*n-1;k++)/*n-1次合并*/{

Select(huffTree,i1,i2);/*權(quán)值最小的兩個(gè)根結(jié)點(diǎn)下標(biāo)為i1和i2*/huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;huffTree[i1].parent=k;huffTree[i2].parent=k;huffTree[k].lchild=i1;huffTree[k].rchild=i2;}for(i=0;i<n;i++)/*構(gòu)造n棵只含有根結(jié)點(diǎn)的二叉樹*/huffTree[i].weight=w[i];算法實(shí)現(xiàn)4-7-2哈夫曼編碼v第四章樹和二叉樹編碼編碼：給每一個(gè)對(duì)象標(biāo)記一個(gè)二進(jìn)制位串來表示一組對(duì)象等長(zhǎng)編碼：用長(zhǎng)度相等的二進(jìn)制位串表示一組對(duì)象酸甜

01酸甜苦辣00011011酸

甜苦辣

咸麻000

001

010

011

100101編碼的目的是什么?數(shù)字化編碼效率取決于編碼長(zhǎng)度如果每個(gè)對(duì)象的使用頻率不等，如何獲得較高的編碼效率市區(qū)出生日期順序校驗(yàn)身份證號(hào)碼不等長(zhǎng)編碼：表示一組對(duì)象的二進(jìn)制位串的長(zhǎng)度不相等設(shè)計(jì)不等長(zhǎng)編碼時(shí)，必須考慮解碼的唯一性

字符串：AABACD

編碼：00100110ABCDE

一組對(duì)象3525151510

使用頻率01011011

不等長(zhǎng)編碼前綴（無歧義）編碼保證了在解碼時(shí)不會(huì)有多種可能前綴無歧義編碼（簡(jiǎn)稱前綴編碼）：在一組編碼中，任一編碼都不是其它任何編碼的前綴解碼

00100110

00100110

解碼：哈夫曼編碼如何設(shè)計(jì)一個(gè)編碼效率最高的前綴編碼呢?哈夫曼編碼例一組字符{A,B,C,D,E,F,G}出現(xiàn)的頻率分別是{9,11,5,7,8,2,3}，設(shè)計(jì)最經(jīng)濟(jì)的編碼方案。00000011111195231187ABDCEFG哈夫曼編碼方案：A：00B：10C：010D：110E：111F：0110G：011151510261945等長(zhǎng)編碼的長(zhǎng)度：3哈夫曼編碼的平均長(zhǎng)度：(2×9+3×5+4×2+4×3+2×11+3×7+3×8)/45=2.67該編碼方案的壓縮比是多少?(3-2.