樹的定義和基本術(shù)語

樹的定義和基本術(shù)語第一頁，共二十一頁，2022年，8月28日樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹來形象表示。樹在計(jì)算機(jī)領(lǐng)域中也得到廣泛應(yīng)用，如在編譯程序中，可用樹來表示源程序的語法結(jié)構(gòu)。又如在數(shù)據(jù)庫系統(tǒng)中，樹形結(jié)構(gòu)也是信息的重要組織形式之一。第二頁，共二十一頁，2022年，8月28日6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.6哈夫曼樹及其應(yīng)用第三頁，共二十一頁，2022年，8月28日6.1樹的定義和基本術(shù)語（1）定義樹（Tree）：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集。定義一：（遞歸定義）：①在任意一棵非空樹中，有且僅有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)；②當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集

T1,T2,…,Tm，其中每一個(gè)集合本身又是一棵樹。并且

T1,T2,…,Tm，稱為根的子樹（SubTree）。定義二：（形式定義） 任何一棵樹是一個(gè)二元組Tree=(root,F)。其中：root是數(shù)據(jù)元素，稱做樹的根結(jié)點(diǎn)；F是m（m≥0）棵樹的森林，

F＝（T1,T2,…,Tm），其中Ti=(ri,Fi)稱做根root的第i棵子樹；當(dāng)m≠0

時(shí)，在樹根和其子樹森林之間存在下列關(guān)系：

RF={<root,ri>|i=1,2,…,m;m>0}第四頁，共二十一頁，2022年，8月28日（2）表示形式該樹有13個(gè)結(jié)點(diǎn)。其中，A是樹根，其余結(jié)點(diǎn)分成3個(gè)互不相交的子集：T1={B,E,F,K,L}，T2={C,G}，T3={D,H,I,J,M};T1、T2和T3都是A的子樹，其本身也是一棵樹。層次A1BCD 2EFGHIJ3KLM4圖6.1 一般的樹A第五頁，共二十一頁，2022年，8月28日該樹又可表示為如下三種形式：(a)嵌套集合表示(c)凹入表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))(b)廣義表表示ABCDEFGHIJKLMABCDEFGHIJKLM圖6.2 樹的其他3種表示法第六頁，共二十一頁，2022年，8月28日（3）樹的抽象數(shù)據(jù)類型定義ADTTree{

數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹； 若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H},H是如下二元關(guān)系： （1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)； （2）若D－{root}≠Ф，則存在D－{root}的一個(gè)劃分D1,D2,…,Dm(m>0),

對(duì)任意j≠k(1≤j,k≤m)有Dj∩Dk＝Ф，且對(duì)任意的i(1≤i≤m)，唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H； （3）對(duì)應(yīng)于D－{root}的劃分，H－{<root,xi>,…,<root,xm>}有唯一的一個(gè)劃分H1,H2,…,Hm(m>0)，對(duì)任意j≠k(1≤j,k≤m)有

Hj∩Hk＝Ф，且對(duì)任意i(1≤i≤m)，Hi是Di上的二元關(guān)系，

(Di,{Hi})是一棵符合本定義的樹，稱為根root的子樹。 基本操作：

InitTree(&T);

操作結(jié)果：構(gòu)造空樹T。

DestroyTree(&T);

初始條件：樹T存在。 操作結(jié)果：銷毀樹T。第七頁，共二十一頁，2022年，8月28日

CreateTree(&T,definition);

初始條件：definition給出樹T的定義。 操作結(jié)果：按definition構(gòu)造樹T。

ClearTree(&T);

初始條件：樹T存在。 操作結(jié)果：將樹T清為空樹。

TreeEmpty(T);

初始條件：樹T存在。 操作結(jié)果：若T為空樹，則返回TRUE，否則返回FALSE。

TreeDepth(T);

初始條件：樹T存在。 操作結(jié)果：返回T的深度。

Root(T);

初始條件：樹T存在。 操作結(jié)果：返回T的根。

