樹(shù)結(jié)構(gòu)

1.1 樹(shù)的定義

樹(shù)(Tree)：個(gè)節(jié)點(diǎn)構(gòu)成的有限集合。當(dāng)n = 0時(shí)，稱(chēng)為空樹(shù)。對(duì)于任一棵非空樹(shù)(n>0)，它具備以下性質(zhì)：

成都創(chuàng)新互聯(lián)公司成立與2013年，是專(zhuān)業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元德清做網(wǎng)站,已為上家服務(wù),為德清各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108

樹(shù)中有一個(gè)稱(chēng)為"根(Root)"的特殊節(jié)點(diǎn)，用r表示；其余節(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集、，...,，其中每個(gè)集合本身又是一棵樹(shù)，稱(chēng)為原來(lái)樹(shù)的子樹(shù)(SubTree)。如下圖：

1.2 樹(shù)結(jié)構(gòu)的術(shù)語(yǔ)

樹(shù)結(jié)構(gòu)中有很多概念術(shù)語(yǔ)，在深入討論樹(shù)結(jié)構(gòu)之前，我們先來(lái)介紹下跟樹(shù)結(jié)構(gòu)有關(guān)的術(shù)語(yǔ)。為了方便理解記憶，結(jié)合具體的一棵樹(shù)結(jié)構(gòu)來(lái)進(jìn)行介紹，樹(shù)結(jié)構(gòu)如下：

節(jié)點(diǎn)：樹(shù)中存儲(chǔ)的項(xiàng)。上圖中的A-L都是節(jié)點(diǎn)。

根節(jié)點(diǎn)：樹(shù)中最頂端的節(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中只有它沒(méi)有父節(jié)點(diǎn)。上圖中的A為根節(jié)點(diǎn)。

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)。根節(jié)點(diǎn)A的度為3；子節(jié)點(diǎn)C的度為1。

樹(shù)的度：樹(shù)中最大節(jié)點(diǎn)度。樹(shù)中最大節(jié)點(diǎn)度為3(根節(jié)點(diǎn)A和子節(jié)點(diǎn)B的度均為3)，所以樹(shù)的度為3。

子節(jié)點(diǎn)(孩子節(jié)點(diǎn))：緊鄰一個(gè)給定的節(jié)點(diǎn)之下，并且直接與給定節(jié)點(diǎn)相連的一個(gè)節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)。上圖中B-L都是子節(jié)點(diǎn)。

父節(jié)點(diǎn)(雙親節(jié)點(diǎn))：緊鄰一個(gè)給定節(jié)點(diǎn)之上，且直接與給定節(jié)點(diǎn)相連的一個(gè)節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)只能有一個(gè)父節(jié)點(diǎn)。上圖中A、B、C、D、H都是父節(jié)點(diǎn)。

兄弟節(jié)點(diǎn)：擁有共同父節(jié)點(diǎn)的子節(jié)點(diǎn)。上圖中B、C、D是兄弟節(jié)點(diǎn)，E、F、G也是兄弟節(jié)點(diǎn)。

葉子節(jié)點(diǎn)：沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。或者說(shuō)度為0的節(jié)點(diǎn)。上圖中標(biāo)綠的幾個(gè)節(jié)點(diǎn)都是葉子節(jié)點(diǎn)。

內(nèi)部節(jié)點(diǎn)：至少有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)。B、C、D、H都是內(nèi)部節(jié)點(diǎn)。

邊/分支：將一個(gè)父節(jié)點(diǎn)連接到其子節(jié)點(diǎn)的線。上圖中的線就是邊也稱(chēng)為分支。

后代(子孫)：以某節(jié)點(diǎn)為根的子樹(shù)中任一節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的后代。E、F、G是節(jié)點(diǎn)B的后代；H、K、L是節(jié)點(diǎn)C的后代，B-L的所有節(jié)點(diǎn)都是根節(jié)點(diǎn)A的后代。

祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)。節(jié)點(diǎn)D是I、J的祖先；根節(jié)點(diǎn)A是所有節(jié)點(diǎn)的祖先。

路徑：連接一個(gè)節(jié)點(diǎn)與其后代節(jié)點(diǎn)邊的序列。A-B-E和A-C-H-K都可以稱(chēng)作一條路徑。

路徑長(zhǎng)度：路徑中邊的數(shù)目。路徑A-B-E的路徑長(zhǎng)度為2；路徑A-C-H-K的路徑長(zhǎng)度為3。

節(jié)點(diǎn)的層次：從根節(jié)點(diǎn)定義，根節(jié)點(diǎn)為第1層，根節(jié)點(diǎn)的子節(jié)點(diǎn)為第2層，依次類(lèi)推。節(jié)點(diǎn)的層在上圖中已經(jīng)標(biāo)出。

深度(高度)：葉子節(jié)點(diǎn)所在的最大層次。上圖中樹(shù)的深度為4。

