資源描述：
《樹(shù)的定義和基本術(shù)語(yǔ).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第六章樹(shù)和二叉樹(shù)樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。其中以樹(shù)和二叉樹(shù)最為常用。直觀來(lái)說(shuō)，樹(shù)是以分支關(guān)系定義的層次結(jié)構(gòu)。樹(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)也是信息的重要組織形式之一。6.1樹(shù)的定義和基本術(shù)語(yǔ)6.2二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.4樹(shù)和森林6.6哈夫曼樹(shù)及其應(yīng)用6.1樹(shù)的定義和基本術(shù)語(yǔ)（1）定義樹(shù)（Tree）：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集。定義一：（遞歸定義）：①在任意一棵非空
2、樹(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(xiàn)＝（T1,T2,…,Tm），其中Ti=(ri,Fi)稱做根root的第i棵子樹(shù)；當(dāng)m≠0時(shí)，在樹(shù)根和其子樹(shù)森林之間存在下列關(guān)系：RF={
3、i=1,2,…,m;m>0}（2）表
4、示形式該樹(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ù)。層次A1BCD2EFGHIJ3KLM4圖6.1一般的樹(shù)A該樹(shù)又可表示為如下三種形式：(a)嵌套集合表示(c)凹入表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))(b)廣義表表示ABCDEFGHIJKLMABCDEFGHIJKLM圖6.2樹(shù)的其他3種表示法（3）樹(shù)的抽象數(shù)據(jù)類型定義ADTTree{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)
5、元素的集合。數(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，有∈H；（3）對(duì)應(yīng)于D－{root}的劃分，H－{,…,}有唯一的一個(gè)劃分H1,H2,…,Hm(m>0)，對(duì)任意j≠
6、k(1≤j,k≤m)有Hj∩Hk＝Ф，且對(duì)任意i(1≤i≤m)，Hi是Di上的二元關(guān)系，(Di,{Hi})是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)?；静僮鳎篒nitTree(&T);操作結(jié)果：構(gòu)造空樹(shù)T。DestroyTree(&T);初始條件：樹(shù)T存在。操作結(jié)果：銷毀樹(shù)T。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é)果：若
7、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。Parent(T,cur_e);初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)
8、值為“空”。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);
9、初始條件：樹(shù)T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p指結(jié)點(diǎn)的度。操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵子樹(shù)。TraverseTree(T,v
