樹結(jié)構(gòu)樹的遍歷

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

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

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

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

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

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

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

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

樹的度--也即是寬度，簡單地說，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹各結(jié)點(diǎn)中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。樹中度不為零的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。

樹的深度--組成該樹各結(jié)點(diǎn)的最大層次，如上圖，其深度為4;

根結(jié)點(diǎn)的層次為1，其他結(jié)點(diǎn)的層次等于它的父結(jié)點(diǎn)的層次數(shù)加1.

對于一棵子樹中的任意兩個(gè)不同的結(jié)點(diǎn)，如果從一個(gè)結(jié)點(diǎn)出發(fā)，按層次自上而下沿著一個(gè)個(gè)樹枝能到達(dá)另一結(jié)點(diǎn)，稱它們之間存在著一條路徑。可用路徑所經(jīng)過的結(jié)點(diǎn)序列表示路徑，路徑的長度等于路徑上的結(jié)點(diǎn)個(gè)數(shù)減1.

指若干棵互不相交的樹的集合

一棵樹(tree)是由n(n>0)個(gè)元素組成的有限集合，其中:

(1)每個(gè)元素稱為結(jié)點(diǎn)(node);

(2)有一個(gè)特定的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)或根(root);

(3)除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成m(m>=0)個(gè)互不相交的有限集合，而每個(gè)子集又都是一棵樹(稱為原樹的子樹)

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

一、二叉排序樹的定義

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

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

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

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

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

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

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

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

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

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

所謂路徑長度就是某個(gè)端結(jié)點(diǎn)到樹的根結(jié)點(diǎn)的距離，等于該端結(jié)點(diǎn)的祖先數(shù)，或該結(jié)點(diǎn)所在層數(shù)減1，用lk表示。二叉樹中每個(gè)端結(jié)點(diǎn)對應(yīng)的一個(gè)實(shí)數(shù)稱為該結(jié)點(diǎn)的權(quán)，用Wk表示。我們定義各端結(jié)點(diǎn)的權(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個(gè)權(quán)值{W1，W2，…，Wn}構(gòu)成n棵二叉樹的森林:F{T1，T2，…，Tn}。其中每棵二叉樹Ti只有一個(gè)帶權(quán)為Wi的根結(jié)點(diǎn)，其左右子樹為空。

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

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

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

2、算法描述

為了上述算法，選用數(shù)組型的鏈表作為存儲(chǔ)結(jié)構(gòu)，其類型設(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)造哈夫曼樹的算法:

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)值放在樹葉中}

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);{按根值大小對森林中的樹進(jìn)行升序排列}

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

{選擇兩棵結(jié)點(diǎn)權(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é)點(diǎn)標(biāo)號(hào)}

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

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

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

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

END;

END;

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

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

例如，有一段電文'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樹，并在每個(gè)葉子上注明對應(yīng)的字符。樹中從根到每個(gè)葉子都有一條路徑，若對路徑上的各分支進(jìn)行約定，指向左子樹根的分支用"0"碼表示，指向右子樹根的分支用"1"碼表示，再取每條路徑上的"0"或"1"的序列作為與各個(gè)葉子對應(yīng)的字符的編碼，這就是哈夫曼編碼。