最優(yōu)二叉樹(shù)算法構(gòu)造算法

最優(yōu)二叉樹(shù)，也稱(chēng)哈夫曼(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ù)。

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

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

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

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

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

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

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

鐵球分類(lèi)

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

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

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

兩種判斷二叉樹(shù)示意圖

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

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

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

左圖 和下圖

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

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

在數(shù)據(jù)通訊中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0，1組成的二進(jìn)制串，我們稱(chēng)之為編碼。例如，假設(shè)要傳送的電文為ABACCDA，電文中只含有A，B，C，D四種字符，若這四種字符采用表7.3 (a)所示的編碼，則電文的代碼為000010000100100111 000，長(zhǎng)度為21。在傳送電文時(shí)，我們總是希望傳送時(shí)間盡可能短，這就要求電文代碼盡可能短，顯然，這種編碼方案產(chǎn)生的電文代碼不夠短。表7.3 (b)所示為另一種編碼方案，用此編碼對(duì)上述電文進(jìn)行編碼所建立的代碼為00010010101100，長(zhǎng)度為14。在這種編碼方案中，四種字符的編碼均為兩位，是一種等長(zhǎng)編碼。如果在編碼時(shí)考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長(zhǎng)的編碼，構(gòu)造一種不等長(zhǎng)編碼，則電文的代碼就可能更短。如當(dāng)字符A，B，C，D采用表7.3 (c)所示的編碼時(shí)，上述電文的代碼為0110010101110，長(zhǎng)度僅為13。

表a、表b、表c、表d(從下圖的上下順序依次列出)

表3 字符的四種不同的編碼方案

哈夫曼樹(shù)可用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。具體做法如下:設(shè)需要編碼的字符集合為{d1，d2，…，dn}，它們?cè)陔娢闹谐霈F(xiàn)的次數(shù)或頻率集合為{w1，w2，…，wn}，以d1，d2，…，dn作為葉結(jié)點(diǎn)，w1，w2，…，wn作為它們的權(quán)值，構(gòu)造一棵哈夫曼樹(shù)，規(guī)定哈夫曼樹(shù)中的左分支代表0，右分支代表1，則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過(guò)的路徑分支組成的0和1的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼，我們稱(chēng)之為哈夫曼編碼。

在哈夫曼編碼樹(shù)中，樹(shù)的帶權(quán)路徑長(zhǎng)度的含義是各個(gè)字符的碼長(zhǎng)與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長(zhǎng)，所以采用哈夫曼樹(shù)構(gòu)造的編碼是一種能使電文代碼總長(zhǎng)最短的不等長(zhǎng)編碼。

在建立不等長(zhǎng)編碼時(shí)，必須使任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴，這樣才能保證譯碼的唯一性。例如表7.3 (d)的編碼方案，字符A的編碼01是字符B的編碼010的前綴部分，這樣對(duì)于代碼串0101001，既是AAC的代碼，也是ABD和BDA的代碼，因此，這樣的編碼不能保證譯碼的唯一性，我們稱(chēng)之為具有二義性的譯碼。

然而，采用哈夫曼樹(shù)進(jìn)行編碼，則不會(huì)產(chǎn)生上述二義性問(wèn)題。因?yàn)?，在哈夫曼?shù)中，每個(gè)字符結(jié)點(diǎn)都是葉結(jié)點(diǎn)，它們不可能在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符的哈夫曼編碼不可能是另一個(gè)字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。

下面討論實(shí)現(xiàn)哈夫曼編碼的算法。實(shí)現(xiàn)哈夫曼編碼的算法可分為兩大部分:

(1)構(gòu)造哈夫曼樹(shù);

(2)在哈夫曼樹(shù)上求葉結(jié)點(diǎn)的編碼。

求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹(shù)中，從葉結(jié)點(diǎn)開(kāi)始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，每回退一步，就走過(guò)了哈夫曼樹(shù)的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉結(jié)點(diǎn)所經(jīng)過(guò)的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。我們可以設(shè)置一結(jié)構(gòu)數(shù)組HuffCode用來(lái)存放各字符的哈夫曼編碼信息，數(shù)組元素的結(jié)構(gòu)如下:

其中，分量bit為一維數(shù)組，用來(lái)保存字符的哈夫曼編碼，start表示該編碼在數(shù)組bit中的開(kāi)始位置。所以，對(duì)于第i個(gè)字符，它的哈夫曼編碼存放在HuffCode.bit中的從HuffCode.start到n的分量上。

求哈夫曼編碼程序段

const Maxleaf=128; {定義最多葉結(jié)點(diǎn)數(shù)}

MaxNode=255; {定義最大結(jié)點(diǎn)數(shù)}

MaxBit=10; {定義哈夫曼編碼的最大長(zhǎng)度}

type HCodeType =record

bit: array[0..MaxBit] of integer;

start: integer;

end;

……

procedure HaffmanCode ; {生成哈夫曼編碼}

var HuffNode: array[0..MaxNode] of HCodeType;

HuffCode: array[0..MaxLeaf] of HcodeType;

cd : HcodeType ;

i,j, c,p: integer ;

begin

HuffmanTree (HuffNode ); {建立哈夫曼樹(shù)}

for i:=0 to n-1 do {求每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼}

begin

cd.start:=n-1; c:=i;

p:=HuffNode[c].parent;

while p<>0 do {由葉結(jié)點(diǎn)向上直到樹(shù)根}

if HuffNode

.lchild=c then cd.bit[cd.start]:=0

else cd.bit[cd.start]:=1;

dec (cd.start); c:=p;

p:=HuffNode[c].parent;

end;

for j:=cd.start 1 to n-1 do {保存求出的每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位}

begin

HuffCode.bit[j]:=cd.bit[j];

HuffCode.start=cd.start;

end;

for i:=0 to n-1 do {輸出每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼}

begin

for j:=HuffCode.start 1 to n-1 do write(HuffCode.bit[j]:10);

writeln;

end;

end;