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

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

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

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

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

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

RF={<root,ri>|i=1,2,…,m;m>0}第4頁，課件共21頁，創(chuàng)作于2023年2月（2）表示形式該樹有13個結(jié)點。其中，A是樹根，其余結(jié)點分成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第5頁，課件共21頁，創(chuàng)作于2023年2月該樹又可表示為如下三種形式：(a)嵌套集合表示(c)凹入表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))(b)廣義表表示ABCDEFGHIJKLMABCDEFGHIJKLM圖6.2 樹的其他3種表示法第6頁，課件共21頁，創(chuàng)作于2023年2月（3）樹的抽象數(shù)據(jù)類型定義ADTTree{

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

對任意j≠k(1≤j,k≤m)有Dj∩Dk＝Ф，且對任意的i(1≤i≤m)，唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H； （3）對應(yīng)于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上的二元關(guān)系，

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

InitTree(&T);

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

DestroyTree(&T);

初始條件：樹T存在。 操作結(jié)果：銷毀樹T。第7頁，課件共21頁，創(chuàng)作于2023年2月

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中某個結(jié)點。 操作結(jié)果：返回cur_e的值。

Assign(T,cur_e,value);

初始條件：樹T存在，cur_e是T中某個結(jié)點。 操作結(jié)果：結(jié)點cur_e賦值為value。第8頁，課件共21頁，創(chuàng)作于2023年2月

Parent(T,cur_e);

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

LeftChild(T,cur_e);

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

RightSibling(T,cur_e);

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

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

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

DeleteChild(&T,&P,i);

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

TraverseTree(T,visit());

初始條件：樹T存在，visit是對結(jié)點操作的應(yīng)用函數(shù)。 操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。}ADTTree第9頁，課件共21頁，創(chuàng)作于2023年2月￡6.1.2基本術(shù)語

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

雙親（Parent）：結(jié)點的子樹的根，稱為該結(jié)點的孩子，該結(jié)點稱為孩子的雙親。兄弟（Sibling）：同一個雙親的孩子之間互稱為兄弟。第10頁，課件共21頁，創(chuàng)作于2023年2月子孫：以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。祖先：從根到某結(jié)點所經(jīng)分支上的所有結(jié)點，稱為該結(jié)點的祖先。

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

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

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