樹的權值：每個樹節(jié)點所在的那個數(shù)字。

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

　　路徑長度： 某一路徑上的分支條數(shù)。

　　節(jié)點帶權路徑長度： 節(jié)點的權值*該節(jié)點的路徑長度。

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

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

　　a、路徑和路徑長度

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

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

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

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

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

　　c、樹的帶權路徑長度

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

　　其中，n表示葉子結點的數(shù)目，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、哈夫曼樹

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

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