如何構(gòu)造最優(yōu)二叉樹 什么是最優(yōu)二叉樹？
什么是最優(yōu)二叉樹？給定n個權(quán)重作為n個葉節(jié)點，構(gòu)造一棵二叉樹。如果加權(quán)路徑長度達(dá)到最小值，這種二叉樹稱為最優(yōu)二叉樹。簡單地認(rèn)為葉節(jié)點的值是平均路徑最短的二叉樹。它相當(dāng)于對一個n態(tài)隨機源進(jìn)行編碼，每個態(tài)
什么是最優(yōu)二叉樹？
給定n個權(quán)重作為n個葉節(jié)點，構(gòu)造一棵二叉樹。如果加權(quán)路徑長度達(dá)到最小值，這種二叉樹稱為最優(yōu)二叉樹。簡單地認(rèn)為葉節(jié)點的值
是平均路徑最短的二叉樹。它相當(dāng)于對一個n態(tài)隨機源進(jìn)行編碼，每個態(tài)都有一個概率，由Huffman樹編碼的碼長就是葉節(jié)點的深度。證明了用哈夫曼樹編碼的平均碼長是最短的，具體的證明方法可以參考貪心法