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

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

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

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

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

數據對象D：一個集合，該集合中的所有元素具有相同的特性。數據關系R：若D為空集，則為空樹。若D中僅含有一個數據元素，則R為空集，否則R={H}，H是如下的二元關系：

(1)在D中存在唯一的稱為根的數據元素root，它在關系H下沒有前驅。

(2)除root以外，D中每個結點在關系H下都有且僅有一個前驅。樹的概念和定義

基本操作：

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

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

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

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

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

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

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

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

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

(11)TraverseTree（Tree，Visit（））：樹Tree存在，Visit（）是對結點進行訪問的函數。按照某種次序對樹Tree的每個結點調用Visit（）函數訪問一次且最多一次。若Visit（）失敗，則操作失敗。樹的概念和定義二叉樹的定義與基本操作

樹的概念和定義

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

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

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

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

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

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

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

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

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

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

樹的概念和定義

性質1:

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

性質2:

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

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

性質3:

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

設二叉樹中分支數目為B，因為除根結點外，每個結點均對應一個進入它的分支，所以有n=B+1樹的概念和定義

又因為二叉樹中的分支都是由度為1和度為2的結點發出，所以分支數目為B=n1+2n2

整理上述兩式可得到

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

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

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

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

性質4：具有n個結點的完全二叉樹的深度為［log2n］+1。證明：假設n個結點的完全二叉樹的深度為k，根據性質2可知，k-1層滿二叉樹的結點總數為n1=2k-1-1k層滿二叉樹的結點總數為n2=2k-1

顯然有n1<n≤n2，進一步可以推出n1+1≤n<n2+1。將n1=2k-1-1和n2=2k-1代入上式，可得2k-1≤n<2k，即k-1≤log2n<k。因為k是整數，所以k-1=［log2n］，k=［log2n］+1,故結論成立。樹的概念和定義

性質5:

對于具有n個結點的完全二叉樹，如果按照從上到下和從左到右的順序對二叉樹中的所有結點從1開始順序編號，則對于任意的序號為i的結點有：（1）如i=1，則序號為i的結點是根結點，無雙親結點；如i>1，則序號為i的結點的雙親結點序號為［i/2］。（2）如2×i>n，則序號為i的結點無左孩子；如2×i≤n，則序號為i的結點的左孩子結點的序號為2×i。（3）如2×i＋1>n，則序號為i的結點無右孩子；如2×i＋1≤n，則序號為i的結點的右孩子結點的序號為2×i＋1。樹的概念和定義

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

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

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

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

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

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

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

(1)訪