樹結構基本概念

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

樹的深度--組成該樹各結點的最大層次，如上圖，其深度為4;

根結點的層次為1，其他結點的層次等于它的父結點的層次數加1.

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

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

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

(1)每個元素稱為結點(node);

(2)有一個特定的結點，稱為根結點或根(root);

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

樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的系統(tǒng)的訪問，即依次對樹中每個結點訪問一次且僅訪問一次。樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和后序遍歷。以這3種方式遍歷一棵樹時，若按訪問結點的先后次序將結點排列起來，就可分別得到樹中所有結點的前序列表，中序列表和后序列表。相應的結點次序分別稱為結點的前序、中序和后序。

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

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

§ 如果T是一棵單結點樹，那么對T進行前序遍歷、中序遍歷和后序遍歷都只訪問這個結點。這個結點本身就是要得到的相應列表。

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

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

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

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

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

一、二叉排序樹的定義

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

1、左子樹上所有結點的數據值均小于根結點的數據值;

2、右子樹上所有結點的數據值均大于或等于根結點的數據值;

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

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

二、二叉排序樹的構造

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

1、以待排序的數據的第一個數據構成根結點;

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

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

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

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

二、哈夫曼樹的構造

1、哈夫曼算法:

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

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

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

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

2、算法描述

為了上述算法，選用數組型的鏈表作為存儲結構，其類型設計如下:

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;

下面是在這個存儲結構上實現的構造哈夫曼樹的算法:

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

VAR AT:A;

BENGIN

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

BEGIN

TR.weight:=W;{將權值放在樹葉中}

TR.Lc:=0;

TR.Rc:=0;

AT.weight:=TR.weight;{用AT存放當前森林的根}

AT.adr:=i;

END;

num:=n;{森林中結點個數}

K:=num+1;{形成的新結點在TR數組中的位置}

WHILE (num>=2) DO {重復實現第(2)、(3)步}

BEGIN

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

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

{選擇兩棵結點權值最小的樹構造新二叉樹}

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

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

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

AT[1].adr:=k; {新樹結點標號}

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

AT[2].adr:=AT[num].adr; {跟進結點標號}

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

k:=k+1; {增加結點標號}

END;

END;

三、應用:哈夫曼編碼

利用哈夫曼樹構造的用于通信的二進制編碼，稱為哈夫曼編碼。

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