樹結(jié)構(gòu)二叉樹

二叉樹是一類非常重要的樹形結(jié)構(gòu)，它可以遞歸地定義如下:

二叉樹T是有限個結(jié)點的集合，它或者是空集，或者由一個根結(jié)點u以及分別稱為左子樹和右子樹的兩棵互不相交的二叉樹u(1)和u(2)組成。若用n,n1和n2分別表示T，u(1)和u(2)的結(jié)點數(shù)，則有n=1+n1+n2 。u(1)和u(2)有時分別稱為T的第一和第二子樹。

因此，二叉樹的根可以有空的左子樹或空的右子樹，或者左、右子樹均為空。

二叉樹具有以下的重要性質(zhì):

高度為h≥0的二叉樹至少有h+1個結(jié)點; 高度不超過h(≥0)的二叉樹至多有2h+1-1個結(jié)點; 含有n≥1個結(jié)點的二叉樹的高度至多為n-1; 含有n≥1個結(jié)點的二叉樹的高度至少為 logn ，因此其高度為Ω(logn)。 詳見二叉樹詞條。

排序是一種十分重要的運算。所謂排序就是把一堆雜亂無章的元素按照某種次序排列起來，形成一個線性有序的序列。二叉排序樹是利用二叉樹的結(jié)構(gòu)特點來實現(xiàn)對元素排序的。

一、二叉排序樹的定義

二叉排序樹或者是空樹，或者是具有如下性質(zhì)的二叉樹:

1、左子樹上所有結(jié)點的數(shù)據(jù)值均小于根結(jié)點的數(shù)據(jù)值;

2、右子樹上所有結(jié)點的數(shù)據(jù)值均大于或等于根結(jié)點的數(shù)據(jù)值;

3、左子樹、右子樹本身又各是一棵二叉排序樹。

由此可見，二叉排序樹是一種特殊結(jié)構(gòu)的二叉樹。(18(10(3，15(12，15))，21(20，21(，37))))就是一棵二叉排序樹。

二、二叉排序樹的構(gòu)造

二叉排序樹的構(gòu)造過程實質(zhì)上就是排序的過程，它是二叉排序樹作媒介，將一個任意的數(shù)據(jù)序列變成一個有序序列。二叉排序樹的構(gòu)造一般是采用陸續(xù)插入結(jié)點的辦法逐步構(gòu)成的。具體構(gòu)造的思路是:

1、以待排序的數(shù)據(jù)的第一個數(shù)據(jù)構(gòu)成根結(jié)點;

2、對以后的各個數(shù)據(jù)，逐個插入結(jié)點，而且規(guī)定:在插入過程的每一步，原有樹結(jié)點位置不再變動，只是將新數(shù)據(jù)的結(jié)點作為一個葉子結(jié)點插入到合適的位置，使樹中任何結(jié)點的數(shù)據(jù)與其左、右子樹結(jié)點數(shù)據(jù)之間的關(guān)系仍然符合對二叉排序樹的要求。

一、哈夫曼樹的含義:哈夫曼樹是一種帶權(quán)路徑長度最短的樹。

所謂路徑長度就是某個端結(jié)點到樹的根結(jié)點的距離，等于該端結(jié)點的祖先數(shù)，或該結(jié)點所在層數(shù)減1，用lk表示。二叉樹中每個端結(jié)點對應(yīng)的一個實數(shù)稱為該結(jié)點的權(quán)，用Wk表示。我們定義各端結(jié)點的權(quán)Wk與相應(yīng)的路徑程度lk乘積的代數(shù)和為該二叉樹的帶權(quán)路徑長度，用WPL表示，即:

可以證明，哈夫曼樹是最優(yōu)二叉樹。如給定權(quán)值{5，4，7，2，3}，可以生成很多棵二叉樹，其中的(A(B(7，5)，C(4，D(3，2))))是哈夫曼樹。

二、哈夫曼樹的構(gòu)造

1、哈夫曼算法:

(1)根據(jù)給定的n個權(quán)值{W1，W2，…，Wn}構(gòu)成n棵二叉樹的森林:F{T1，T2，…，Tn}。其中每棵二叉樹Ti只有一個帶權(quán)為Wi的根結(jié)點，其左右子樹為空。

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

(3)在F中刪除這兩棵樹，同時，將新得到的二叉樹加入F中。

(4)重復(fù)(2)、(3)，直到F只含一棵樹為止。最后的這棵樹便是哈夫曼樹。

2、算法描述

為了上述算法，選用數(shù)組型的鏈表作為存儲結(jié)構(gòu)，其類型設(shè)計如下:

Type tnode=RECORD

weight:real;

Lc，Rc:integer;

END;

tree=ARRAY[1..2*n-1] of tnode;

node=RECORD

weight:real;

adr:integer;

END;

A=ARRAY[1..n] of node;

下面是在這個存儲結(jié)構(gòu)上實現(xiàn)的構(gòu)造哈夫曼樹的算法:

Procedure Huffmantree(VAR W:ARRAY[1..n]OF real;VAR TR:tree);

VAR AT:A;

BENGIN

FOR i:=1 TO n DO{實現(xiàn)第(1)步}

BEGIN

TR.weight:=W;{將權(quán)值放在樹葉中}

TR.Lc:=0;

TR.Rc:=0;

AT.weight:=TR.weight;{用AT存放當(dāng)前森林的根}

AT.adr:=i;

END;

num:=n;{森林中結(jié)點個數(shù)}

K:=num+1;{形成的新結(jié)點在TR數(shù)組中的位置}

WHILE (num>=2) DO {重復(fù)實現(xiàn)第(2)、(3)步}

BEGIN

SORTING(AT,num);{按根值大小對森林中的樹進(jìn)行升序排列}

TR[k].weight:=AT[1].weight+AT[2].weight;

{選擇兩棵結(jié)點權(quán)值最小的樹構(gòu)造新二叉樹}

TR[k].Lc:=AT[1].adr; {左子樹:權(quán)值最小的樹}

TR[k].Rc:=AT[2].adr; {右子樹:權(quán)值次小的樹}

AT[1].weight:=TR[k].weight; {新樹賦予第一}

AT[1].adr:=k; {新樹結(jié)點標(biāo)號}

AT[2].weight:=AT[num].weight;{原最后樹賦予第二}

AT[2].adr:=AT[num].adr; {跟進(jìn)結(jié)點標(biāo)號}

num:=num-1; {刪除原最后樹}

k:=k+1; {增加結(jié)點標(biāo)號}

END;

END;

三、應(yīng)用:哈夫曼編碼

利用哈夫曼樹構(gòu)造的用于通信的二進(jìn)制編碼，稱為哈夫曼編碼。

例如，有一段電文'CAST TAT A SA'，統(tǒng)計電文中字母的頻度，f('C')=1,f('S')=2,f('T')=3,f(' ')=3,f('A')=4，可用其頻度{1，2，3，3，4}為權(quán)值生成Huffman樹，并在每個葉子上注明對應(yīng)的字符。樹中從根到每個葉子都有一條路徑，若對路徑上的各分支進(jìn)行約定，指向左子樹根的分支用"0"碼表示，指向右子樹根的分支用"1"碼表示，再取每條路徑上的"0"或"1"的序列作為與各個葉子對應(yīng)的字符的編碼，這就是哈夫曼編碼。