Value(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：返回cur_e的值。

Assign(T,cur_e,value);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：結(jié)點(diǎn)cur_e賦值為value。第八頁，共二十一頁，2022年，8月28日

Parent(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為“空”。

LeftChild(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回“空”。

RightSibling(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。 操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。

InsertChild(&T,&P,i,c);

初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p所指結(jié)點(diǎn)的度＋1，非空樹c與T不相交。 操作結(jié)果：插入c為T中p指結(jié)點(diǎn)的第i棵子樹。

DeleteChild(&T,&P,i);

初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p指結(jié)點(diǎn)的度。 操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵子樹。

TraverseTree(T,visit());

初始條件：樹T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。}ADTTree第九頁，共二十一頁，2022年，8月28日￡6.1.2基本術(shù)語

結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。在樹的圖形表示中為一個(gè)圓圈。結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)擁有的子樹數(shù)。葉子（或終端結(jié)點(diǎn)）（Leaf）：度為0的結(jié)點(diǎn)。即沒有子樹的結(jié)點(diǎn)。分支結(jié)點(diǎn)（或非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)。內(nèi)部結(jié)點(diǎn)：除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)。樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。孩子（Child）：結(jié)點(diǎn)的子樹的根，稱為該結(jié)點(diǎn)的孩子。

雙親（Parent）：結(jié)點(diǎn)的子樹的根，稱為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱為孩子的雙親。兄弟（Sibling）：同一個(gè)雙親的孩子之間互稱為兄弟。第十頁，共二十一頁，2022年，8月28日子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。祖先：從根到某結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的祖先。

森林（Forest）：是m（m≥0）棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。層次（Level）：從根開始定義起，根為第一層，根的孩子為第二層。若某結(jié)點(diǎn)在第k層，則其子樹的根就在第k＋1層。堂兄弟：其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。深度（高度）（Depth）：樹中結(jié)點(diǎn)的最大層次。

有序樹：若將樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。在有序樹中最左邊的子樹的根稱為第一個(gè)孩子，最右邊的稱為最后一個(gè)孩子。第十一頁，共二十一頁，2022年，8月28日結(jié)點(diǎn):包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支結(jié)點(diǎn)的度:結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度ABCDEFGHIJMKL如圖：A的度為3，C的度為1，E的度為0。第十二頁，共二十一頁，2022年，8月28日樹的度:葉子（或終端）結(jié)點(diǎn):分支（或非終端）結(jié)點(diǎn):樹中所有結(jié)點(diǎn)的度的最大值。度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。ABCDEFGHIJMKL如圖所示的樹的度為3。第十三頁，共二十一頁，2022年，8月28日結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子（child)，相應(yīng)的，該結(jié)點(diǎn)的稱為孩子的雙親（parent）。ABCDEFGHIJMKL如圖所示中，D為A的子樹T3的根，則D是A的孩子，而A則是D的雙親。第十四頁，共二十一頁，2022年，8月28日同一個(gè)雙親的孩子之間互稱兄弟（sibling）。ABCDEFGHIJMKL如圖所示中，H、I、J互稱為兄弟。將這些關(guān)系進(jìn)一步推廣，可認(rèn)為D是M的祖父。結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)。如圖所示中，M的祖先為A、D和J。反之，以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。如B的子孫為E、F、K、L。第十五頁，共二十一頁，2022年，8月28日結(jié)點(diǎn)的層次:樹的深度：ABCDEFGHIJMKL結(jié)點(diǎn)的層次從根開始定義起，根為第一層，根的孩子為第二層。假設(shè)根結(jié)點(diǎn)的層次為1,第l層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1。樹中葉子結(jié)點(diǎn)所在的最大層次。圖示的樹的深度為4。結(jié)點(diǎn)雙親在同一層的結(jié)點(diǎn)互為堂兄弟。例如，結(jié)點(diǎn)G與E、F、H、I、J互為堂兄弟。第十六頁，共二十一頁，2022年，8月28日有序樹：子樹之間存在確定的次序關(guān)系。樹中結(jié)點(diǎn)的各子樹從左到右是有次序的（即不能互換）。

在有序樹中最左邊的子樹的根稱為第一個(gè)孩子，最右邊的稱為最后一個(gè)孩子。無序樹：子樹之間不存在確定的次序關(guān)系。第十七頁，共二十一頁，2022年，8月28日森林：是m（m≥0）棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。由此，也可以森林和樹相互遞歸的定義來描述樹。ArootBEFKLCGDHIJMF第十八頁，共二十一頁，2022年，8月28日就邏輯結(jié)構(gòu)而言，任何一棵非空樹是一個(gè)二元組Tree=（root，F(xiàn)）其中：root是數(shù)據(jù)元素，被稱為根結(jié)點(diǎn)，F(xiàn)是m(m>=0)棵樹的森林，被稱為子樹森林，F(xiàn)=（T1，T2,…,Tm),其中Ti=(ri,Fi)稱做根為root的第i棵子樹；當(dāng)m<>0時(shí)，在樹根和其子樹森林之間存在下列關(guān)系：RF={<root,ri>|i=1,2,…,m,m>0}這個(gè)定義將有助于得到