《數(shù)據(jù)結(jié)構(gòu)與算法》PPT課件

《《數(shù)據(jù)結(jié)構(gòu)與算法》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)及其算法）馮耀霖Chap5樹(shù)?樹(shù)的基本概念?二叉樹(shù)?二叉樹(shù)遍歷?樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)結(jié)構(gòu)是元素之間具有分層關(guān)系的結(jié)構(gòu)，它類似于自然界中的樹(shù)，是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)。一方面，計(jì)算機(jī)應(yīng)用中常出現(xiàn)嵌套的數(shù)據(jù)，樹(shù)結(jié)構(gòu)提供了對(duì)該類數(shù)據(jù)的自然表示；另一方面，利用樹(shù)結(jié)構(gòu)可以有效地解決一些算法問(wèn)題。因此，樹(shù)結(jié)構(gòu)有著廣泛的應(yīng)用。樹(shù)結(jié)構(gòu)常采用遞歸方式定義，被稱為遞歸數(shù)據(jù)結(jié)構(gòu)，有關(guān)樹(shù)的許多算法是遞歸的?！?樹(shù)的基本概念▲樹(shù)的定義▲基本術(shù)語(yǔ)▲樹(shù)的基本操作1.1樹(shù)的定義層次結(jié)構(gòu)的數(shù)據(jù)在現(xiàn)實(shí)世界中大量存在。例如，一個(gè)國(guó)家包括若干省，一個(gè)省有若干市，每個(gè)市管轄若干個(gè)縣、區(qū)。又

2、如，書(shū)的內(nèi)容可以分成章節(jié)，章節(jié)編號(hào)也是有層次的。所有上級(jí)和下級(jí)、整體和部分、祖先和后裔的關(guān)系都是層次關(guān)系的例子。1.樹(shù)（Tree）的一般定義樹(shù)T=(D,R)，其中，D是包含n個(gè)結(jié)點(diǎn)的有限非空集合，R是D上的關(guān)系的集合，R滿足以下特性：(1)有且僅有一個(gè)結(jié)點(diǎn)r∈D，不存在任何結(jié)點(diǎn)v∈D，v≠r，使得∈R，稱r為樹(shù)的根（root）；(2)除根之外的所有結(jié)點(diǎn)u∈D，都有且僅有一個(gè)結(jié)點(diǎn)v，v≠u，使得∈R。(3)樹(shù)中任一結(jié)點(diǎn)x∈D，都可以有m（m≥0）個(gè)結(jié)點(diǎn)yi（i≥0），使得∈R。從上述定義可知，樹(shù)不為空集合，樹(shù)中至少有一個(gè)根結(jié)點(diǎn)，根結(jié)點(diǎn)

3、沒(méi)有前驅(qū)，其余結(jié)點(diǎn)都有唯一的前驅(qū)結(jié)點(diǎn)，而每個(gè)結(jié)點(diǎn)又都可以有0或多個(gè)后繼結(jié)點(diǎn)。因此，樹(shù)形成了層次結(jié)構(gòu)。2.樹(shù)的遞歸定義樹(shù)是包含n個(gè)結(jié)點(diǎn)的有限非空集合T，其中一個(gè)特定的結(jié)點(diǎn)r稱為根，其余結(jié)點(diǎn)(T-{r})劃分成m（m≥0）個(gè)互不相交的子集T1,T2,…Tm，其中每一個(gè)子集都是樹(shù)，被稱為根r的子樹(shù)。圖5.1樹(shù)的示例AACBDGEFKLHIJM（a）（b）在圖5.1中，（a）是只有一個(gè)根結(jié)點(diǎn)的樹(shù)；(b)是有13個(gè)結(jié)點(diǎn)的樹(shù)，其中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的子樹(shù)