森林：m棵不相交的樹(shù)的集合。分別以B、C、D為根節(jié)點(diǎn)的子樹(shù)組成的集合可以看做一個(gè)森林。

以上就是樹(shù)結(jié)構(gòu)的一些術(shù)語(yǔ)。

1.3 樹(shù)的分類(lèi)

樹(shù)結(jié)構(gòu)可以分為兩大類(lèi)：有序樹(shù)和無(wú)序樹(shù)。樹(shù)中任意節(jié)點(diǎn)間沒(méi)有順序關(guān)系，那么稱(chēng)其為無(wú)序樹(shù)，也稱(chēng)自由樹(shù)。相對(duì)的，樹(shù)中的任意節(jié)點(diǎn)有順序關(guān)系，稱(chēng)其為有序樹(shù)。在有序樹(shù)中，子節(jié)點(diǎn)被視為按照從左到右的順序排列，最左邊的子節(jié)點(diǎn)稱(chēng)為第一個(gè)子節(jié)點(diǎn)，最右邊的子節(jié)點(diǎn)稱(chēng)為最后一個(gè)子節(jié)點(diǎn)。我們研究的最多的樹(shù)結(jié)構(gòu)就是有序樹(shù)。而有序樹(shù)中最具代表性的樹(shù)結(jié)構(gòu)就是二叉樹(shù)。

二叉樹(shù)就是度不超過(guò)2的有序樹(shù)結(jié)構(gòu)。 二叉樹(shù)中的每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)分支，分別稱(chēng)為左子樹(shù)和右子樹(shù)。

根據(jù)二叉樹(shù)的定義，會(huì)有如下兩種極端的二叉樹(shù)：

?

根據(jù)二叉樹(shù)的形狀，有以下幾種常見(jiàn)的二叉樹(shù)：

平衡二叉樹(shù)：當(dāng)且僅當(dāng)任意節(jié)點(diǎn)的兩棵子樹(shù)的高度差不大于1的二叉樹(shù)。

完全二叉樹(shù)：除了最后一層外，其他層的節(jié)點(diǎn)數(shù)目都達(dá)到最大的二叉樹(shù)。完全二叉樹(shù)是平衡二叉樹(shù)的一個(gè)特例，完全二叉樹(shù)最后一層上的節(jié)點(diǎn)都是從左到右填充的。對(duì)于一顆k層的完全二叉樹(shù)，其節(jié)點(diǎn)總數(shù)最少的情況是：最后一層只有一個(gè)節(jié)點(diǎn)，此時(shí)節(jié)點(diǎn)數(shù)目為：；其節(jié)點(diǎn)總數(shù)最多的情況是：最后一層節(jié)點(diǎn)數(shù)目達(dá)到最大，即滿二叉樹(shù)，此時(shí)節(jié)點(diǎn)數(shù)目為：。對(duì)于節(jié)點(diǎn)數(shù)目為k的完全二叉樹(shù)，其深度為：

滿二叉樹(shù)：所有層的節(jié)點(diǎn)數(shù)目均達(dá)到最大的二叉樹(shù)。滿二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例。對(duì)于深度為k的滿二叉樹(shù)，其節(jié)點(diǎn)數(shù)目是：；對(duì)于節(jié)點(diǎn)數(shù)目為k的滿二叉樹(shù)，其深度為：。

幾種二叉樹(shù)的結(jié)構(gòu)圖如下：

關(guān)于二叉樹(shù)還有一個(gè)性質(zhì)：二叉樹(shù)中葉子節(jié)點(diǎn)數(shù)為(因?yàn)槿~子節(jié)點(diǎn)的度為0，所以下標(biāo)為0)，度為2的節(jié)點(diǎn)數(shù)為 ，那么有: n₀ = n₂ + 1

解析：關(guān)于上面等式關(guān)系的求解我們可以這樣考慮。假設(shè)二叉樹(shù)的總節(jié)點(diǎn)數(shù)為，因?yàn)槎鏄?shù)的節(jié)點(diǎn)度只有0、1、2三種情況，假設(shè)節(jié)點(diǎn)度為0、1、2的節(jié)點(diǎn)數(shù)分別為：n₀、n₁和n₂。那么有n = n₀ + n₁ + n₂。二叉樹(shù)中節(jié)點(diǎn)度為1的節(jié)點(diǎn)有1條邊連接到其子節(jié)點(diǎn)、節(jié)點(diǎn)度為2的節(jié)點(diǎn)有2條邊連接到其子節(jié)點(diǎn)，假設(shè)二叉樹(shù)有E條邊，那么E = n₁ + 2n₂。而我們知道，在二叉樹(shù)中節(jié)點(diǎn)總數(shù)和邊的數(shù)目有這樣的關(guān)系：n = E +1 = n₁ + 2n₂ + 1。聯(lián)立加粗的兩個(gè)等式，容易得出 n₀ = n₂ + 1。