什么是最優(yōu)二叉樹？給定n個(gè)權(quán)重作為n個(gè)葉節(jié)點(diǎn)，構(gòu)造一棵二叉樹。如果加權(quán)路徑長(zhǎng)度達(dá)到最小值，這種二叉樹稱為最優(yōu)二叉樹。簡(jiǎn)單地認(rèn)為葉節(jié)點(diǎn)的值是平均路徑最短的二叉樹。它相當(dāng)于對(duì)一個(gè)n態(tài)隨機(jī)源進(jìn)行編碼，每個(gè)態(tài)

什么是最優(yōu)二叉樹？

給定n個(gè)權(quán)重作為n個(gè)葉節(jié)點(diǎn)，構(gòu)造一棵二叉樹。如果加權(quán)路徑長(zhǎng)度達(dá)到最小值，這種二叉樹稱為最優(yōu)二叉樹。簡(jiǎn)單地認(rèn)為葉節(jié)點(diǎn)的值

是平均路徑最短的二叉樹。它相當(dāng)于對(duì)一個(gè)n態(tài)隨機(jī)源進(jìn)行編碼，每個(gè)態(tài)都有一個(gè)概率，由Huffman樹編碼的碼長(zhǎng)就是葉節(jié)點(diǎn)的深度。證明了用哈夫曼樹編碼的平均碼長(zhǎng)是最短的，具體的證明方法可以參考貪心法