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

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

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

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

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

數(shù)據(jù)對象D：一個集合，該集合中的所有元素具有相同的特性。數(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)除root以外，D中每個結(jié)點在關(guān)系H下都有且僅有一個前驅(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中的某個結(jié)點。若x為非根結(jié)點，則返回它的雙親，否則返回“空”。樹的概念和定義(7)FirstChild（Tree，x）：樹Tree存在，x是Tree中的某個結(jié)點。若x為非葉子結(jié)點，則返回它的第一個孩子結(jié)點，否則返回“空”。

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

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

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

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

樹的概念和定義

定義：我們把滿足以下兩個條件的樹形結(jié)構(gòu)叫做二叉樹（BinaryTree）：（1）每個結(jié)點的度都不大于2；（2）每個結(jié)點的孩子結(jié)點次序不能任意顛倒。由此定義可以看出，一個二叉樹中的每個結(jié)點只能含有0、1或2個孩子，而且每個孩子有左右之分。我們把位于左邊的孩子叫做左孩子，位于右邊的孩子叫做右孩子。樹的概念和定義圖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é)點。若bt為空二叉樹，則函數(shù)返回“空”。樹的概念和定義

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

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

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

樹的概念和定義

性質(zhì)1:

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

性質(zhì)2:

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

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

性質(zhì)3:

對任意一棵二叉樹T，若終端結(jié)點數(shù)為n0，而其度數(shù)為2的結(jié)點數(shù)為n2，則n0=n2+1。證明：設(shè)二叉樹中結(jié)點總數(shù)為n，n1為二叉樹中度為1的結(jié)點總數(shù)。因為二叉樹中所有結(jié)點的度小于等于2，所以有n=n0+n1+n2

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

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

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

性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為［log2n］+1。證明：假設(shè)n個結(jié)點的完全二叉樹的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹的結(jié)點總數(shù)為n1=2k-1-1k層滿二叉樹的結(jié)點總數(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。因為k是整數(shù)，所以k-1=［log2n］，k=［log2n］+1,故結(jié)論成立。樹的概念和定義

性質(zhì)5:

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

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

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

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

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

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

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

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

(1)訪