樹森林及其應(yīng)用

?8.1樹和森林的基本概念

8.2樹的存儲(chǔ)

8.3樹的基本算法

8.4樹的應(yīng)用——B-樹第8章樹和森林及其應(yīng)用樹的定義：

樹是由n(n≥0)個(gè)節(jié)點(diǎn)組成的有限集合，其中：⑴當(dāng)n＝0時(shí)為空樹；⑵當(dāng)n＞0時(shí)，有且僅有一個(gè)特定的節(jié)點(diǎn)，稱為樹的根，其余節(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的子集，其中每一個(gè)子集本身又是一棵樹，并且稱為根的子樹?？梢?，樹的定義也是遞歸定義。樹結(jié)構(gòu)中常用的基本術(shù)語父結(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)有子樹，則該結(jié)點(diǎn)為父結(jié)點(diǎn)。孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)子樹的根。兄弟結(jié)點(diǎn)：同一個(gè)結(jié)點(diǎn)的孩子。層次：根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次是其父結(jié)點(diǎn)的層次加1。ABCDEFGH高度（深度）：樹中結(jié)點(diǎn)的最大層次數(shù)。度：一個(gè)結(jié)點(diǎn)的孩子數(shù)目是這個(gè)結(jié)點(diǎn)的度。如：圖中A的度為2,B度為3.葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。樹的度：樹中結(jié)點(diǎn)的最大的度。上圖中樹的度為3。有序樹/無序樹：兄弟結(jié)點(diǎn)之間的排列是否有序。ABCDEFGH注意：雖然樹結(jié)構(gòu)的圖形表示形式和二叉樹的圖形表示形式有相似之處，但兩者從本質(zhì)上說是不同的－－二叉樹中每個(gè)結(jié)點(diǎn)的孩子都有左右之分：左孩子、右孩子；而樹不是。例：三個(gè)結(jié)點(diǎn)所構(gòu)成的樹。ABCCAB結(jié)論：二叉樹和樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)。森林：

森林是m(m≥0)棵互不相交的樹的集合。即：森林是多棵樹。EFADCBJIHG8.1樹和森林的基本概念?8.2樹的存儲(chǔ)

8.3樹的基本運(yùn)算

8.4樹的應(yīng)用——B-樹第8章樹和森林及其應(yīng)用?8.2.1雙親表示法

8.2.2孩子表示法

8.2.3孩子兄弟表示法8.2樹的存儲(chǔ)dataparent數(shù)據(jù)

雙親

實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域

數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息

雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置特點(diǎn)：找雙親容易，找孩子難.

其結(jié)點(diǎn)的結(jié)構(gòu)如下：

typedefstructnode{datatypedata;intparent;}Tnode;6012345789dataparent0號(hào)單元不用或存結(jié)點(diǎn)個(gè)數(shù)如何找孩子結(jié)點(diǎn)abcdfehgiacdefghib01223555109雙親表示法的形式說明如下：

＃defineMAX_NODE_NUM

100typedefstructTnode{datatypedata;intparent;}PTNode;一棵樹可以定義為:typedefstruct{PTNode

nodes[MAX_NODE_NUM];intnodeNum;/*結(jié)點(diǎn)數(shù)*/}Parentree;6012345789dataparent8.2.1雙親表示法

?

8.2.2孩子表示法

8.2.3孩子兄弟表示法8.2樹的存儲(chǔ)實(shí)現(xiàn)：

(1)把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表；n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表）。

(2)n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針組成一個(gè)順序表。6012345789acdefghibdatafc23∧45∧978∧6∧如何找雙親結(jié)點(diǎn)abcdfehgi∧∧∧∧∧這種存儲(chǔ)結(jié)構(gòu)的形式說明如下：

typesetstructChildnode

//孩子鏈表結(jié)點(diǎn)的定義

