本篇內(nèi)容主要講解“php中樹(shù)和二叉樹(shù)的定義及特點(diǎn)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“php中樹(shù)和二叉樹(shù)的定義及特點(diǎn)”吧!

網(wǎng)站的建設(shè)創(chuàng)新互聯(lián)專(zhuān)注網(wǎng)站定制,經(jīng)驗(yàn)豐富,不做模板,主營(yíng)網(wǎng)站定制開(kāi)發(fā).小程序定制開(kāi)發(fā),H5頁(yè)面制作!給你煥然一新的設(shè)計(jì)體驗(yàn)!已為成都服務(wù)器托管等企業(yè)提供專(zhuān)業(yè)服務(wù)。

在計(jì)算機(jī)領(lǐng)域，我們天天要打交道的【文件夾】、數(shù)據(jù)庫(kù)中我們存儲(chǔ)的數(shù)據(jù)，都是樹(shù)的典型的應(yīng)用。今天我們來(lái)學(xué)習(xí)的就是比較偏理論的關(guān)于樹(shù)和二叉樹(shù)的定義以及它們的一些屬性特點(diǎn)。

樹(shù)

從上面實(shí)際生活中的例子里，我們可以看出，樹(shù)這種結(jié)構(gòu)是可以歸納出它的一些特點(diǎn)的。

樹(shù) （Tree）是 N (N>0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)（N=0）;或?yàn)榉强諛?shù) T 。

在這個(gè)定義中，我們需要明確兩個(gè)問(wèn)題：一是樹(shù)一定是有結(jié)點(diǎn)的，二是根據(jù)結(jié)點(diǎn)數(shù)量可以分為空樹(shù)和非空樹(shù)兩種。不過(guò)這只是最基本的定義，它還有一些特性。

有且僅有一個(gè)稱(chēng)之為根的結(jié)點(diǎn)。

也就是說(shuō)，這個(gè)樹(shù)一定是從某一個(gè)結(jié)點(diǎn)開(kāi)始擴(kuò)展出來(lái)的，這個(gè)結(jié)點(diǎn)就向樹(shù)根一樣。從它開(kāi)始向外開(kāi)枝散葉。

除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)可分為 m ( m > 0 ) 個(gè)互不相交的有限集 T1，T2 ……，Tm 其中每一個(gè)集合本身又是一顆樹(shù)，并且稱(chēng)為根的子樹(shù)（SubTree）

這一段可能會(huì)不太好理解，其實(shí)說(shuō)白了就是每個(gè)結(jié)點(diǎn)只有一個(gè)上級(jí)結(jié)點(diǎn)，不能有多個(gè)上級(jí)結(jié)點(diǎn)。同理，平級(jí)結(jié)點(diǎn)之間也不能有聯(lián)系，但是它可以有多個(gè)下級(jí)結(jié)點(diǎn)。

關(guān)于樹(shù)的定義我們可以看下下面這個(gè)圖。

上圖中簡(jiǎn)單的列舉了標(biāo)準(zhǔn)的樹(shù)和不標(biāo)準(zhǔn)的樹(shù)是什么樣子的。其中：

• (a) ，是只有一個(gè)根結(jié)點(diǎn)的樹(shù)，只要有一個(gè)結(jié)點(diǎn)，它就可以稱(chēng)為一個(gè)樹(shù)結(jié)構(gòu)

• (b) ，是一個(gè)標(biāo)準(zhǔn)的樹(shù)結(jié)構(gòu)

• (c) ，注意它的 C 和 H 結(jié)點(diǎn)之間有一條連接線，這個(gè)就不是樹(shù)了，結(jié)點(diǎn)只能有一個(gè)上級(jí)結(jié)點(diǎn)的才稱(chēng)為樹(shù)，這個(gè)其實(shí)就是我們將來(lái)要學(xué)的【圖】了

樹(shù)的相關(guān)術(shù)語(yǔ)

相對(duì)于棧的壓（入）棧、出棧，隊(duì)列的入隊(duì)、出隊(duì)來(lái)說(shuō)，樹(shù)的相關(guān)術(shù)語(yǔ)可就復(fù)雜的多了。不論如何，首先你得先記住這些術(shù)語(yǔ)，要不后面講的東西用得那些術(shù)語(yǔ)只會(huì)讓你更暈。不過(guò)我們一時(shí)記不住也沒(méi)關(guān)系，先有個(gè)大概的印象，在后面的學(xué)習(xí)進(jìn)程中遇到了再回來(lái)復(fù)習(xí)，這樣印象反而會(huì)更加深刻。

