高中信息競(jìng)賽數(shù)據(jù)結(jié)構(gòu)—樹的基礎(chǔ)知識(shí)-資料下載頁(yè)
2025-05-10 10:40本頁(yè)面
【正文】 堆 ,付出的代價(jià)為這兩堆石子的重量之和 ,如果把這 n堆石子最后合并成 1堆石子 ,怎樣合并才能使付出的代價(jià)最小 ,求出最小的代價(jià) . 七 、 最優(yōu)二叉樹 (哈夫曼樹 ) 顯然圖 (D)所示的合并方法付出的代價(jià)最小 :54 5*2+（ 2+4） *3+（ 6+7） *2=54 例如 n=5,重量 分別為 6。 2 4 6 5 11 6 7 13 24 (D) L=6+11+13+24=54 最優(yōu)二叉樹的定義 在具有 n個(gè)帶權(quán)葉結(jié)點(diǎn)的二叉樹中 ， 使所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 （ 即二叉樹的帶權(quán)路徑長(zhǎng)度 ） 為最小的二叉樹 ，稱為最優(yōu)二叉樹 （ 又稱最優(yōu)搜索樹或哈夫曼樹 ） ， 即最優(yōu)二叉樹使 （ wk—第 k個(gè)葉結(jié)點(diǎn)的權(quán)值； pk—第 k個(gè)葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度）達(dá)到最小。 最優(yōu)二叉樹的構(gòu)造方法 假定給出 n個(gè)結(jié)點(diǎn) ki(i=1‥ n)， 其權(quán)值分別為 wi(i=1‥ n)。 要構(gòu)造以此 n個(gè)結(jié)點(diǎn)為葉結(jié)點(diǎn)的最優(yōu)二叉樹 ， 其構(gòu)造方法如下： 首先 , 將 給 定 的 n 個(gè) 結(jié) 點(diǎn) 構(gòu) 成 n 棵 二 叉 樹 的 集 合F={T1,T2,…… ,Tn}。 其中每棵二叉樹 Ti中只有一個(gè)權(quán)值為 wi的根結(jié)點(diǎn) ki， 其左 、 右子樹均為空 。 然后做以下兩步 ⑴ .在 F中選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹作為左右子樹 ,構(gòu)造一棵新的二叉樹 ,并且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左 、 右子樹根結(jié)點(diǎn)的權(quán)值之和； ⑵ .在 F中刪除這兩棵二叉樹 ,同時(shí)將新得到的二叉樹加入 F中； 重復(fù) ⑴ 、 ⑵ ,直到在 F中只含有一棵二叉樹為止 。 這棵二叉樹便是最優(yōu)二叉樹 。 以上構(gòu)造最優(yōu)二叉樹的方法稱為哈夫曼 （ huffmann） 算法 。 例如：給定五個(gè)結(jié)點(diǎn) k1， k2， k3， k4， k5， 其權(quán)值分別為 1 1 1 23。 構(gòu)造最優(yōu)二叉樹的過(guò)程如下： ⑴構(gòu)造初始集合 F， F中各二叉樹根結(jié)點(diǎn)的權(quán)值分別為 16， 2，18， 16， 23（如下圖）： ⑵ 以具有權(quán)值 16及 2的根結(jié)點(diǎn)的兩棵二叉樹為左 、 右子樹 ， 構(gòu)造一棵根權(quán)值為 18的新二叉樹 ， 并從 F中刪去這兩棵二叉樹（ 如下圖 ） ： ⑶ 以同樣的方法 ， 得到一個(gè)新二叉樹的集合 F， 其根結(jié)點(diǎn)的權(quán)值分別為 23， 18， 34（ 如下圖 ） ： ⑷ 又得到一個(gè)新二叉樹的集合 F， 其根結(jié)點(diǎn)的權(quán)值分別為34， 41（ 如下圖 ） ： ⑸ 最后得到最優(yōu)二叉樹 （ 如下圖 ） ， 其根結(jié)點(diǎn)的權(quán)值為 75，結(jié)點(diǎn)數(shù)為 2*51=9。 哈夫曼編碼 使用頻率高的采用短的的編碼 ,則總的編碼長(zhǎng)度便可減少 . 例如 :在某通訊中只使用 abcd四種字符 ,其出現(xiàn)頻率分別為 :,。請(qǐng)進(jìn)行哈夫曼編碼。使通訊碼盡可能的短 ,并寫出信息： bbdaac的編碼。 {3， 5， 6， 9， 12}，下列二叉樹哪個(gè)是該整數(shù)集合對(duì)應(yīng)的霍夫曼（ Huffman）樹。 （ ） 已知如圖所示的哈夫曼樹，那么電文CDAA的編碼是 [ ] A 110100 B 11011100 C 010110111 D 11111100 若以 {4， 5， 6， 7,8}作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹 ， 則其帶權(quán)路徑長(zhǎng)度是 [ ] A 、 69 B、 70 C 、 73 D、 68 ⑥ (NOIP6)在有 N個(gè)葉子節(jié)點(diǎn)的哈夫曼樹中，其節(jié)點(diǎn)總數(shù)為（ ） B. 2N1 C. 2N+1 D. 2N 在最優(yōu)二叉樹中非葉結(jié)點(diǎn)的度均為 2， 因此采用順序存儲(chǔ)結(jié)構(gòu)為宜 。 如果帶權(quán)葉結(jié)點(diǎn)數(shù)為 n個(gè) ， 則最優(yōu)二叉樹的結(jié)點(diǎn)數(shù)為 2n1個(gè) 。 由此得出最優(yōu)二叉樹的數(shù)據(jù)類型定義 define n 葉結(jié)點(diǎn)數(shù)的上限； Int m=2*n1； //最優(yōu)二叉樹的結(jié)點(diǎn)數(shù) Struct node //結(jié)點(diǎn)類型 { int data； //權(quán)值 int prt,lch,rch,lth； //父指針 、 左 、 右指針和路徑長(zhǎng)度 } wtype=array[1‥ n] of integer； {n個(gè)葉結(jié)點(diǎn)權(quán)值的類型 } treetype=array[1‥ m] of node； {最優(yōu)二叉樹的數(shù)組類型 } node tree[m]； //其中 tree [1‥ n]為葉結(jié)點(diǎn) ,tree [n+1‥ 2n1]為中間結(jié)點(diǎn) ,根為 tree [2n1] 在最優(yōu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)中前 n個(gè)結(jié)點(diǎn)為葉結(jié)點(diǎn) 。 構(gòu)造最優(yōu)二叉樹的算法如下： int minn(int h)//在前 h個(gè)結(jié)點(diǎn)中選擇父指針為 0且權(quán)值最小的結(jié)點(diǎn) { ml=∞； for(p=1。p=h。p++) if((tree[p].prt==0)amp。amp。(m1tree[p].data)) //沒(méi)有父親結(jié)點(diǎn)且較小的結(jié)點(diǎn) {i= p。m1=tree[p].data。} return i。 } void hufm(int w[],node tree[]) { memset(tree,0,sizeof(tree))。//構(gòu)造初始集合 f for(i=1。i=n。i++)cintree[i].data； for(k=n+1。k=m。k++)//構(gòu)造最優(yōu)二叉樹生成 n1個(gè)新結(jié)點(diǎn) { //計(jì)算 k為根的左兒子和右兒子 i= min(k1)。tree[i].prt=k。tree[k].lch= i。 j= min(k1)。 tree[j].prt=k。tree[k].rch= j。 tree[k].data= tree[i].data+tree[j].data； } bt=m； } 計(jì)算每一個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度 Void ht(int t)//通過(guò)前序遍歷計(jì)算每一個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度 { if(t==m)tree[t].lth=0。 //若結(jié)點(diǎn) t為根 ,則路徑長(zhǎng)度為 0。否則結(jié)點(diǎn) t的路徑長(zhǎng)度為其父結(jié)點(diǎn)的路徑長(zhǎng)度 +1 else tree[t].lth=tree[tree[t].prt].lth+1。 if(tree[t].lch!=0){ht(tree[t].lch)。ht(tree[t].rch)。}//分別遞歸左右子樹 } 由此可見 ,葉結(jié)點(diǎn) t（ 1≤t≤n） 的帶權(quán)路徑長(zhǎng)度即為 : tree[t].lth*tree[t].data。 主 程 序 int main() { cinn。 //輸入葉節(jié)點(diǎn)個(gè)數(shù) bt=hufm(w,tree)。//計(jì)算最優(yōu)二叉樹 tree和根序號(hào) bt ht(bt)。//計(jì)算每一個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度 for(i=1。i=n。i++) couttree[i].lth*tree[i].data“ ”。 //輸出每個(gè)葉節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度 return 0。 }
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1