{

intChild;

//該孩子結(jié)點(diǎn)在線性表中的位置

structChildnode*next;

//指向下一個(gè)孩子結(jié)點(diǎn)的指針}Childnode;typedefstruct

//順序表結(jié)點(diǎn)的結(jié)構(gòu)定義

{datatypedata;

//結(jié)點(diǎn)的信息

Childnode*Firstchild;

//指向孩子鏈表的頭指

}Datanode;樹的定義:

typedefstruct{Datanodenodes［MAX］; //順序表

introot,num;

//該樹的根結(jié)點(diǎn)在線性表中的位置和該樹的結(jié)點(diǎn)個(gè)數(shù)

}Childtree;abcdfehgi8.2.1雙親表示法

8.2.2孩子表示法

?

8.2.3孩子兄弟表示法8.2樹的存儲(chǔ)實(shí)現(xiàn)：用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。特點(diǎn)：(1)操作容易

(2)破壞了樹的層次abcdfehgiabcdefghi∧∧∧∧∧∧∧∧∧∧孩子兄弟表示法的類型定義如下：

typedefstructCSnode{datatypedata;//結(jié)點(diǎn)信息

structCSnode*Firstchild,*Nextsibling;

//第一個(gè)孩子,下一個(gè)兄弟}CSnode;

這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)樹的各種操作。

例如：如果要訪問結(jié)點(diǎn)x的第i個(gè)孩子，則只要先從FirstChild域找到第一個(gè)孩子結(jié)點(diǎn)，然后沿著這個(gè)孩子結(jié)點(diǎn)的Nextsibling域連續(xù)走i-1步,便可找到x的第i個(gè)孩子。如果在這種結(jié)構(gòu)中為每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)Parent域，則同樣可以方便地實(shí)現(xiàn)查找雙親的操作。8.1樹和森林的基本概念

8.2樹的存儲(chǔ)?8.3樹的基本運(yùn)算

8.4樹的應(yīng)用——B-樹第8章樹和森林及其應(yīng)用?8.3.1樹(森林)與二叉樹的轉(zhuǎn)換

8.3.2樹(森林)的遍歷8.3樹的基本運(yùn)算ACBED樹ABCDE二叉樹A∧

∧BC∧D∧

∧E∧A∧

∧BC∧D∧∧E∧

A∧

∧

BC∧D∧

E∧對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋8.3.1樹(森林)與二叉樹的轉(zhuǎn)換?

一、樹轉(zhuǎn)換為二叉樹

二、森林轉(zhuǎn)換為二叉樹三、二叉樹轉(zhuǎn)換為樹或森林

將一棵樹轉(zhuǎn)換為二叉樹的方法是：(1)

樹中所有相鄰兄弟之間加一條連線。AEDCBHGF(2)

對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。(3)

以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。下圖是樹轉(zhuǎn)換為二叉樹的結(jié)果示意圖。AEDCBHGFAEDCBHGF8.3.1樹(森林)與二叉樹的轉(zhuǎn)換

一、樹轉(zhuǎn)換為二叉樹

?二、森林轉(zhuǎn)換為二叉樹三、二叉樹轉(zhuǎn)換為樹或森林

森林轉(zhuǎn)換為二叉樹的方法如下：

(1)將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。

(2)將各二叉樹的根結(jié)點(diǎn)連在一起。ADCBJIHGEFDCFJIEABDCFHGJI8.3.1樹(森林)與二叉樹的轉(zhuǎn)換

一、樹轉(zhuǎn)換為二叉樹

二、森林轉(zhuǎn)換為二叉樹?三、二叉樹轉(zhuǎn)換為樹或森林

二叉樹轉(zhuǎn)換為樹或森林，具體方法如下：

(1)若某結(jié)點(diǎn)

x是其父結(jié)點(diǎn)y

的左孩子，則把該結(jié)點(diǎn)x

的右孩子、右孩子的右孩子……都與y

用線連起來。

(2)刪掉原二叉樹中所有父結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。

DCIEABFHGJEFADCBJIHGxyyx8.3.1樹(森林)與二叉樹的轉(zhuǎn)換?