• 結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)可能包含一組數(shù)據(jù)，或者指向其它結(jié)點(diǎn)的分支，可以看作是樹(shù)枝分叉的那個(gè)地方，(b)圖中 A、 B、 C、 D、 E 等等這些都是結(jié)點(diǎn)

• 結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)量就叫做結(jié)點(diǎn)的度，其實(shí)就是它的下級(jí)子結(jié)點(diǎn)有幾個(gè)就是幾度，(b)圖中，C 結(jié)點(diǎn)的度為 1 ， D 結(jié)點(diǎn)的度為 3

• 樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)度的最大值，就是擁有最多子結(jié)點(diǎn)的度是多少，這個(gè)樹(shù)的度就是多少，(b) 圖這個(gè)樹(shù)的度為 3

• 葉子：度為0的結(jié)點(diǎn)，也就是沒(méi)有子結(jié)點(diǎn)的結(jié)點(diǎn)，(b) 圖中的 K 、 L 、 F 、 G 、 M 、 I 、 J 就是這顆樹(shù)的葉子結(jié)點(diǎn)

• 雙親和孩子：一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)，就是它的孩子；對(duì)于這些子結(jié)點(diǎn)來(lái)說(shuō)，當(dāng)前這個(gè)結(jié)點(diǎn)就是它的雙親，(b) 圖中，D 的孩子是  H 、 I 、 J ，而  H 、 I 、 J 的雙親就是 D

• 層次：從根結(jié)點(diǎn)算起，根結(jié)點(diǎn)就是第一層，根的孩子就是第二層，依次類(lèi)推，(b) 圖中 G 結(jié)點(diǎn)所在的層次為 3 ，(a) 圖的全部層次都只有 1

• 樹(shù)的深度（高度）：當(dāng)前這顆樹(shù)的最大層次，很明顯，(b) 圖的深度就是 4

• 兄弟、祖先和子孫：兄弟結(jié)點(diǎn)就是這些結(jié)點(diǎn)的雙親是同一個(gè)結(jié)點(diǎn)；祖先結(jié)點(diǎn)就是從根結(jié)點(diǎn)到某個(gè)指定結(jié)點(diǎn)路上的經(jīng)過(guò)的所有結(jié)點(diǎn)；子孫就是從某一個(gè)節(jié)點(diǎn)出發(fā)，到達(dá)目標(biāo)結(jié)點(diǎn)這一路上的所有結(jié)點(diǎn)。(b) 圖中， E、 F 是兄弟，E 的祖先是 A 、 B ， E 的子孫為 K 或者 L

• 堂（表）兄弟：所有在同一層的結(jié)點(diǎn)但雙親不同的結(jié)點(diǎn)都是堂兄弟，同樣還是在 (b) 圖中，G 的堂（表）兄弟有  E、 F ，另外還有   H 、 I 、 J 也是它的表兄弟

二叉樹(shù)

對(duì)于樹(shù)的概念有了一定的了解之后，我們?cè)賮?lái)進(jìn)一步的學(xué)習(xí)另一個(gè)概念，同時(shí)也是在數(shù)據(jù)結(jié)構(gòu)和算法中最重要的一種樹(shù)的形式：二叉樹(shù)。

通常來(lái)說(shuō)，樹(shù)的形態(tài)是可以千變?nèi)f化的，比如一個(gè)結(jié)點(diǎn)可以有 3 個(gè)子結(jié)點(diǎn)，而另一個(gè)結(jié)點(diǎn)可能有 300 個(gè)子結(jié)點(diǎn)。這樣沒(méi)有什么規(guī)則的樹(shù)其實(shí)操作起來(lái)會(huì)非常麻煩，而二叉樹(shù)的定義就要簡(jiǎn)單的多，除了有樹(shù)的性質(zhì)外，它還多了一項(xiàng)內(nèi)容：二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多只有兩個(gè)子結(jié)點(diǎn)，也就是說(shuō)，整個(gè)二叉樹(shù)的度肯定是 2 ，所有結(jié)點(diǎn)的度也不會(huì)超過(guò) 2 。關(guān)于二叉樹(shù)為什么好操作這點(diǎn)，我們?cè)谙乱恍」?jié)的二叉樹(shù)的性質(zhì)中再詳細(xì)地說(shuō)明。所有的樹(shù)結(jié)構(gòu)都是可以通過(guò)一定的規(guī)則變形來(lái)轉(zhuǎn)換成二叉樹(shù)的。