4、，且本身也是一棵樹(shù)。例如T1，其根為B，其余結(jié)點(diǎn)分成2個(gè)互不相交的子集：T11={E,K,L}，T12={F}。T11和T12都是B的子樹(shù)。在T11中，E是根，{K}和{L}是E的兩棵互不相交的子樹(shù)，其本身又是只有一個(gè)根結(jié)點(diǎn)的樹(shù)。可以看出，上述兩種關(guān)于樹(shù)的定義是完全一致的。1.2基本術(shù)語(yǔ)結(jié)點(diǎn)：樹(shù)中的每個(gè)元素分別對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)包含數(shù)據(jù)元素值及其邏輯關(guān)系信息（后繼／子樹(shù)的指針）。結(jié)點(diǎn)的度：一結(jié)點(diǎn)擁有的子樹(shù)數(shù)目。樹(shù)的度：樹(shù)中結(jié)點(diǎn)度的最大值。葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，簡(jiǎn)稱葉子，又稱終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度大于0的結(jié)點(diǎn)，又稱非終端結(jié)點(diǎn)。子結(jié)點(diǎn)和父結(jié)點(diǎn)：如果一結(jié)點(diǎn)有子樹(shù)，則子

5、樹(shù)的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)，反之，該結(jié)點(diǎn)是子結(jié)點(diǎn)的父結(jié)點(diǎn)。結(jié)點(diǎn)的層次：樹(shù)有明顯的層次關(guān)系。根結(jié)點(diǎn)為第一層，根結(jié)點(diǎn)的子結(jié)點(diǎn)處于第二層，以此類推。樹(shù)的深度：樹(shù)中結(jié)點(diǎn)的最大層次，也稱樹(shù)的高度。兄弟結(jié)點(diǎn)：同一父結(jié)點(diǎn)的結(jié)點(diǎn)互為兄弟。堂兄弟結(jié)點(diǎn)：在同一層上但父結(jié)點(diǎn)不同的結(jié)點(diǎn)互為堂兄弟。祖先結(jié)點(diǎn)：從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。子孫／后裔結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的所有子樹(shù)上的任何結(jié)點(diǎn)都是該結(jié)點(diǎn)的后裔。路徑：從某個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的分支（邊）構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。有序樹(shù)：如果將樹(shù)中根結(jié)點(diǎn)的各子樹(shù)看成是從左到右有次序的，則稱該樹(shù)是有序樹(shù)。從左到右，可分別稱這些子

6、樹(shù)為第一子樹(shù)、第二子樹(shù)等。無(wú)序樹(shù)：如果根結(jié)點(diǎn)的各子樹(shù)之間不存在確定的次序關(guān)系，可以交換位置，則稱該樹(shù)是無(wú)序樹(shù)，也就是通常所說(shuō)的樹(shù)。森林：是樹(shù)的集合。與現(xiàn)實(shí)世界的森林不同，在數(shù)據(jù)結(jié)構(gòu)中，森林和樹(shù)只有微小的差別，刪去樹(shù)根，樹(shù)變成森林，對(duì)森林加上一個(gè)結(jié)點(diǎn)作為樹(shù)根，森林即成為樹(shù)。但是需要注意的是，森林可以是空森林，但樹(shù)不能是空樹(shù)。圖5.2樹(shù)和森林的例子FEBAGCDLMNJXYZUEFBADCGJLNMT1T2T3(a)樹(shù)T1和T2組成的森林(b)樹(shù)T3在圖5.2(a)中，T1和T2是兩棵樹(shù)，組合在一起成為森林。如果樹(shù)是無(wú)序的，則圖5.2(a)中的樹(shù)T1和圖5.2(b)中

7、的樹(shù)T3是相同的樹(shù)，否則它們是不相同的樹(shù)。在樹(shù)T1中，結(jié)點(diǎn)A、F、和B是結(jié)點(diǎn)E的子結(jié)點(diǎn)，結(jié)點(diǎn)E是A、F、B的父結(jié)點(diǎn)，A、F和B互為兄弟。結(jié)點(diǎn)E、F、C和L都是結(jié)點(diǎn)N的祖先，F(xiàn)的后裔結(jié)點(diǎn)有C、L、M、N、D和J。結(jié)點(diǎn)E的度為3。根結(jié)點(diǎn)E的層次是1，F(xiàn)的層次是2，樹(shù)T1的深度為5，T2的深度為3。在樹(shù)T1中，G、M、N、J和B是葉子結(jié)點(diǎn)，其余結(jié)點(diǎn)是分支結(jié)點(diǎn)。就邏輯結(jié)構(gòu)而言，任何一棵樹(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棵子

8、樹(shù)；當(dāng)m≠