第六章 樹和二叉樹演示

第六章樹和二叉樹演示第1頁(yè)，共20頁(yè)，2023年，2月20日，星期三第六章樹和二叉樹6.7哈夫曼樹及應(yīng)用6.7.1哈夫曼樹及構(gòu)造6.7.1哈夫曼編碼

第2頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用6.7.1哈夫曼樹及構(gòu)造1哈夫曼樹的概念路徑：從一個(gè)祖先結(jié)點(diǎn)到子孫結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的路徑；路徑長(zhǎng)度：路徑上的分支數(shù)目稱為路徑長(zhǎng)度；結(jié)點(diǎn)的權(quán)：根據(jù)應(yīng)用的需要可以給樹的結(jié)點(diǎn)賦權(quán)值；結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從根到該結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積；樹的帶權(quán)路徑長(zhǎng)度=樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑之和；

通常記作WPL=wiLi哈夫曼樹：假設(shè)有n個(gè)權(quán)值(w1,

w2,…,wn)，構(gòu)造有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)有一個(gè)wi作為它的權(quán)值。則帶權(quán)路徑長(zhǎng)度最小的二叉樹稱為哈夫曼樹。第3頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用2應(yīng)用舉例在求得某些判定問題時(shí)，利用哈夫曼樹獲得最佳判定算法。例編制一個(gè)將百分制轉(zhuǎn)換成五分制的程序。最直觀的方法是利用if語句來的實(shí)現(xiàn)?？捎枚鏄涿枋雠卸ㄟ^程。參見課本P145圖6.23(a)。如果這個(gè)程序很不經(jīng)常使用，或要轉(zhuǎn)換的分?jǐn)?shù)不多，不必考慮該程序效率，我們可以按照這個(gè)流程編程?？墒侨绻摮绦蚪?jīng)常要使用或數(shù)據(jù)量很大。比如對(duì)北京市幾十萬小學(xué)生的分?jǐn)?shù)進(jìn)行轉(zhuǎn)換，在這種情況下，要考慮轉(zhuǎn)換程序的效率。

設(shè)有10000個(gè)百分制分?jǐn)?shù)要轉(zhuǎn)換，設(shè)學(xué)生成績(jī)?cè)?個(gè)等級(jí)以上的分布如下：

分?jǐn)?shù)0-5960-6970-7980-8990-100比例數(shù)0.050.150.400.300.10第4頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用按圖的判定過程，轉(zhuǎn)換一個(gè)分?jǐn)?shù)所需的比較次數(shù)=從根到對(duì)應(yīng)結(jié)點(diǎn)的路徑長(zhǎng)度。轉(zhuǎn)換10000個(gè)分?jǐn)?shù)所需的總比較次數(shù)=10000（0.051+0.152+0.43+0.34+0.14）若將學(xué)生成績(jī)?cè)?個(gè)等級(jí)以上的分布比例看作描述判定過程二叉樹葉子結(jié)顛點(diǎn)權(quán)值，（0.051+0.152+0.43+0.34+0.14）正是該二叉樹的帶權(quán)路徑長(zhǎng)度。可見要想獲得效率較高的轉(zhuǎn)換程序，可構(gòu)造以分?jǐn)?shù)的分布比例為權(quán)值的哈夫曼樹。403060155101530100第5頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用3哈夫曼樹的構(gòu)造構(gòu)造哈夫曼樹的步驟：1．根據(jù)給定的n個(gè)權(quán)值，構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，n個(gè)權(quán)值分別是這些二叉樹根結(jié)點(diǎn)的權(quán)。設(shè)F是由這n棵二叉樹構(gòu)成的集合2．在F中選取兩棵根結(jié)點(diǎn)樹值最小的樹作為左、右子樹，構(gòu)造一顆新的二叉樹，置新二叉樹根的權(quán)值=左、右子樹根結(jié)點(diǎn)權(quán)值之和；3．從F中刪除這兩顆樹，并將新樹加入F；4．重復(fù)2、3，直到F中只含一顆樹為止；第6頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用403060155101530403060155101530100例：構(gòu)造以W=（5，15，40，30，10）為權(quán)的哈夫曼樹。305101540403015510154030301551015第7頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用6.7.2哈夫曼編碼

哈夫曼樹除了能求解最優(yōu)判定問題解，還用于其他一些最優(yōu)問題的求解。這里介紹用哈夫曼樹求解數(shù)據(jù)的二進(jìn)制編碼。

在進(jìn)行數(shù)據(jù)通訊時(shí)，涉及數(shù)據(jù)編碼問題。所謂數(shù)據(jù)編碼就是數(shù)據(jù)與二進(jìn)制字符串的轉(zhuǎn)換。例如：郵局發(fā)電報(bào)，發(fā)送方將原文轉(zhuǎn)換成二進(jìn)制字符串，接收方將二進(jìn)制字符串還原成原文。原文電文（二進(jìn)制字符串）原文例要傳輸?shù)脑臑锳BACCDA

設(shè)ABCD的編碼為

A；00

B；01

