樹的概念和定義

樹的概念與定義樹的概念和定義

樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合T。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n>0時(shí)，該集合滿足如下條件：

(1)其中必有一個(gè)稱為根（root）的特定結(jié)點(diǎn)，它沒(méi)有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。

(2)其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m≥0）個(gè)互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。樹的概念和定義圖6.1樹的圖示方法樹的概念和定義結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其它結(jié)點(diǎn)的分支信息。結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)稱為此結(jié)點(diǎn)的度。葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。雙親結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接前驅(qū)稱為該結(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)。在圖6.1中，結(jié)點(diǎn)K的祖先是A、B、E。子孫結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼和間接后繼稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。在圖6.1中，結(jié)點(diǎn)D的子孫是H、I、J、M。樹的度：樹中所有結(jié)點(diǎn)的度的最大值。結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始定義，根結(jié)點(diǎn)的層次為1，根的直接后繼的層次為2，依此類推。樹的高度（深度）：樹中所有結(jié)點(diǎn)的層次的最大值。有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。森林：

m（m≥0）棵互不相交的樹的集合。將一棵非空樹的根結(jié)點(diǎn)刪去，樹就變成一個(gè)森林；反之，給森林增加一個(gè)統(tǒng)一的根結(jié)點(diǎn)，森林就變成一棵樹。樹的概念和定義ADTTree

數(shù)據(jù)對(duì)象D：一個(gè)集合，該集合中的所有元素具有相同的特性。數(shù)據(jù)關(guān)系R：若D為空集，則為空樹。若D中僅含有一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下的二元關(guān)系：

(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下沒(méi)有前驅(qū)。

(2)除root以外，D中每個(gè)結(jié)點(diǎn)在關(guān)系H下都有且僅有一個(gè)前驅(qū)。樹的概念和定義

基本操作：

(1)InitTree（Tree）：將Tree初始化為一棵空樹。

(2)DestoryTree（Tree）：銷毀樹Tree。

(3)CreateTree（Tree）：創(chuàng)建樹Tree。

(4)TreeEmpty（Tree）：若Tree為空，則返回TRUE，否則返回FALSE。

(5)Root（Tree）：返回樹Tree的根。

(6)Parent（Tree，x）：樹Tree存在，x是Tree中的某個(gè)結(jié)點(diǎn)。若x為非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。樹的概念和定義(7)FirstChild（Tree，x）：樹Tree存在，x是Tree中的某個(gè)結(jié)點(diǎn)。若x為非葉子結(jié)點(diǎn)，則返回它的第一個(gè)孩子結(jié)點(diǎn)，否則返回“空”。

(8)NextSibling（Tree，x）：樹Tree存在，x是Tree中的某個(gè)結(jié)點(diǎn)。若x不是其雙親的最后一個(gè)孩子結(jié)點(diǎn)，則返回x后面的下一個(gè)兄弟結(jié)點(diǎn)，否則返回“空”。

樹的概念和定義(9)InsertChild（Tree，p，Child）：樹Tree存在，p指向Tree中某個(gè)結(jié)點(diǎn)，非空樹Child與Tree不相交。將Child插入Tree中，做p所指向結(jié)點(diǎn)的子樹。

(10)DeleteChild（Tree，p，i）：樹Tree存在，p指向Tree中某個(gè)結(jié)點(diǎn)，1≤i≤d，d為p所指向結(jié)點(diǎn)的度。刪除Tree中p所指向結(jié)點(diǎn)的第i棵子樹。

(11)TraverseTree（Tree，Visit（））：樹Tree存在，Visit（）是對(duì)結(jié)點(diǎn)進(jìn)行訪問(wèn)的函數(shù)。按照某種次序?qū)銽ree的每個(gè)結(jié)點(diǎn)調(diào)用Visit（）函數(shù)訪問(wèn)一次且最多一次。若Visit（）失敗，則操作失敗。樹的概念和定義二叉樹的定義與基本操作

樹的概念和定義

定義：我們把滿足以下兩個(gè)條件的樹形結(jié)構(gòu)叫做二叉樹（BinaryTree）：（1）每個(gè)結(jié)點(diǎn)的度都不大于2；（2）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。由此定義可以看出，一個(gè)二叉樹中的每個(gè)結(jié)點(diǎn)只能含有0、1或2個(gè)孩子，而且每個(gè)孩子有左右之分。我們把位于左邊的孩子叫做左孩子，位于右邊的孩子叫做右孩子。樹的概念和定義圖6.2給出了二叉樹的五種基本形態(tài)。樹的概念和定義

與樹的基本操作類似，二叉樹有如下基本操作：

(1)Initiate（bt）：將bt初始化為空二叉樹。

(2)Create(bt)：創(chuàng)建一棵非空二叉樹bt。

(3)Destory（bt）：銷毀二叉樹bt。

(4)Empty（bt）：若bt為空，則返回TRUE，否則返回FALSE。

(5)Root(bt)：求二叉樹bt的根結(jié)點(diǎn)。若bt為空二叉樹，則函數(shù)返回“空”。樹的概念和定義

