哈夫曼樹帶權(quán)路徑長度

2．樹的帶權(quán)路徑長度(Weighted Path Length of Tree,簡記為WPL)
　　結(jié)點(diǎn)的權(quán)：在一些應(yīng)用中,賦予樹中結(jié)點(diǎn)的一個(gè)有某種意義的實(shí)數(shù).
　　結(jié)點(diǎn)的帶權(quán)路徑長度：結(jié)點(diǎn)到樹根之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積.
　　樹的帶權(quán)路徑長度(Weighted Path Length of Tree)：定義為樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和,通常記為：
其中：
n表示葉子結(jié)點(diǎn)的數(shù)目
wi和li分別表示葉結(jié)點(diǎn)ki的權(quán)值和根到結(jié)點(diǎn)ki之間的路徑長度.
樹的帶權(quán)路徑長度亦稱為樹的代價(jià).
3．最優(yōu)二叉樹或哈夫曼樹
　在權(quán)為wl,w2,…,wn的n個(gè)葉子所構(gòu)成的所有二叉樹中,帶權(quán)路徑長度最小(即代價(jià)最小)的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹.
【例】給定4個(gè)葉子結(jié)點(diǎn)a,b,c和d,分別帶權(quán)7,5,2和4.構(gòu)造如下圖所示的三棵二叉樹(還有許多棵),它們的帶權(quán)路徑長度分別為：
(a)WPL=7*2+5*2+2*2+4*2=36
(b)WPL=7*3+5*3+2*1+4*2=46
(c)WPL=7*1+5*2+2*3+4*3=35
　　其中(c)樹的WPL最小,可以驗(yàn)證,它就是哈夫曼樹.
注意：
① 葉子上的權(quán)值均相同時(shí),完全二叉樹一定是最優(yōu)二叉樹,否則完全二叉樹不一定是最優(yōu)二叉樹.
② 最優(yōu)二叉樹中,權(quán)越大的葉子離根越近.
③ 最優(yōu)二叉樹的形態(tài)不唯一,WPL最小