C：10

D：11發(fā)送方：將ABACCDA轉(zhuǎn)換成00010010101100接收方：將00010010101100還原為ABACCDA第8頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用在數(shù)據(jù)輸傳時(shí)，為省節(jié)費(fèi)用總希望傳輸?shù)亩M(jìn)制串盡可能短。

可利用二叉樹設(shè)計(jì)不等長(zhǎng)編碼：例某通訊系統(tǒng)只使用8種字符a、b、c、d、e、f、g、h，其使用頻率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，利用二叉樹設(shè)計(jì)一種不等長(zhǎng)編碼：1）構(gòu)造以a、b、c、d、e、f、g、h為葉子結(jié)點(diǎn)的二叉樹；2）將該二叉樹所有左分枝標(biāo)記1，所有右分枝標(biāo)記0；3）從根到葉子結(jié)點(diǎn)路徑上標(biāo)記作為葉子結(jié)點(diǎn)所對(duì)應(yīng)字符的編碼；acbdgfeha:0000b:0001c:0010d:0011e:010f:011g:10h:11第9頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用應(yīng)用中每個(gè)字符的使用頻率是不一樣的。顯然，為使傳輸?shù)亩M(jìn)制串盡可能的短，使用頻率高的字符用較短編碼，使用頻率低的字符用較長(zhǎng)編碼電文總長(zhǎng)=原文中字符總數(shù)（字符x使用頻率字符x編碼長(zhǎng)度）

為設(shè)計(jì)電文總長(zhǎng)最短編碼，可通過構(gòu)造以字符使用頻率作為權(quán)值的哈夫曼樹實(shí)現(xiàn)。如何得到使二進(jìn)制串總長(zhǎng)最短編碼？第10頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用例某通訊系統(tǒng)只使用8種字符a、b、c、d、e、f、g、h，其使用頻率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11。構(gòu)造以字符使用頻率作為權(quán)值的哈夫曼樹。，將權(quán)值取為整數(shù)w=(5,29,7,8,14,23,3,11)，按哈夫曼算法構(gòu)造的一棵哈夫曼樹如下：對(duì)應(yīng)字符的編碼a:0110b:10c:1110d:1111e:110f:00g:0111h:01029195842100158

735811231429第11頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用2．構(gòu)造哈夫曼樹的算法

輸入：n個(gè)權(quán)值

結(jié)果：哈夫曼樹設(shè)用一維數(shù)組W存儲(chǔ)n個(gè)權(quán)值，用靜態(tài)三叉鏈表HT存儲(chǔ)哈夫曼樹存儲(chǔ)哈夫曼樹的靜態(tài)三叉鏈表類型定義typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹weightparentlchildrchildHTNode類型的結(jié)構(gòu)變量第12頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用wplchrch01234567891011121314155000290007000800014000230003000110008111715123419138929145104215611581521210001314哈夫曼樹哈夫曼樹對(duì)應(yīng)的靜態(tài)三叉鏈表w,p,lch,rch是weight,parent,lchild,rchild的縮寫29195842100158

735811231429第13頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用哈夫曼算法voidHuffmanTree(HuffmanTree&HT,int*w,intn){//w存放n個(gè)字符的權(quán)值（均>0），構(gòu)造赫夫曼樹HTif(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);//為哈夫曼樹分配存儲(chǔ)//空間for(p=HT,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0};//用給定的n個(gè)權(quán)//值，構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹for(;i<m;++i;++p){//按構(gòu)造哈夫曼樹的步驟2、3、4，建哈夫曼樹//在HT[1..i-1]選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2。Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;//HT[i]存放新子樹的根結(jié)點(diǎn)，HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;第14頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用例：用哈夫曼算法構(gòu)造以w=(5,29,7,8,14,23,3,11)為權(quán)值的哈夫曼樹529781423311012345678Wwplchrch01234567891011121314155000290007000800014000230003000110008111715123419138929145104215611581521210001314哈夫曼樹對(duì)應(yīng)的靜態(tài)三叉鏈表HTHT算法原始數(shù)據(jù)算法結(jié)果數(shù)據(jù)權(quán)值數(shù)組W第15頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用0123456789101112131415wplchrchHT為哈夫曼樹分配存儲(chǔ)空間哈夫曼算法主要步驟圖示第16頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用0123456789101112131415wplchrch5000290007000800014000230003000000HT算法的第一個(gè)FOR循環(huán)的執(zhí)行結(jié)果8棵只有一個(gè)結(jié)點(diǎn)的二叉樹5378

11

2314

29第17頁(yè)，共20頁(yè)，2023年，2月20日，星期三6.7哈夫曼樹及應(yīng)用HT算法的第二個(gè)FOR循環(huán)的執(zhí)行結(jié)果完整的哈夫曼樹29195842100158

735811231429靜態(tài)三叉鏈表HT對(duì)應(yīng)的哈夫曼樹構(gòu)造哈夫曼樹的過程中，新生成的結(jié)點(diǎn)wplchrch01234567891011121314155000290007000800014000230003