樹的定義和基本術語

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

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

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

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

時，在樹根和其子樹森林之間存在下列關系：

RF={<root,ri>|i=1,2,…,m;m>0}第四頁，共二十一頁，2022年，8月28日（2）表示形式該樹有13個結點。其中，A是樹根，其余結點分成3個互不相交的子集：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ù)據類型定義ADTTree{

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

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

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

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

InitTree(&T);

操作結果：構造空樹T。

DestroyTree(&T);

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

CreateTree(&T,definition);

初始條件：definition給出樹T的定義。 操作結果：按definition構造樹T。

ClearTree(&T);

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

TreeEmpty(T);

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

TreeDepth(T);

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

Root(T);

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

Value(T,cur_e);

初始條件：樹T存在，cur_e是T中某個結點。 操作結果：返回cur_e的值。

Assign(T,cur_e,value);

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

Parent(T,cur_e);

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

LeftChild(T,cur_e);

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

RightSibling(T,cur_e);

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

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

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

DeleteChild(&T,&P,i);

初始條件：樹T存在，p指向T中某個結點，1≤i≤p指結點的度。 操作結果：刪除T中p所指結點的第i棵子樹。

TraverseTree(T,visit());

初始條件：樹T存在，visit是對結點操作的應用函數(shù)。 操作結果：按某種次序對T的每個結點調用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。}ADTTree第九頁，共二十一頁，2022年，8月28日￡6.1.2基本術語

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

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

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

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

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