我們同樣還是通過(guò)一張圖示來(lái)展示什么是二叉樹(shù)。

二叉樹(shù)中，左邊的子結(jié)點(diǎn)及其子孫結(jié)點(diǎn)可以看成是關(guān)于當(dāng)前結(jié)點(diǎn)的左子樹(shù)。右邊結(jié)點(diǎn)及其子孫結(jié)點(diǎn)也一樣可以看成是當(dāng)前結(jié)點(diǎn)的右子樹(shù)。根據(jù)結(jié)點(diǎn)的子結(jié)點(diǎn)情況，就有了上面圖中的這幾種二叉樹(shù)形態(tài)。

• (a) 樹(shù)是僅有一個(gè)結(jié)點(diǎn)的樹(shù)，也可以說(shuō)是僅有一個(gè)結(jié)點(diǎn)的二叉樹(shù)

• (b) 樹(shù)是僅有一個(gè)左結(jié)點(diǎn)的二叉樹(shù)

• (c) 樹(shù)是僅有一個(gè)右結(jié)點(diǎn)的二叉樹(shù)

• (d) 樹(shù)是擁有左右兩個(gè)結(jié)點(diǎn)的二叉樹(shù)

二叉樹(shù)的性質(zhì)

性質(zhì)1：在二叉樹(shù)的第 i 層上至多有 2i-1 個(gè)結(jié)點(diǎn)（ i >= 1 ）

性質(zhì)2：深度為 k 的二叉樹(shù)至多有 2k - 1 個(gè)結(jié)點(diǎn)（ k >= 1）

性質(zhì)3：對(duì)任何一顆二叉樹(shù) T ，如果其終端結(jié)點(diǎn)數(shù)為 n0 ，度為2的結(jié)點(diǎn)數(shù)為 n2 ，則 n0 = n2 + 1

性質(zhì)4：具有 n 個(gè)結(jié)點(diǎn) 的完全二叉樹(shù)的深度為 log2n + 1

性質(zhì)5：如果對(duì)一顆有 n 個(gè)結(jié)點(diǎn) 的完全二叉樹(shù)（其深度為 log2n + 1 ）的結(jié)點(diǎn)按層序編號(hào)（從第1層到第 log2n + 1 層，每層從左到右），則對(duì)任一結(jié)點(diǎn) i （ 1 <= i <= n），有：

1. 如果 i = 1 ，則結(jié)點(diǎn) i 是二叉樹(shù)的根，無(wú)雙親；如果 i > 1 ，則其雙親是結(jié)點(diǎn) i / 2

2. 如果 2i > n ，則結(jié)點(diǎn) i 無(wú)左孩子（結(jié)點(diǎn) i 為葉子結(jié)點(diǎn)）；否則其左孩子是結(jié)點(diǎn) 2i

3. 如果 2i + 1 > n ，則結(jié)點(diǎn) i 無(wú)右孩子；否則其右孩子是結(jié)點(diǎn) 2i + 1

關(guān)于二叉樹(shù)的上述五個(gè)性質(zhì)的數(shù)學(xué)證明我們就不詳細(xì)說(shuō)了，畢竟我們這一系列的文章的宗旨也是希望通過(guò)簡(jiǎn)單的示例讓大家學(xué)習(xí)到數(shù)據(jù)結(jié)構(gòu)和算法的精髓，而不是簡(jiǎn)單粗暴的直接用數(shù)學(xué)公式來(lái)推導(dǎo)證明，那么我們就直接來(lái)圖上數(shù)一數(shù)就好了。

• 對(duì)于 性質(zhì)1 來(lái)說(shuō)，我們當(dāng)前這個(gè)二叉樹(shù)根據(jù)公式的話(huà)，在第 3 層上最多只能有 23-1 個(gè)結(jié)點(diǎn)，也就是 4 個(gè)結(jié)點(diǎn)。第 4 層上最多只能有 24-1 ，也就是 23 = 8 個(gè)結(jié)點(diǎn)

• 對(duì)于 性質(zhì)2 來(lái)說(shuō)，當(dāng)前這圖中的樹(shù)的深度為 4 ，也就是最多有 24 - 1 = 15 個(gè)結(jié)點(diǎn)

