哈夫曼樹基本概念與構(gòu)造

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

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

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

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

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

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

　　a、路徑和路徑長(zhǎng)度

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

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

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

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

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

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

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

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

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

　　d、哈夫曼樹

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

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