哈夫曼樹(shù)與樹(shù)的應(yīng)用(編輯修改稿)
2024-11-16 20:36 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 1,T2,… ,Tn}， 其中每一棵二叉樹(shù) Ti中只有一個(gè)帶權(quán)為 wi的根結(jié)點(diǎn) ， 其左右子樹(shù)為空 。 ② 在 F中選取兩棵權(quán)值最小的樹(shù)作為左右子樹(shù)以構(gòu)造一棵新的二叉樹(shù)，且新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。 ③ 在 F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入 F中。 ④ 重復(fù) (2)和 (3)，直到 F中只含一棵樹(shù)為止 。 Hu Junfeng 16 哈夫曼樹(shù)的構(gòu)造過(guò)程 6 12 2 3 2 3 5 6 12 2 3 5 6 11 12 2 3 5 6 11 12 23 4棵只有根的二叉樹(shù) 3合并得到 3棵二叉樹(shù) 6合并得到 2棵二叉樹(shù) 1 12合并得到 1棵二叉樹(shù) 左右選擇不同，得到的 HuffMan樹(shù)形態(tài)不同，但 WPL相同 。 Hu Junfeng 17 哈夫曼樹(shù)的存儲(chǔ)實(shí)現(xiàn) ? 存儲(chǔ)結(jié)構(gòu)可以有多種，如二叉鏈表、三叉鏈表等。下面給出一種順序結(jié)構(gòu) (一維數(shù)組），結(jié)點(diǎn)結(jié)構(gòu)： – ww: 以該結(jié)點(diǎn)為根的子樹(shù)中所有外部結(jié)點(diǎn)的加權(quán)和。 – parent: 父結(jié)點(diǎn)在數(shù)組中的存儲(chǔ)位置（下標(biāo)），根無(wú)父，設(shè)為 1。 – llink: 左孩子存儲(chǔ)位置，對(duì)于外部結(jié)點(diǎn)，無(wú)孩子，設(shè)為 1。 – rlink: 右孩子存儲(chǔ)位置，對(duì)于外部結(jié)點(diǎn)，無(wú)孩子，設(shè)為 1。 ww parent llink rlink Hu Junfeng 18 哈夫曼樹(shù)的表示 2 ? 假定外部結(jié)點(diǎn)個(gè)數(shù)為 m，則內(nèi)部結(jié)點(diǎn)個(gè)數(shù)必為 m1，因此最后得到的 HuffMan樹(shù)必定有 2m1個(gè)結(jié)點(diǎn)。因此，用 2m1個(gè)元素的一維數(shù)組就可以存儲(chǔ)該 HuffMan樹(shù)。每個(gè)元素表示一個(gè)結(jié)點(diǎn)，前 m個(gè)存儲(chǔ)外部結(jié)點(diǎn)，后 m1個(gè)用于內(nèi)部結(jié)點(diǎn)。 ? struct HtNode /*哈夫曼樹(shù)結(jié)點(diǎn)的結(jié)構(gòu) */ { int ww。 int parent, llink, rlink。 }。 Hu Junfeng 19 哈夫曼樹(shù)的表示 3 ? struct HtTree /*哈夫曼樹(shù)類(lèi)型 */ { int m。 /*外部結(jié)點(diǎn)的個(gè)數(shù) */ int root。 /* 哈夫曼樹(shù)根在數(shù)組中的位置 */ struct HtNode *ht。 /*存放 2m1個(gè)結(jié)點(diǎn)的數(shù)組 */ }。 typedef struct HtTree *PHtTree。 /* 哈夫曼樹(shù)類(lèi)型的指針類(lèi)型 */ struct HtTree /*哈夫曼樹(shù)類(lèi)型 */ { stru
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1