(6)Parent（bt，x）：求雙親函數(shù)。求二叉樹bt中結(jié)點(diǎn)x的雙親結(jié)點(diǎn)。若結(jié)點(diǎn)x是二叉樹的根結(jié)點(diǎn)或二叉樹bt中無(wú)結(jié)點(diǎn)x，則返回“空”。(7)LeftChild（bt，x）：求左孩子。若結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或x不在bt中，則返回“空”。(8)RightChild（bt，x）：求右孩子。若結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或x不在bt中，則返回“空”。

(9)Traverse（bt）:遍歷操作。按某個(gè)次序依次訪問(wèn)二叉樹中每個(gè)結(jié)點(diǎn)一次且僅一次。

(10)Clear（bt）：清除操作。將二叉樹bt置為空樹。樹的概念和定義二叉樹的性質(zhì)

樹的概念和定義

性質(zhì)1:

在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。證明：用數(shù)學(xué)歸納法。歸納基礎(chǔ)：當(dāng)i=1時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，結(jié)論成立。歸納假設(shè)：假設(shè)i=k時(shí)結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)?，F(xiàn)證明當(dāng)i=k+1時(shí)，結(jié)論成立：因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為2，則第k+1層的結(jié)點(diǎn)總數(shù)最多為第k層上結(jié)點(diǎn)最大數(shù)的2倍，即2×2k-1=2(k+1)-1，故結(jié)論成立。樹的概念和定義

性質(zhì)2:

深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k≥1）。

證明：因?yàn)樯疃葹閗的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為故結(jié)論成立。樹的概念和定義

性質(zhì)3:

對(duì)任意一棵二叉樹T，若終端結(jié)點(diǎn)數(shù)為n0，而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹中度為1的結(jié)點(diǎn)總數(shù)。因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度小于等于2，所以有n=n0+n1+n2

設(shè)二叉樹中分支數(shù)目為B，因?yàn)槌Y(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有n=B+1樹的概念和定義

又因?yàn)槎鏄渲械姆种Ф际怯啥葹?和度為2的結(jié)點(diǎn)發(fā)出，所以分支數(shù)目為B=n1+2n2

整理上述兩式可得到

n=B+1=n1+2n2+1

將n=n0+n1+n2代入上式，得出n0+n1+n2=n1+2n2+1，整理后得n0=n2+1，故結(jié)論成立。樹的概念和定義滿二叉樹：

深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。圖6.3(a)所示的二叉樹，即為一棵滿二叉樹。滿二叉樹的順序表示，即從二叉樹的根開始，層間從上到下，層內(nèi)從左到右，逐層進(jìn)行編號(hào)（1，2，…，n）。例如圖6.3(a)所示的滿二叉樹的順序表示為(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15)。樹的概念和定義

完全二叉樹：深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹，如果其結(jié)點(diǎn)1~n的位置序號(hào)分別與滿二叉樹的結(jié)點(diǎn)1~n的位置序號(hào)一一對(duì)應(yīng)，則為完全二叉樹，如圖6.3(b)所示。滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。樹的概念和定義圖6.3滿二叉樹與完全二叉樹樹的概念和定義

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為［log2n］+1。證明：假設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹的結(jié)點(diǎn)總數(shù)為n1=2k-1-1k層滿二叉樹的結(jié)點(diǎn)總數(shù)為n2=2k-1

顯然有n1<n≤n2，進(jìn)一步可以推出n1+1≤n<n2+1。將n1=2k-1-1和n2=2k-1代入上式，可得2k-1≤n<2k，即k-1≤log2n<k。因?yàn)閗是整數(shù)，所以k-1=［log2n］，k=［log2n］+1,故結(jié)論成立。樹的概念和定義

性質(zhì)5:

對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)有：（1）如i=1，則序號(hào)為i的結(jié)點(diǎn)是根結(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn)；如i>1，則序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào)為［i/2］。（2）如2×i>n，則序號(hào)為i的結(jié)點(diǎn)無(wú)左孩子；如2×i≤n，則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2×i。（3）如2×i＋1>n，則序號(hào)為i的結(jié)點(diǎn)無(wú)右孩子；如2×i＋1≤n，則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2×i＋1。樹的概念和定義

可以用歸納法證明其中的（2）和（3）：當(dāng)i=1時(shí)，由完全二叉樹的定義知，如果2×i=2≤n，說(shuō)明二叉樹中存在兩個(gè)或兩個(gè)以上的結(jié)點(diǎn)，所以其左孩子存在且序號(hào)為2；反之，如果2>n，說(shuō)明二叉樹中不存在序號(hào)為2的結(jié)點(diǎn)，其左孩子不存在。同理，如果2×i+1=3≤n，說(shuō)明其右孩子存在且序號(hào)為3；如果3>n，則二叉樹中不存在序號(hào)為3的結(jié)點(diǎn)，其右孩子不存在。假設(shè)對(duì)于序號(hào)為j(1≤j≤i)的結(jié)點(diǎn)，當(dāng)2×j≤n時(shí)，其左孩子存在且序號(hào)為2×j，當(dāng)2×j>n時(shí)，其左孩子不存在；當(dāng)2×j+1≤n時(shí)，其右孩子存在且序號(hào)為2×j+1，當(dāng)2×j+1>n時(shí)，其右孩子不存在。樹的概念和定義

