路徑二叉樹(shù)

是程序算法中的一種算法模式。

在二叉樹(shù)中出現(xiàn)空的子樹(shù)（包括樹(shù)葉）上增加空的樹(shù)葉，使其成為滿二叉樹(shù)的二叉樹(shù)稱之為擴(kuò)充二叉樹(shù)。

最優(yōu)二叉樹(shù)，也稱哈夫曼(Haffman)樹(shù)，是指對(duì)于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)。

那么什么是二叉樹(shù)的帶權(quán)路徑長(zhǎng)度呢?

在前面我們介紹過(guò)路徑和結(jié)點(diǎn)的路徑長(zhǎng)度的概念，而二叉樹(shù)的路徑長(zhǎng)度則是指由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長(zhǎng)度之和。如果二叉樹(shù)中的葉結(jié)點(diǎn)都具有一定的權(quán)值，則可將這一概念加以推廣。設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度，記為:

WPL= Wk·Lk

其中Wk為第k個(gè)葉結(jié)點(diǎn)的權(quán)值，Lk 為第k個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度。如圖7.2所示的二叉樹(shù)，它的帶權(quán)路徑長(zhǎng)度值WPL=2×2+4×2+5×2+3×2=28。

在給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出不同的帶權(quán)二叉樹(shù)。例如，給出4個(gè)葉結(jié)點(diǎn)，設(shè)其權(quán)值分別為1，3，5，7，我們可以構(gòu)造出形狀不同的多個(gè)二叉樹(shù)。這些形狀不同的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度將各不相同。圖7.3給出了其中5個(gè)不同形狀的二叉樹(shù)。

這五棵樹(shù)的帶權(quán)路徑長(zhǎng)度分別為:

(a)WPL=1×2+3×2+5×2+7×2=32

(b)WPL=1×3+3×3+5×2+7×1=29

(c)WPL=1×2+3×3+5×3+7×1=33

(d)WPL=7×3+5×3+3×2+1×1=43

(e)WPL=7×1+5×2+3×3+1×3=29

最優(yōu)二叉樹(shù)算法

最優(yōu)二叉樹(shù)算法

由此可見(jiàn)，由相同權(quán)值的一組葉子結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有不同的形態(tài)和不同的帶權(quán)路徑長(zhǎng)度，那么如何找到帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)(即哈夫曼樹(shù))呢?根據(jù)哈夫曼樹(shù)的定義，一棵二叉樹(shù)要使其WPL值最小，必須使權(quán)值越大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。

哈夫曼(Haffman)依據(jù)這一特點(diǎn)于1952年提出了一種方法，這種方法的基本思想是:

(1)由給定的n個(gè)權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二叉樹(shù)的集合F={T1，T2，…，Tn};

(2)在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和;

(3)在集合F中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到集合F中;

(4)重復(fù)(2)(3)兩步，當(dāng)F中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)便是所要建立的哈夫曼樹(shù)。

1

/ \

2 3

\ /

4 5 是均衡二叉樹(shù)，因?yàn)樗サ羧~結(jié)點(diǎn)及相應(yīng)的樹(shù)枝后，

變成了：

1

/ \

2 3 ，這是一個(gè)二叉樹(shù)。

1

/ \

2 3

而 \ / \ 則不是，因?yàn)樗サ羧~結(jié)點(diǎn)及相應(yīng)的樹(shù)枝后，

4 5 6

/

7

變成了：

1

/ \

2 3

\

4

很顯然，這并不是一個(gè)完全二叉樹(shù)。