樹 - 哈夫曼樹及其應用 - 最優二叉樹（一）

　　樹的路徑長度

　　樹的路徑長度是從樹根到樹中每一結點的路徑長度之和在結點數目相同的二叉樹中完全二叉樹的路徑長度最短

　　樹的帶權路徑長度(Weighted Path Length of Tree簡記為WPL)

　　結點的權在一些應用中賦予樹中結點的一個有某種意義的實數

　　結點的帶權路徑長度結點到樹根之間的路徑長度與該結點上權的乘積

　　樹的帶權路徑長度(Weighted Path Length of Tree)定義為樹中所有葉結點的帶權路徑長度之和通常記為

　　

　　其中

　　n表示葉子結點的數目

　　w i 和l i 分別表示葉結點k i 的權值和根到結點k i 之間的路徑長度

　　樹的帶權路徑長度亦稱為樹的代價

　　最優二叉樹或哈夫曼樹

　　在權為w l w …w n 的n個葉子所構成的所有二叉樹中帶權路徑長度最小(即代價最小)的二叉樹稱為 最優二叉樹 或

　　哈夫曼樹

　　【例】給定個葉子結點abc和d分別帶權和構造如下圖所示的三棵二叉樹(還有許多棵)它們的帶權路徑長度分別

　　為

　　(a)WPL=*+*+*+*=

　　(b)WPL=*+*+*+*=

　　(c)WPL=*+*+*+*=

　　其中(c)樹的WPL最小可以驗證它就是哈夫曼樹

　　

　　注意

　　① 葉子上的權值均相同時完全二叉樹一定是最優二叉樹否則完全二叉樹不一定是最優二叉樹

　　② 最優二叉樹中權越大的葉子離根越近

　　③ 最優二叉樹的形態不唯一WPL最小

From:http://tw.wingwit.com/Article/program/sjjg/201311/23865.html