當(dāng)i=j+1時(shí)，根據(jù)完全二叉樹的定義，若其左孩子存在，則其左孩子結(jié)點(diǎn)的序號(hào)一定等于序號(hào)為j的結(jié)點(diǎn)的右孩子的序號(hào)加1，即其左孩子結(jié)點(diǎn)的序號(hào)等于（2×j+1）+1=2（j+1）=2×i，且有2×i≤n；如果2×i>n，則左孩子不存在。若右孩子結(jié)點(diǎn)存在，則其右孩子結(jié)點(diǎn)的序號(hào)應(yīng)等于其左孩子結(jié)點(diǎn)的序號(hào)加1，即右孩子結(jié)點(diǎn)的序號(hào)為2×i+1，且有2×i+1≤n；如果2×i+1>n，則右孩子不存在。故（2）和（3）得證。樹的概念和定義

由（2）和（3）我們可以很容易證明（1）。當(dāng)i=1時(shí)，顯然該結(jié)點(diǎn)為根結(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn)。當(dāng)i>1時(shí)，設(shè)序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為m，如果序號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，根據(jù)（2）有i=2×m，即m=i/2;如果序號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，根據(jù)（3）有i=2×m+1，即m=（i-1）/2=i/2-1/2，綜合這兩種情況，可以得到，當(dāng)i>1時(shí)，其雙親結(jié)點(diǎn)的序號(hào)等于［i/2］。證畢。樹的概念和定義二叉樹的存儲(chǔ)結(jié)構(gòu)樹的概念和定義二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點(diǎn)最多可有兩個(gè)后繼。二叉樹的存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。1.順序存儲(chǔ)結(jié)構(gòu)圖6.4二叉樹與順序存儲(chǔ)結(jié)構(gòu)樹的概念和定義圖6.5單支二叉樹與其順序存儲(chǔ)結(jié)構(gòu)樹的概念和定義2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)于任意的二叉樹來(lái)說(shuō)，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、左孩子域和右孩子：LChildDataRChild其中，LChild域指向該結(jié)點(diǎn)的左孩子，Data域記錄該結(jié)點(diǎn)的信息，RChild域指向該結(jié)點(diǎn)的右孩子。樹的概念和定義用C語(yǔ)言可以這樣聲明二叉樹的二叉鏈表結(jié)點(diǎn)的結(jié)構(gòu)：typedefstructNode{DataTypedata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;有時(shí)，為了便于找到父結(jié)點(diǎn)，可以增加一個(gè)Parent域，Parent域指向該結(jié)點(diǎn)的父結(jié)點(diǎn)。該結(jié)點(diǎn)結(jié)構(gòu)如下：LChildDataparentRChild樹的概念和定義圖6.6二叉樹和二叉鏈表樹的概念和定義

若一個(gè)二叉樹含有n個(gè)結(jié)點(diǎn)，則它的二叉鏈表中必含有2n個(gè)指針域，其中必有n＋1個(gè)空的鏈域。此結(jié)論證明如下：證明：分支數(shù)目B=n-1，即非空的鏈域有n-1個(gè)，故空鏈域有2n-(n-1)=n+1個(gè)。不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹的操作也不同。如要找某個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，在三叉鏈表中很容易實(shí)現(xiàn)；在二叉鏈表中則需從根指針出發(fā)一一查找?？梢姡诰唧w應(yīng)用中，需要根據(jù)二叉樹的形態(tài)和需要進(jìn)行的操作來(lái)決定二叉樹的存儲(chǔ)結(jié)構(gòu)。樹的概念和定義二叉樹的遍歷樹的概念和定義圖6.7二叉樹結(jié)點(diǎn)的基本結(jié)構(gòu)樹的概念和定義

我們用L、D、R分別表示遍歷左子樹、訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹，那么對(duì)二叉樹的遍歷順序就可以有六種方式：(1)訪問(wèn)根，遍歷左子樹，遍歷右子樹（記做DLR）。(2)訪問(wèn)根，遍歷右子樹，遍歷左子樹（記做DRL）。(3)遍歷左子樹，訪問(wèn)根，遍歷右子樹（記做LDR）。(4)遍歷左子樹，遍歷右子樹，訪問(wèn)根（記做LRD）。(5)遍歷右子樹，訪問(wèn)根，遍歷左子樹（記做RDL）。(6)遍歷右子樹，遍歷左子樹，訪問(wèn)根（記做RLD）。樹的概念和定義

注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹中亦按上述規(guī)律進(jìn)行遍歷。下面就分別介紹三種遍歷方法的遞歸定義。

·先序遍歷（DLR）操作過(guò)程：若二叉樹為空，則空操作，否則依次執(zhí)行如下3個(gè)操作：

(1)訪