樹(shù)結(jié)構(gòu)

樹(shù)的遍歷是樹(shù)的一種重要的運(yùn)算。所謂遍歷是指對(duì)樹(shù)中所有結(jié)點(diǎn)的系統(tǒng)的訪問(wèn)，即依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。樹(shù)的3種最重要的遍歷方式分別稱(chēng)為前序遍歷、中序遍歷和后序遍歷。以這3種方式遍歷一棵樹(shù)時(shí)，若按訪問(wèn)結(jié)點(diǎn)的先后次序?qū)⒔Y(jié)點(diǎn)排列起來(lái)，就可分別得到樹(shù)中所有結(jié)點(diǎn)的前序列表，中序列表和后序列表。相應(yīng)的結(jié)點(diǎn)次序分別稱(chēng)為結(jié)點(diǎn)的前序、中序和后序。

樹(shù)的這3種遍歷方式可遞歸地定義如下:

§ 如果T是一棵空樹(shù)，那么對(duì)T進(jìn)行前序遍歷、中序遍歷和后序遍歷都是空操作，得到的列表為空表。

§ 如果T是一棵單結(jié)點(diǎn)樹(shù)，那么對(duì)T進(jìn)行前序遍歷、中序遍歷和后序遍歷都只訪問(wèn)這個(gè)結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)本身就是要得到的相應(yīng)列表。

§ 否則，設(shè)T如圖6所示，它以n為樹(shù)根，樹(shù)根的子樹(shù)從左到右依次為T(mén)1,T2,..,Tk，那么有:

§ 對(duì)T進(jìn)行前序遍歷是先訪問(wèn)樹(shù)根n,然后依次前序遍歷T1,T2,..,Tk。

§ 對(duì)T進(jìn)行中序遍歷是先中序遍歷T1，然后訪問(wèn)樹(shù)根n，接著依次對(duì)T2,T2,..,Tk進(jìn)行中序遍歷。

§ 對(duì)T進(jìn)行后序遍歷是先依次對(duì)T1,T2,..,Tk進(jìn)行后序遍歷，最后訪問(wèn)樹(shù)根n。

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

一、二叉排序樹(shù)的定義

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

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

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

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

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

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

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

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

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

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

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

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

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

1、哈夫曼算法:

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

(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)，直到F只含一棵樹(shù)為止。最后的這棵樹(shù)便是哈夫曼樹(shù)。

2、算法描述

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

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;

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

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

VAR AT:A;

BENGIN

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

BEGIN

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

TR.Lc:=0;

TR.Rc:=0;

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

AT.adr:=i;

END;

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

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

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

BEGIN

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

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

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

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

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

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

AT[1].adr:=k; {新樹(shù)結(jié)點(diǎn)標(biāo)號(hào)}

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

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

num:=num-1; {刪除原最后樹(shù)}

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

END;

END;

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

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

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