哈夫曼樹中的名詞意思

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

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

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

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

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

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

　　1、基本概念

　　a、路徑和路徑長度

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

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

　　b、結(jié)點的權(quán)和帶權(quán)路徑長度

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

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

　　c、樹的帶權(quán)路徑長度

　　樹的帶權(quán)路徑長度定義為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，公式為：

　　其中，n表示葉子結(jié)點的數(shù)目，wi 和 li 分別表示葉子結(jié)點 ki 的權(quán)值和樹根結(jié)點到 ki 之間的路徑長度。

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

　　d、哈夫曼樹

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

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