8.3.2樹(森林)的遍歷8.3樹的基本運(yùn)算?一、樹的遍歷二、森林的遍歷8.3.2樹(森林)的遍歷遍歷——按一定規(guī)律走遍樹的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列。常用方法：

先根（序）遍歷：先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹；

后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)；

按層次遍歷：先訪問第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，……第n層的結(jié)點(diǎn)。ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.

樹的先序遍歷二法相同；2.

樹的后序遍歷相當(dāng)于對(duì)應(yīng)二叉樹的中序遍歷；3.

樹沒有中序遍歷，因?yàn)樽訕錈o左右之分。結(jié)論：

一、樹的遍歷?二、森林的遍歷8.3.2樹(森林)的遍歷先序遍歷：若森林為空，返回；訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林；先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷：若森林為空，返回；中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；訪問第一棵樹的根結(jié)點(diǎn)；中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。ABCDEFGHJI討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否相同？例：ABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG結(jié)論：森林的先序和中序遍歷在兩種方式下的結(jié)果相同。結(jié)論：當(dāng)以二叉鏈表做樹的存儲(chǔ)結(jié)構(gòu)時(shí)，樹的先根序列和后根序列可借用二叉樹的先序遍歷和中序遍歷的算法實(shí)現(xiàn)之；對(duì)于森林也一樣。8.1樹和森林的基本概念

8.2樹的存儲(chǔ)

8.3樹的基本算法?8.4樹的應(yīng)用——B-樹第8章樹和森林及其應(yīng)用?8.4.1B－樹的概念

8.4.2B－樹的查找

8.4.3B－樹的插入

8.4.4B－樹的刪除8.4樹的應(yīng)用——B－樹

與二叉排序樹類似，可以定義一種“m叉排序樹”，通常稱為m階B-樹。

一棵m階B-樹，或者是一棵空樹，或者是滿足如下性質(zhì)的樹：每個(gè)結(jié)點(diǎn)最多有m棵子樹、m-1個(gè)關(guān)鍵字；結(jié)點(diǎn)結(jié)構(gòu)如下：nA0K1A1K2A2…KnAn其中：

①n為關(guān)鍵字個(gè)數(shù)，k1,k2,..,kn為n個(gè)按遞增順序排列的鍵值(關(guān)鍵字)；②A0,Al,A2,...,An為(n+1)個(gè)指針,用于指向該結(jié)點(diǎn)的(n+l)棵子樹,即子樹個(gè)數(shù)為(n+l)。A0所指向子樹中的所有關(guān)鍵字的值均小于kl,An所指向子樹中的所有關(guān)鍵字的值均大于kn,Ai(1≤i≤n-1)所指向子樹中的所有關(guān)鍵字的值均大于ki且小于ki+1;（2）根結(jié)點(diǎn)至少有兩棵子樹；

（3）除根結(jié)點(diǎn)之外的所有非葉子結(jié)點(diǎn)至少有棵子樹；（4）所有葉子結(jié)點(diǎn)出現(xiàn)在同一層上，并且不含信息，通常稱為失敗結(jié)點(diǎn)。失敗結(jié)點(diǎn)為虛結(jié)點(diǎn)，在B-樹中并不存在，指向它們的指針為空指針。引入失敗結(jié)點(diǎn)是為了便于分析B-樹的查找性能。說明：

(1)對(duì)于非根結(jié)點(diǎn)的所有分支結(jié)點(diǎn),n(關(guān)鍵字的個(gè)數(shù))的取值范圍為-1≤n≤m-1。

(2)對(duì)于根結(jié)點(diǎn),n的取值范圍為1≤

n≤m－1。例如：在一棵4階B-樹中(m＝4)，每個(gè)結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)最少為4/2－1=1(子樹數(shù)目最少為4/2=2)，最多為4－1＝3(子樹數(shù)目最多為m＝4)。一棵7階B-樹(m＝7)，根結(jié)點(diǎn)至少有2棵子樹(1個(gè)關(guān)鍵字)，其余每個(gè)結(jié)點(diǎn)至少有「7/2=4棵子樹(3個(gè)關(guān)鍵字)；所有非葉子結(jié)點(diǎn)最多有m＝7棵子樹。1501301951251552709023540atbcdfgeh例：四階B-樹37580858.4.1B－樹的概念?

