路徑二叉樹

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

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

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

那么什么是二叉樹的帶權路徑長度呢?

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

WPL= Wk·Lk

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

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

這五棵樹的帶權路徑長度分別為:

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

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

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

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

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

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

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

1

/ \

2 3

\ /

4 5 是均衡二叉樹，因為它去掉葉結點及相應的樹枝后，

變成了：

1

/ \

2 3 ，這是一個二叉樹。

1

/ \

2 3

而 \ / \ 則不是，因為它去掉葉結點及相應的樹枝后，

4 5 6

/

7

變成了：

1

/ \

2 3

\

4

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