[工學(xué)]數(shù)據(jù)結(jié)構(gòu)11樹和二叉樹(更新版)
【正文】 ： 則對于編碼指令來說，還有一種指令沒有利用，即 111。 利用哈夫曼算法，可設(shè)計出最優(yōu)前綴編碼。 結(jié)點結(jié)構(gòu)： 類型定義： 哈夫曼算法 void HuffmanTree(HuffmanTree amp。i=m。 //HT[i]存放新子樹的根結(jié)點， HT[i].lchild=s1。 HT[i].weight=HT[s1].weight+HT[s2].weight。//對剩余空間進行初始化 for (i=n+1。 m=2* n1。 如在本題中規(guī)定：向左的分支標(biāo)記為 0， 向右的分支標(biāo)記為 1。 在數(shù)據(jù)傳輸時，為節(jié)省費用總希望傳輸?shù)亩M制串盡可能短。例如，下面完成的功能是要編制一個將百分制轉(zhuǎn)換成五級分制的程序。 Log以 2為底的 n 思考 1：什么樣的二叉樹的路徑長度最小？ ? 雖然完全二叉樹具有最小路徑長度的性質(zhì)，但不具有唯一性。 哈夫曼 (Huffman)樹及應(yīng)用 哈夫曼樹的概念 結(jié)點的權(quán)： 根據(jù)應(yīng)用的需要可以給樹的結(jié)點賦權(quán)值，給樹的每個結(jié)點賦予一個具有某種實際意義的實數(shù)，稱該實數(shù)為這個結(jié)點的權(quán)； 結(jié)點的帶權(quán)路徑長度： 從根到該結(jié)點的路徑長度與該結(jié)點權(quán)的乘積； 樹的帶權(quán)路徑長度 =樹中所有葉子結(jié)點的帶權(quán)路徑長度之和； 通常記作 WPL= ?ni=1 wi ? li （其中 n為葉子結(jié)點的個數(shù)， wi 為第 i個葉子結(jié)點的權(quán)值， li為第 i個葉子結(jié)點的路徑長度。 思考 2：什么樣的二叉樹的帶權(quán)路徑長度最??？ ? 例如：給定一個權(quán)值序列｛ 2,3,4,7｝，可構(gòu)造多種二叉樹形態(tài)如下： 2 哈夫曼樹的構(gòu)造 構(gòu)造哈夫曼樹的步驟： 1)根據(jù)給定的 n個權(quán)值 ，構(gòu)造 n棵只有一個根結(jié)點的二叉樹， n個權(quán)值分別是這些二叉樹根結(jié)點的權(quán)。 在進行數(shù)據(jù)通訊時，涉及數(shù)據(jù)編碼問題。 問：下面的變長編碼是否可行？ 解答：不行，因為機器無法解碼。 則，程序總位數(shù)是： 定長編碼： 3*10000=30000 哈夫曼編碼： 1*400+2*300+3*150+5*50+5*40+5*30+5*30=2200 哈夫曼編碼的平均碼長為： *1+*2+*3+*5+*5+*5+*5= 例 某通訊系統(tǒng)只使用 8種字符 a、 b、 c、 d、 e、 f、 g、 h，其使用頻率分別為, , ,。 i=n。 Select(HT, i1, s1, s2)。 帶權(quán)路徑長度＝(18+22)*4+(50+56+45+24+40)*3+48*3=949 303 191 1 12 106 85 64 48 50 56 45 40 18 22 24 40
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1