8.4.2B－樹的查找

8.4.3B－樹的插入

8.4.4B－樹的刪除8.4樹的應(yīng)用——B－樹查找方法

在B-樹上進(jìn)行查找的過程與二叉排序樹的查找類似。

(1)根據(jù)給定的鍵值k,先在根結(jié)點(diǎn)的鍵值的集合中采用順序(當(dāng)m較小時(shí))或二分(當(dāng)m較大時(shí))查找方法進(jìn)行查找。

(2)若有k=ki,則查找成功,根據(jù)相應(yīng)的指針即可取得記錄；否則,若k在ki和ki+1之間,取指針Ai所指的結(jié)點(diǎn);(3)重復(fù)這個(gè)查找過程,直到在某結(jié)點(diǎn)中查找成功,或在某結(jié)點(diǎn)處出現(xiàn)Ai

為空,查找失敗.例如，在下圖所示B_樹中查找關(guān)鍵字80和38。1501301951251552709023540atbcdfgeh3758085性能分析

在B-樹上進(jìn)行查找需比較的結(jié)點(diǎn)數(shù)最多為B-樹的高度,B-樹的高度與B-樹的階m和關(guān)鍵字總數(shù)N有關(guān),下面就來討論它們之間的關(guān)系。

(1)根據(jù)B-樹的定義,B-樹的第一層(即根結(jié)點(diǎn))的子樹數(shù)至少為2個(gè)，第二層結(jié)點(diǎn)的子樹數(shù)至少為2*┌m/2┐個(gè),第三層結(jié)點(diǎn)的子樹數(shù)至少為2*(┌m/2┐)2個(gè),以此類推,若B-樹的高度為h，第h層結(jié)點(diǎn)的空指針數(shù)至少為2*(┌m/2┐)h-1。非葉子結(jié)點(diǎn)的子樹數(shù)至少為：根結(jié)點(diǎn)的子樹數(shù)至少為2個(gè)另一方面，B-樹中每個(gè)結(jié)點(diǎn)中的指針數(shù)＝關(guān)鍵字?jǐn)?shù)＋1則所有結(jié)點(diǎn)中的指針數(shù)＝總關(guān)鍵字?jǐn)?shù)＋1×結(jié)點(diǎn)數(shù)即：總指針數(shù)C2＝關(guān)鍵字總數(shù)N+所有結(jié)點(diǎn)數(shù)C4而空指針數(shù)C1＝總指針數(shù)C2－非空指針數(shù)C3，并且，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都由一個(gè)非空指針指向，即所有結(jié)點(diǎn)數(shù)C4=非空指針數(shù)C3+1

從而得到：C1＝C2－C3＝N+C4－C3

＝N+C3+1－C3＝N+1即B-樹中空指針數(shù)＝關(guān)鍵字總數(shù)＋1這與二叉樹中的空指針數(shù)與關(guān)鍵字總數(shù)的關(guān)系相同。(3)綜上所述,可得到如下不等式:N+1≥2*(┌m/2┐)h-1即空指針數(shù)應(yīng)大于等于它所具有的最小值，求解后得：

h≤1+log┌m/2┐(N+1)/2

又：根據(jù)B-樹的定義,m階B-樹的第一層(即根結(jié)點(diǎn))的子樹數(shù)最多為m個(gè)，第二層結(jié)點(diǎn)的子樹數(shù)最多為m*m=m2個(gè),……，則第h層結(jié)點(diǎn)的空指針數(shù)最多為mh個(gè)。即N+1≤mhh≥logm(N+1)由以上分析可知，m階B-樹的高度h為：

logm(N+1)≤h≤1+log┌m/2┐(N+1)/28.4.1B－樹的概念

