怎樣求哈夫曼樹(shù)的平均編碼長(zhǎng)？怎樣求哈夫曼樹(shù)？假設(shè)用于通信2113的消息由字符集{a、B、C、D、e、F、G、H}中的5261個(gè)字母組成，消息中出現(xiàn)這八個(gè)字母的概率為4102，即{0.07、0.19、0

怎樣求哈夫曼樹(shù)的平均編碼長(zhǎng)？怎樣求哈夫曼樹(shù)？

假設(shè)用于通信2113的消息由字符集{a、B、C、D、e、F、G、H}中的5261個(gè)字母組成，消息中出現(xiàn)這八個(gè)字母的概率為4102，即{0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10}。哈夫曼碼1653可以從上面的編碼表中得到：A:1001 B:01 C:10111 D:1010 e:11 F:10110 G:00 h:1000，三位二進(jìn)制等長(zhǎng)編碼的平均長(zhǎng)度為3，哈夫曼樹(shù)編碼的平均長(zhǎng)度為4*0.07 2*0.19 5*0.02 4*0.06 2*0.32 5*0.03 2*0.21 4*0.10=2.61 2.61/3=0.87%，平均碼長(zhǎng)為等長(zhǎng)碼的87%，平均壓縮比為13%。由于定長(zhǎng)碼已經(jīng)使用了相同的位數(shù)，這個(gè)條件保證了任何字符的碼都不會(huì)成為其他碼的前綴，所以這種情況只發(fā)生在變長(zhǎng)碼中，我們必須用一個(gè)條件來(lái)制作常規(guī)長(zhǎng)度碼。這個(gè)條件是，如果我們想成為壓縮碼，可變長(zhǎng)度的代碼必須是前綴碼。所謂前綴碼，是指任何一個(gè)字符的編碼不能是另一個(gè)字符編碼的前綴。

怎樣求哈夫曼樹(shù)的平均編碼長(zhǎng)度？

創(chuàng)建一個(gè)結(jié)構(gòu)數(shù)組，每個(gè)成員都有一個(gè)指向結(jié)構(gòu)的指針，左，右，權(quán)重值。隨機(jī)初始化值。將每個(gè)節(jié)點(diǎn)的左側(cè)和右側(cè)設(shè)置為null。從陣列中隨機(jī)選取三個(gè)節(jié)點(diǎn)，讓其中一個(gè)節(jié)點(diǎn)的左右兩側(cè)分別指向另外兩個(gè)節(jié)點(diǎn)。等等。（節(jié)點(diǎn)是否被使用，要自己判斷，頂點(diǎn)也要自己記住。數(shù)組應(yīng)該是奇數(shù)（有一個(gè)結(jié)束節(jié)點(diǎn)，需要2N-1個(gè)節(jié)點(diǎn)）。用指針查找路徑的長(zhǎng)度，從節(jié)點(diǎn)開(kāi)始，直到指針為空。

哈夫曼樹(shù)怎樣構(gòu)造編碼？

首先構(gòu)造了哈夫曼樹(shù)，并給出了哈夫曼樹(shù)的構(gòu)造規(guī)則：假設(shè)有n個(gè)權(quán)值，構(gòu)造的哈夫曼樹(shù)有n個(gè)葉節(jié)點(diǎn)。N個(gè)權(quán)值設(shè)為W1，W2哈夫曼樹(shù)的構(gòu)造規(guī)則如下：（1）W1，W2（2）在林中選取根節(jié)點(diǎn)權(quán)值最小的兩棵樹(shù)，合并為一棵新樹(shù)的左右子樹(shù)，新樹(shù)的根節(jié)點(diǎn)的權(quán)重是其左右子樹(shù)的根節(jié)點(diǎn)的權(quán)重之和；（3）從林中刪除所選的兩棵樹(shù)，并將新樹(shù)添加到林中；（4）重復(fù)步驟（2）和（3），直到林中只剩下一棵樹(shù)。構(gòu)造完成后，從樹(shù)的根節(jié)點(diǎn)開(kāi)始，默認(rèn)的左子樹(shù)為0，右子樹(shù)為1，直到葉節(jié)點(diǎn)。葉節(jié)點(diǎn)的代碼是必需的代碼。例如，ABCDEF的權(quán)重是812520411，哈夫曼樹(shù)是：60/2337//f（11）B（12）17D（20）/a（8）9/e（4）C（5）編碼是：a:100，B:01，C:1011，D:11，e:1010，f:00