最優(yōu)二叉樹算法基本概念

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

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

在前面我們介紹過(guò)路徑和結(jié)點(diǎn)的路徑長(zhǎng)度的概念，而二叉樹的路徑長(zhǎng)度則是指由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長(zhǎng)度之和。如果二叉樹中的葉結(jié)點(diǎn)都具有一定的權(quán)值，則可將這一概念加以推廣。設(shè)二叉樹具有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹的帶權(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所示的二叉樹，它的帶權(quán)路徑長(zhǎng)度值WPL=2×2+4×2+5×2+3×2=28。

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

這五棵樹的帶權(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)二叉樹算法

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

由此可見，由相同權(quán)值的一組葉子結(jié)點(diǎn)所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長(zhǎng)度，那么如何找到帶權(quán)路徑長(zhǎng)度最小的二叉樹(即哈夫曼樹)呢?根據(jù)哈夫曼樹的定義，一棵二叉樹要使其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)的二叉樹，從而得到一個(gè)二叉樹的集合F={T1，T2，…，Tn};

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

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

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

在實(shí)際應(yīng)用中，常常要考慮一個(gè)問(wèn)題:如何設(shè)計(jì)一棵二叉樹，使得執(zhí)行路徑最短，即算法的效率最高。

例1.快遞包裹的郵資問(wèn)題

假設(shè)郵政局的包裹自動(dòng)測(cè)試系統(tǒng)能夠測(cè)出包裹的重量，如何設(shè)計(jì)一棵二叉樹將包裹根據(jù)重量及運(yùn)距進(jìn)行分類從而確定郵資。

國(guó)內(nèi)快遞包裹資費(fèi) 單位:元

(2004年1月1日起執(zhí)行)

表1 國(guó)家郵政局制定的快遞包裹參考標(biāo)準(zhǔn)

根據(jù)表1可以制定出許多種二叉樹，但不同的二叉樹判定的次數(shù)可能不一樣，執(zhí)行的效率也不同。

鐵球分類

現(xiàn)有一批球磨機(jī)上的鐵球，需要將它分成四類:直徑不大于20的屬于第一類;直徑大于20而不大于50的屬于第二類;直徑大于50而不大于100的屬于第三類;其余的屬于第四類;假定這批球中屬于第一、二、三、四類鐵球的個(gè)數(shù)之比例是1:2:3:4。

我們可以把這個(gè)判斷過(guò)程表示為 圖1中的兩種方法:

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

兩種判斷二叉樹示意圖

那么究竟將這個(gè)判斷過(guò)程表示成哪一個(gè)判斷框，才能使其執(zhí)行時(shí)間最短呢?讓我們對(duì)上述判斷框做一具體的分析。

假設(shè)有1000個(gè)鐵球，則各類鐵球的個(gè)數(shù)分別為:100、200、300、400;

對(duì)于圖7.1中的上圖和下圖比較的次數(shù)分別如表所示:

左圖 和下圖

表2 兩種判斷二叉樹比較次數(shù)

過(guò)上述分析可知，圖1中右圖所示的判斷框的比較次數(shù)遠(yuǎn)遠(yuǎn)小于左圖所示的判斷框的比較次數(shù)。為了找出比較次數(shù)最少的判斷框，將涉及到樹的路徑長(zhǎng)度問(wèn)題。

從上述算法中可以看出，F(xiàn)實(shí)際上是森林，該算法的思想是不斷地進(jìn)行森林F中的二叉樹的"合并"，最終得到哈夫曼樹。

在構(gòu)造哈夫曼樹時(shí)，可以設(shè)置一個(gè)結(jié)構(gòu)數(shù)組HuffNode保存哈夫曼樹中各結(jié)點(diǎn)的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)，所以數(shù)組HuffNode的大小設(shè)置為2n-1，數(shù)組元素的結(jié)構(gòu)形式如下:

其中，weight域保存結(jié)點(diǎn)的權(quán)值，lchild和rchild域分別保存該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)在數(shù)組HuffNode中的序號(hào)，從而建立起結(jié)點(diǎn)之間的關(guān)系。為了判定一個(gè)結(jié)點(diǎn)是否已加入到要建立的哈夫曼樹中，可通過(guò)parent域的值來(lái)確定。初始時(shí)parent的值為-1，當(dāng)結(jié)點(diǎn)加入到樹中時(shí)，該結(jié)點(diǎn)parent的值為其雙親結(jié)點(diǎn)在數(shù)組HuffNode中的序號(hào)，就不會(huì)是-1了。

構(gòu)造哈夫曼樹時(shí)，首先將由n個(gè)字符形成的n個(gè)葉結(jié)點(diǎn)存放到數(shù)組HuffNode的前n個(gè)分量中，然后根據(jù)前面介紹的哈夫曼方法的基本思想，不斷將兩個(gè)小子樹合并為一個(gè)較大的子樹，每次構(gòu)成的新子樹的根結(jié)點(diǎn)順序放到HuffNode數(shù)組中的前n個(gè)分量的后面。

下面給出哈夫曼樹的構(gòu)造算法。

const maxvalue= 10000; {定義最大權(quán)值}

maxleat=30; {定義哈夫曼樹中葉子結(jié)點(diǎn)個(gè)數(shù)}

maxnode=maxleaf*2-1;

type HnodeType=record

weight: integer;

parent: integer;

lchild: integer;

rchild: integer;

end;

HuffArr:array[0..maxnode] of HnodeType;

var ……

procedure CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼樹的構(gòu)造算法}

var i,j,m1,m2,x1,x2,n: integer;

begin

readln(n); {輸入葉子結(jié)點(diǎn)個(gè)數(shù)}

for i:=0 to 2*n-1 do {數(shù)組HuffNode[ ]初始化}

begin

HuffNode.weight=0;

HuffNode.parent=-1;

HuffNode.lchild=-1;

HuffNode.rchild=-1;

end;

for i:=0 to n-1 do read(HuffNode.weight); {輸入n個(gè)葉子結(jié)點(diǎn)的權(quán)值}

for i:=0 to n-1 do {構(gòu)造哈夫曼樹}

begin

m1:=MAXVALUE; m2:=MAXVALUE;

x1:=0; x2:=0;

for j:=0 to n i-1 do

if (HuffNode[j].weight

begin m2:=m1; x2:=x1;

m1:=HuffNode[j].weight; x1:=j;

end

else if (HuffNode[j].weight

begin m2:=HuffNode[j].weight; x2:=j; end;

{將找出的兩棵子樹合并為一棵子樹}

HuffNode[x1].parent:=n i; HuffNode[x2].parent:=n i;

HuffNode[n i].weight:= HuffNode[x1].weight HuffNode[x2].weight;

HuffNode[n i].lchild:=x1; HuffNode[n i].rchild:=x2;

end;

end;