哈夫曼樹中的名詞意思

　　樹的權值：每個樹節點所在的那個數字。

　　路徑：兩個節點之間所經過的分支。

　　路徑長度： 某一路徑上的分支條數。

　　節點帶權路徑長度： 節點的權值*該節點的路徑長度。

　　樹帶權路徑長度：所有葉子節點的帶全路徑長度之和。

　　樹帶權路徑長度：所有葉子節點的帶全路徑長度之和。

　　1、基本概念

　　a、路徑和路徑長度

　　若在一棵樹中存在著一個結點序列 k1，k2，……，kj， 使得 ki是ki+1 的雙親（1《=i《j），則稱此結點序列是從 k1 到 kj 的路徑。

　　從 k1 到 kj 所經過的分支數稱為這兩點之間的路徑長度，它等于路徑上的結點數減1.

　　b、結點的權和帶權路徑長度

　　在許多應用中，常常將樹中的結點賦予一個有著某種意義的實數，我們稱此實數為該結點的權，（如下面一個樹中的藍色數字表示結點的權）

　　結點的帶權路徑長度規定為從樹根結點到該結點之間的路徑長度與該結點上權的乘積。

　　c、樹的帶權路徑長度

　　樹的帶權路徑長度定義為樹中所有葉子結點的帶權路徑長度之和，公式為：

　　其中，n表示葉子結點的數目，wi 和 li 分別表示葉子結點 ki 的權值和樹根結點到 ki 之間的路徑長度。

　　如下圖中樹的帶權路徑長度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4 = 122

　　d、哈夫曼樹

　　哈夫曼樹又稱最優二叉樹。它是 n 個帶權葉子結點構成的所有二叉樹中，帶權路徑長度 WPL 最小的二叉樹。

　　如下圖為一哈夫曼樹示意圖。