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

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

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

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

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

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

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

數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹(shù)； 若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H},H是如下二元關(guān)系： （1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(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})是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)。 基本操作：

InitTree(&T);

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

DestroyTree(&T);

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

CreateTree(&T,definition);

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

ClearTree(&T);

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

TreeEmpty(T);

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

TreeDepth(T);

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

Root(T);

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

Value(T,cur_e);

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

Assign(T,cur_e,value);

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

Parent(T,cur_e);

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

LeftChild(T,cur_e);

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

RightSibling(T,cur_e);

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

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

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

DeleteChild(&T,&P,i);

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

TraverseTree(T,visit());

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

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

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

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

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

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