路徑二叉樹

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

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

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

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

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

WPL= Wk·Lk

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

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

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

(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)二叉樹算法

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

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

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

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

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

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

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

1

/ \

2 3

\ /

4 5 是均衡二叉樹，因為它去掉葉結(jié)點及相應(yīng)的樹枝后，

變成了：

1

/ \

2 3 ，這是一個二叉樹。

1

/ \

2 3

而 \ / \ 則不是，因為它去掉葉結(jié)點及相應(yīng)的樹枝后，

4 5 6

/

7

變成了：

1

/ \

2 3

\

4

很顯然，這并不是一個完全二叉樹。