樹結構

樹結構

樹是一種重要的非線性數據結構,直觀地看,它是數據元素(在樹中稱為結點)按分支關係組織起來的結構,很象自然界中的樹那樣。

內容簡介

樹結構在客觀世界中廣泛存在,如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛套用,如在編譯源程式如下時,可用樹表示源源程式如下的語法結構。又如在資料庫系統中,樹型結構也是信息的重要組織形式之一。一切具有層次關係的問題都可用樹來描述。

定義

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

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

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

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

概念介紹

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

深度

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

層次

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

路徑

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

森林

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

樹的表示

父親數組

設T是一棵樹,表示T的一種最簡單的方法是用一個一維數組存儲每個結點,數組的下標就是結點的位置指針,每個結點中有一個指向各自的父親結點的數組下標的域,這樣可使Parent操作非常方便。類型定義如下:

Type TPosition=integer; {結點的位置類型為整型} NodeType=Record Label:LabelType; {該結點的標號} Parent:TPosition; {該結點的父親的數組下標,對於根結點該域為0} End; TreeType=Record NodeCount:integer; {樹的結點的總數目} Node:Array [1..MaxNodeCount] of NodeType;{存儲樹的結點} End;

由於樹中每個結點的父親是唯一的,所以上述的父親數組表示法可以唯一地表示任何一棵樹。在這種表示法下,尋找一個結點的父結點只需要 O(1)時間。在樹中可以從一個結點出發找出一條向上延伸到達其祖先的道路,即從一個結點到其父親,再到其祖父等等。求這樣的道路所需的時間正比於道路上結點的個數。在樹的父親數組表示法中,對於涉及查詢兒子和兄弟信息的樹操作,可能要遍歷整個數組。為了節省查詢時間,可以規定指示兒子的數組下標值大於父親的數組下標值,而指示兄弟結點的數組下標值隨著兄弟的從左到右是遞增的。

兒子鍊表

樹的另一種常用的表示方法就是兒子鍊表表示法。這種表示法用一個線性表來存儲樹的所有結點信息,稱為結點表。對每個結點建立一個兒子表。兒子表中只存儲兒子結點的地址信息,可以是指針,數組下標甚至記憶體地址。由於每個結點的兒子數目不定,因此兒子表常用單鍊表來實現,因此這種表示法稱為兒子鍊表表示法。這種實現法與圖的鄰接表表示法類似。下圖是一個兒子鍊表表示法的示意圖。

圖3 樹的兒子鍊表實現

圖3中兒子鍊表結構表示的樹如圖4所示,樹中各結點存放於一個數組實現的表中,數組下標作為各結點的指針。每一個數組元素(即每一個結點)含有一個兒子表,在圖3中兒子表是用單鍊表來實現的,當然也可以用其他表的實現方式來實現兒子表,比如說游標方式(靜態鍊表)。但由於每個結點的兒子數目不確定,所以一般不用數組來實現兒子表,但可以用數組來實現結點表,就如圖3所示。在圖3中可以看到,位於結點表第一個位置的結點(未必是根結點)有兩個兒子結點,從左到右的兩個兒子結點分別位於結點表的第2和第3個位置。因為圖3中的結點表用數組實現,所以結點的標號就是結點在結點表中的數組下標。如圖4所示。

圖4 圖3中兒子鍊表所表示的樹

為了指明樹的根結點的位置,我們可以用一個變數Root記錄根結點在結點表中的位置。有了根結點的位置,就可以利用兒子表依次找到樹中所有的結點。

兒子鍊表表示的樹的類型定義如下:

Type {====================== NodeListType是一個元素為NodeType類型的線性表,其位置類型為TPosition, NodeListType定義了結點表的類型; ChildrenListType是一個元素為TPosition類型的線性表, ChildrenListType定義了兒子表的類型 =======================} TPosition=.... ChildrenListType=... NodeType=Record {結點的類型} Label:LabelType; {結點的標號} Children:ChildrenListType;{結點的兒子表} End; NodeListType=... TreeType=record root:TPosition; {記錄樹根在結點表中的位置} Node:NodeListType; {結點表} end;

其中NodeListType是一個元素為NodeType類型的線性表,其位置類型為TPosition,NodeListType定義了結點表的類型;ChildrenListType是一個元素為TPosition類型的線性表, ChildrenListType定義了兒子表的類型。以上類型定義並不考慮表的具體實現方式,如果假設結點表和兒子表都用單鍊表實現,則類型定義可以具體實現如下:

{兒子鍊表實現樹的類型定義的一個具體實例,結點表和兒子表都用單鍊表實現} Type TPosition=^NodeType; {結點表的位置類型} ChildrenNodeType=record {兒子表的結點項的類型} child:TPosition; {指向兒子結點的位置指針} next:^ChildrenNodeType; {指向下一個兒子表項的指針} end; NodeType=Record {結點的類型定義為單鍊表} Label:LabelType; {結點的標號} Children:^ChildrenNodeType;{指向兒子表的指針} Next:TPosition; End; TreeType=^NodeType; {樹的類型定義為結點指針類型}

注意以上的定義只是一種具體情況,實際套用中結點表和兒子表可能用數組、鍊表等任何一種表的實現方式實現。

左兒子右兄弟

樹的左兒子右兄弟表示法又稱為 二叉樹表示法二叉鍊表表示法。每個結點除了data域外,還含有兩個域,分別指向該結點的最左兒子和右鄰兄弟。這種表示法常用二叉鍊表實現,因此又稱為 二叉鍊表表示法。但是實際套用中常用游標(靜態鍊表)來代替鍊表,請參見表的游標實現。

若用指針實現,其類型定義為:

Type TPosition=^NodeType; NodeType=record Label:LabelType; Leftmost_Child,Right_Sibling:TPosition; end; TreeType=TPosition;

若用游標實現,其類型定義為:

Type TPosition=integer; NodeType=record Label:LabelType; Leftmost_Child,Right_Sibling:TPosition; end; CellspaceType=array [1..MaxNodeCount] of NodeType; TreeType=TPosition; var Cellspace:CellspaceType; Tree:TreeType;

此時樹類型TreeType是整數類型,它指示樹根在cellspace中的游標。例如圖5(a)中樹的左兒子右兄弟表示法的指針和游標實現分別如圖5(b)和(c)所示。

(a)

(b)

(c)

圖5 樹的左兒子右兄弟表示法

用樹的左兒子右兄弟表示法可以直接實現樹的大部分操作,只有在對樹結點作Parent操作時需遍歷樹。如果要反覆執行Parent操作,可在結點記錄中再開闢一個指向父結點的指針域,也可以利用最右兒子單元中的Right_Sibling作為指向父結點的指針(否則這裡總是空指針)。當執行Parent(v)時,可以先通過Right_Sibling逐步找出結點v的最右兄弟,再通過最右兄弟的Right_Sibling(父親指針)找到父結點。這個結點就是結點v的父親。在這樣的表示法下,求一個結點的父親所需要的時間正比於該結點右邊的兄弟個數。不過,這時每個記錄中需要多用一位(bit)空間,用以標明該記錄中的right_sibling是指向右鄰兄弟還是指向父親。

考慮到對於現在的計算機,記憶體已經不是很重要的限制因素了。我們下面就採取增加一個parent域的方案,以改進左兒子右兄弟表示法中Parent操作的效率。因此重新定義樹的類型如下:

若用指針實現,其類型定義為:

Type TPosition=^NodeType; NodeType=record Label:LabelType; Parent,Leftmost_Child,Right_Sibling:TPosition; {增加一個Parent域} end; TreeType=TPosition; var Tree:TreeType;

若用游標實現,其類型定義為:

Type TPosition=integer; NodeType=record Label:LabelType; Parent,Leftmost_Child,Right_Sibling:TPosition; {增加一個Parent域} end; CellspaceType=array [1..MaxNodeCount] of NodeType; TreeType=TPosition; var Cellspace:CellspaceType; Tree:TreeType;

樹的遍歷

樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的系統的訪問,即依次對樹中每個結點訪問一次且僅訪問一次。樹的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))))就是一棵二叉排序樹。

二、二叉排序樹的構造

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

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

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

Huffman樹

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

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

可以證明,哈夫曼樹是最優二叉樹。如給定權值{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[i].weight:=W[i];{將權值放在樹葉中}

TR[i].Lc:=0;

TR[i].Rc:=0;

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

AT[i].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’,統計電文中字母的頻度,f('C')=1,f('S')=2,f('T')=3,f(' ')=3,f('A')=4,可用其頻度{1,2,3,3,4}為權值生成Huffman樹,並在每個葉子上註明對應的字元。樹中從根到每個葉子都有一條路徑,若對路徑上的各分支進行約定,指向左子樹根的分支用“0”碼錶示,指向右子樹根的分支用“1”碼錶示,再取每條路徑上的“0”或“1”的序列作為與各個葉子對應的字元的編碼,這就是哈夫曼編碼。

二叉樹

二叉樹是一類非常重要的樹形結構,它可以遞歸地定義如下:

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

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

二叉樹具有以下的重要性質:

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

相關詞條

相關搜尋

熱門詞條

聯絡我們