8.4.2B－樹的查找?

8.4.3B－樹的插入

8.4.4B－樹的刪除8.4樹的應(yīng)用——B－樹

在B-樹中插入一個(gè)關(guān)鍵字k,不是在樹中添加一個(gè)葉子結(jié)點(diǎn),而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字。且要使插入的結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)≤m－1,將涉及到結(jié)點(diǎn)的“分裂"問題。插入方法

?首先經(jīng)過一個(gè)從樹根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的查找過程,如果鍵值k已在樹中,則不用做其他事;否則,找出插入位置,然后再進(jìn)行插入。?對(duì)于葉子結(jié)點(diǎn)處于第(h+1)層的樹,插入的位置總是在第h層。若結(jié)點(diǎn)的關(guān)鍵字值個(gè)數(shù)不超過(m-l),直接把鍵值插就行了;否則需要把結(jié)點(diǎn)分裂成兩個(gè)。分裂的方法：

取一新結(jié)點(diǎn),把原結(jié)點(diǎn)上的關(guān)鍵字和k按升序排序后,從中間位置(即┌m/2┐之處)把關(guān)鍵字(不包括中間位置的關(guān)鍵字)成兩部分,

?左部分所含關(guān)鍵字放在舊結(jié)點(diǎn)中,?

右部分所含關(guān)鍵字放在新結(jié)點(diǎn)中,?中間位置鍵值連同新結(jié)點(diǎn)的存儲(chǔ)位置插入到父親結(jié)點(diǎn)中。?如果父結(jié)點(diǎn)的鍵值個(gè)數(shù)也超過(m-l),要再分裂,再往上插,直至這個(gè)過程傳到根結(jié)點(diǎn)為止。例：已知一棵3階B-樹如圖所示，要求插入52、20、49。614c50f48a25b5386e37d5870g98h5052f48a25b5386e614c37d5870g98h插入52首先查找插入位置5025b61420c5052f37d48a5386e5870g98h插入20

結(jié)點(diǎn)C需要分裂為兩個(gè)結(jié)點(diǎn)(k1~k[m/2]-1)、(k[m/2]+1~km)，k[m/2]插入到其雙親結(jié)點(diǎn)中。61414620c1425b620c’495052插入4948a5870g98he49f50538652f’5386e5052f505249508653494853a5870g98h5250861425b637d20c’8.4.1B－樹的概念

8.4.2B－樹的查找

8.4.3B－樹的插入?

8.4.4B－樹的刪除8.4樹的應(yīng)用——B－樹

若在B–樹上刪除一個(gè)關(guān)鍵字，則首先應(yīng)找到該關(guān)鍵字所在的結(jié)點(diǎn):

?

若該結(jié)點(diǎn)為最下層的非終端結(jié)點(diǎn)，且其中的關(guān)鍵字?jǐn)?shù)目不少于，則刪除完成，否則要進(jìn)行“合并”操作。

?

若所刪關(guān)鍵字為非終端結(jié)點(diǎn)中的Ki，則以指針Ai

所指子樹中的最小關(guān)鍵字Y替代Ki，然后在相應(yīng)的結(jié)點(diǎn)中刪去Y。

nA0K1A1K2A2…KnAn例：刪除4848a50f50anA0K1A1K2A2…KnAn25b5386e614c37d5870g98h51

下面重點(diǎn)討論刪除最下層的非終端結(jié)點(diǎn)中的關(guān)鍵字的情形，有三種可能：被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于，則只需從該結(jié)點(diǎn)中刪去關(guān)鍵字Ki和相應(yīng)指針Ai。例：3階B-樹中刪去1448a25b5386e6c37d50f5870g98h14(2)被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目等于

-1，而與該結(jié)點(diǎn)相鄰的右兄弟（或左兄弟）結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于-1，則需將其兄弟結(jié)點(diǎn)中的最?。ɑ蜃畲螅┑年P(guān)鍵字上移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于（或大于）且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中。48a25b86e