• 性質(zhì)3 的話(huà)，我們先數(shù)數(shù)度為 2 的結(jié)點(diǎn)有多少，在這個(gè)圖中，度為 2 的結(jié)點(diǎn)有 7 個(gè)，也就是 A 、 B 、 C 、 D 、 E 、 F 、 G ，第 4 層的結(jié)點(diǎn)都是沒(méi)有子結(jié)點(diǎn)的，也就是說(shuō)它們都是 0 度的，也稱(chēng)為終端結(jié)點(diǎn)（葉子結(jié)點(diǎn)），這些結(jié)點(diǎn)的數(shù)量一共是 8 個(gè)。現(xiàn)在 n2 = 7 ，根據(jù)性質(zhì)公式就可以得出 n0 = n2 + 1 = 7 + 1 = 8

• 圖中的結(jié)點(diǎn)數(shù)量為 15 個(gè)，套用 性質(zhì)4 的公式可以得出 log2n + 1 = log215 + 1 = 3.91（向下取整） + 1 = 3 + 1 = 4 ，當(dāng)前樹(shù)的深度即為 4 ，性質(zhì)4 和 性質(zhì)2 可以看作是互補(bǔ)的

• 對(duì)于 性質(zhì)5 來(lái)說(shuō)，請(qǐng)注意每個(gè)結(jié)點(diǎn)邊上的編號(hào)，我們就選取 E 結(jié)點(diǎn)來(lái)作為例子說(shuō)明。E 結(jié)點(diǎn)當(dāng)前為 5 ，所以它的雙親為 5 / 2 = 2 （向下取整）；E 的左孩子為 2i ，也就是 2*5=10 ，E 的右孩子為 2i + 1 ，也就是 2*5+1 = 11；性質(zhì)5 的定義中說(shuō)得更抽象一些，而且是拿葉子結(jié)點(diǎn)來(lái)做說(shuō)明的，針對(duì)的是整個(gè)二叉樹(shù)的情況，但其實(shí)意思和我們這里解釋的是一樣的，大家可以再拿其它結(jié)點(diǎn)驗(yàn)證一下。性質(zhì)5 對(duì)于后面我們要講的使用順序結(jié)構(gòu)來(lái)存儲(chǔ)二叉樹(shù)非常重要！

請(qǐng)務(wù)必掌握并記牢二叉樹(shù)的這五個(gè)性質(zhì)及其含義，因?yàn)樵诤竺娴膶W(xué)習(xí)中，不管是二叉樹(shù)的順序、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，還是二叉樹(shù)的遍歷，都有可能會(huì)接觸到上面的五個(gè)性質(zhì)中的內(nèi)容。可以說(shuō)，它們就是二叉樹(shù)學(xué)習(xí)中最最基礎(chǔ)的靈魂。

森林

最后，我們來(lái)簡(jiǎn)單的了解下什么是“森林”。多個(gè)樹(shù)放在一起，就形成了一片“森林”。就像上文中二叉樹(shù)的解釋圖一樣，(a)(b)(c)(d)放在一起將它們整體一起來(lái)看，就是一片“森林”，在這片“森林”中分別有著(a)(b)(c)(d)這四顆樹(shù)。

森林中的樹(shù)和樹(shù)之間是沒(méi)有聯(lián)系的，如果我們要操作或者遍歷一個(gè)森林的話(huà)，往往是將這片森林轉(zhuǎn)化為一顆樹(shù)。具體的算法和步驟不是我們學(xué)習(xí)的重點(diǎn)，所以大家了解一下即可，有想深入研究的同學(xué)可以搜索相關(guān)的內(nèi)容或者查閱相關(guān)的教材。

總結(jié)

從棧和隊(duì)列前進(jìn)到樹(shù)后，是不是突然感覺(jué)到一下子就邁了一大步？有點(diǎn)搞不懂了？沒(méi)關(guān)系，今天的內(nèi)容其實(shí)都是一些基礎(chǔ)的理論內(nèi)容，能理解的就理解，不能理解的就接著繼續(xù)學(xué)習(xí)之后再返過(guò)來(lái)看今天的這些概念。

學(xué)習(xí)就不不斷地重復(fù)進(jìn)步地過(guò)程，當(dāng)然一切都還是要以地基為基礎(chǔ)的。當(dāng)你了解了樹(shù)的數(shù)據(jù)結(jié)構(gòu)及一些簡(jiǎn)單的遍歷算法之后，再回來(lái)深入的理解這些概念并把他們背下來(lái)，相信一般的面試中關(guān)于樹(shù)相關(guān)的題目就不在話(huà)下了，一起努力吧！

到此，相信大家對(duì)“php中樹(shù)和二叉樹(shù)的定義及特點(diǎn)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！