數(shù)據(jù)結(jié)構(gòu)樹(shù)簡(jiǎn)介

一、樹(shù)簡(jiǎn)介

樹(shù)(Tree)是一種抽象的數(shù)據(jù)結(jié)構(gòu)，是一個(gè)數(shù)據(jù)的集合，集合中的數(shù)據(jù)組成了一個(gè)樹(shù)狀結(jié)構(gòu)。例如上圖，看起來(lái)像一棵倒掛的樹(shù)，根朝上葉朝下。

樹(shù)是由n(n>=0)個(gè)節(jié)點(diǎn)組成的具有層次關(guān)系的數(shù)據(jù)集合。當(dāng) n=0 時(shí)，樹(shù)中沒(méi)有節(jié)點(diǎn)，稱(chēng)為空樹(shù)。當(dāng) n>0 時(shí)，有且僅有一個(gè)節(jié)點(diǎn)被稱(chēng)為根節(jié)點(diǎn)(Root)，如果 n=1 ，樹(shù)只有根節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)。如果 n>1 ，除根節(jié)點(diǎn)外，將其余的節(jié)點(diǎn)分成m(m>0)個(gè)互不相交的數(shù)據(jù)集合，這 m 個(gè)集合每一個(gè)都要滿(mǎn)足樹(shù)的結(jié)構(gòu)(有且僅有一個(gè)根節(jié)點(diǎn))，并且這 m 棵樹(shù)都“掛”在根節(jié)點(diǎn)上，如此遞歸下去，直到所有節(jié)點(diǎn)都“掛”到這棵樹(shù)上。其中，這 m 個(gè)集合構(gòu)成的 m 棵樹(shù)都被稱(chēng)為根節(jié)點(diǎn)的子樹(shù)。

在理解樹(shù)的結(jié)構(gòu)和定義時(shí)，需要運(yùn)用到遞歸的思想。以下圖為例，樹(shù)的節(jié)點(diǎn)集合為 {A,B,C,D,E,F,G,H} ，n=8，根節(jié)點(diǎn)為 A ，除根節(jié)點(diǎn) A 外，其余節(jié)點(diǎn)組成了兩個(gè)(m=2)集合(m1和m2)，m1集合為 {B,D,E} ，m2集合為 {C,F,G,H} 。在m1中，B 為m1的根節(jié)點(diǎn)，除 B 以外，其余節(jié)點(diǎn)組成兩個(gè)集合，集合 {D} 和集合 {E} ，{D} 和 {E} 都只有一個(gè)節(jié)點(diǎn)，分別構(gòu)成一棵只有一個(gè)節(jié)點(diǎn)的樹(shù)，它們“掛”在m1的根節(jié)點(diǎn) B 上，是 B 的子樹(shù)，m1構(gòu)成一棵樹(shù)，“掛”在根節(jié)點(diǎn) A 上，m1是 A 的子樹(shù)。同理，在m2中，C 為m2根節(jié)點(diǎn)，其余節(jié)點(diǎn)組成三個(gè)集合 {F} 、{G} 和 {H} ......

二、樹(shù)的術(shù)語(yǔ)

要理解樹(shù)這種數(shù)據(jù)結(jié)構(gòu)，必須先理解一些常用的術(shù)語(yǔ)。

樹(shù)由一個(gè)一個(gè)的節(jié)點(diǎn)組成，節(jié)點(diǎn)是構(gòu)成復(fù)雜數(shù)據(jù)結(jié)構(gòu)的基本組成單位。

1. 子節(jié)點(diǎn)：又稱(chēng)為孩子節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)所包含的子樹(shù)的根節(jié)點(diǎn)被稱(chēng)為該節(jié)點(diǎn)的子節(jié)點(diǎn)。如下圖中，節(jié)點(diǎn) B 有兩棵子樹(shù)，這兩棵子樹(shù)的根節(jié)點(diǎn)為 D 和 E ，所以 D 和 E 都是 B 的子節(jié)點(diǎn)。

2. 父節(jié)點(diǎn)：又稱(chēng)為父親節(jié)點(diǎn)，如果一個(gè)節(jié)點(diǎn)有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)被稱(chēng)為其子節(jié)點(diǎn)的父節(jié)點(diǎn)。如下圖中，節(jié)點(diǎn) B 有兩個(gè)子節(jié)點(diǎn) D 和 E ，則 B 是 D 的父節(jié)點(diǎn)，也是 E 的父節(jié)點(diǎn)。

3. 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱(chēng)為兄弟節(jié)點(diǎn)。下圖中的 D 和 E 就互為兄弟節(jié)點(diǎn)。

4. 堂兄弟節(jié)點(diǎn)：如果樹(shù)的兩個(gè)節(jié)點(diǎn)深度相同，但父節(jié)點(diǎn)不同，則它們互為堂兄弟節(jié)點(diǎn)。下圖中的 D與F，D與G，D與H，D與I 都是堂兄弟節(jié)點(diǎn)關(guān)系。

5. 節(jié)點(diǎn)的祖先：從根節(jié)點(diǎn)開(kāi)始，依次找到某節(jié)點(diǎn)所經(jīng)路徑上的所有節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的祖先。如下圖中，節(jié)點(diǎn) J 的祖先節(jié)點(diǎn)為 A,B,D 。

6. 節(jié)點(diǎn)的子孫：以某節(jié)點(diǎn)為根的子樹(shù)中，任一節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的子孫。如下圖中，節(jié)點(diǎn) C 的子孫有 F,G,H,I,M,N,O 。

7. 節(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類(lèi)推。如下圖中，根節(jié)點(diǎn) A 在第1層，節(jié)點(diǎn) M 在第4層。

8. 節(jié)點(diǎn)的深度：一個(gè)節(jié)點(diǎn)所處的層次稱(chēng)為該節(jié)點(diǎn)的深度。如下圖中，根節(jié)點(diǎn) A 的深度為1，節(jié)點(diǎn) M 的深度為4 。(上面解釋堂兄弟節(jié)點(diǎn)時(shí)有用到節(jié)點(diǎn)的深度，現(xiàn)在可以回去看看)

9. 樹(shù)的深度：又稱(chēng)為樹(shù)的高度，一棵樹(shù)中，最大的節(jié)點(diǎn)深度稱(chēng)為樹(shù)的深度。如下圖中的樹(shù)深度為4。

關(guān)于深度和高度，有兩種定義方式，一種是將根節(jié)點(diǎn)的深度定義為0，另一種是將根節(jié)點(diǎn)的深度定義為1。但不管怎樣，每個(gè)深度為 k 的節(jié)點(diǎn)的子節(jié)點(diǎn)的深度都為 k+1 ，這是不變的。

10. 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(shù)(或子節(jié)點(diǎn))的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的度。如下圖中， 根節(jié)點(diǎn) A 的度為2，節(jié)點(diǎn) C 的度為4，節(jié)點(diǎn) I 的度為1，節(jié)點(diǎn) O 的度為 0 。

11. 樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)度稱(chēng)為樹(shù)的度。如下圖中，最大的節(jié)點(diǎn)度是4，則樹(shù)的度為4。

12. 葉節(jié)點(diǎn)：又稱(chēng)為終端節(jié)點(diǎn)，度為零的節(jié)點(diǎn)被稱(chēng)為葉節(jié)點(diǎn)。如下圖中，節(jié)點(diǎn) F,H,J,K,L,M,N,O 都是葉節(jié)點(diǎn)。

13. 森林：由m(m>=0)棵互不相交的樹(shù)構(gòu)成的集合稱(chēng)為森林。森林是從樹(shù)延伸出來(lái)的術(shù)語(yǔ)，森林里的樹(shù)一定是互不相交的。

三、樹(shù)的特點(diǎn)

通過(guò)對(duì)樹(shù)的定義和樹(shù)的術(shù)語(yǔ)進(jìn)行介紹，基本可以理解樹(shù)這種數(shù)據(jù)結(jié)構(gòu)了，總結(jié)起來(lái)，樹(shù)有以下特點(diǎn)。

1. 如果樹(shù)的節(jié)點(diǎn)數(shù) n>0，根節(jié)點(diǎn)是唯一的，不可能存在多個(gè)根節(jié)點(diǎn)。

2. 沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)。根節(jié)點(diǎn)是沒(méi)有父節(jié)點(diǎn)的。

3. 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)。除了根節(jié)點(diǎn)外，其他所有節(jié)點(diǎn)都有父節(jié)點(diǎn)，并且同一個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)，不可能有多個(gè)。

4. 每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)。

5. 除了根節(jié)點(diǎn)外，子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)。這些子樹(shù)一定是互不相交的。

6. 每個(gè)深度為 k 的節(jié)點(diǎn)的子節(jié)點(diǎn)的深度都為 k+1 。

四、樹(shù)的分類(lèi)

所有樹(shù)都滿(mǎn)足以上的特點(diǎn)，除此之外，一些樹(shù)還具有專(zhuān)有的特點(diǎn)。根據(jù)專(zhuān)有的特點(diǎn)，可以對(duì)樹(shù)進(jìn)行分類(lèi)。

1. 無(wú)序樹(shù)：也稱(chēng)為自由樹(shù)，樹(shù)中存在一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒(méi)有順序關(guān)系。如下圖中，右邊的樹(shù)是無(wú)序樹(shù)，從樹(shù)中取一個(gè)節(jié)點(diǎn) D ，D 的子節(jié)點(diǎn)是節(jié)點(diǎn) J 和節(jié)點(diǎn) E，它們是沒(méi)有順序關(guān)系的，所以這是一棵無(wú)序樹(shù)。

2. 有序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系。如下圖中，左邊的樹(shù)是有序樹(shù)，從樹(shù)中任意取一個(gè)節(jié)點(diǎn) C，C 的子節(jié)點(diǎn)是 F,G,H ，它們是有順序關(guān)系的(字母順序)，所以這是一棵有序樹(shù)。

圖中的有序和無(wú)序以字母順序作為案例，實(shí)際應(yīng)用中的“有序”并不限于字母順序、數(shù)字順序等，實(shí)際的有序主要是指“不能互換”。

無(wú)序樹(shù)的節(jié)點(diǎn)之間沒(méi)有順序關(guān)系，節(jié)點(diǎn)之間的關(guān)系不能通過(guò)代碼來(lái)模擬和控制，所以基本沒(méi)有實(shí)際的應(yīng)用場(chǎng)景。

使用樹(shù)這種數(shù)據(jù)結(jié)構(gòu)，基本都是使用有序樹(shù)，對(duì)于有序樹(shù)，又可以分為以下幾種。

1. 二叉樹(shù)：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹(shù)的樹(shù)稱(chēng)為二叉樹(shù)，如下圖。二叉樹(shù)是最常用的樹(shù)結(jié)構(gòu)，可以對(duì)二叉樹(shù)進(jìn)一步細(xì)分(另外的文章再仔細(xì)研究)。

2. 霍夫曼樹(shù)：又稱(chēng)為最優(yōu)二叉樹(shù)，是一種帶權(quán)路徑最短的二叉樹(shù)。

3. B樹(shù)：是一種對(duì)讀寫(xiě)操作進(jìn)行優(yōu)化的自平衡的二叉查找樹(shù)，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個(gè)子樹(shù)。

可以看到，后面的兩種樹(shù)都是在二叉樹(shù)的基礎(chǔ)上，根據(jù)特殊的場(chǎng)景獨(dú)立出來(lái)的，光看定義很難理解，所以以后的文章再研究。

到此這篇關(guān)于數(shù)據(jù)結(jié)構(gòu)之樹(shù)的概念詳解的文章就介紹到這了,更多相關(guān)數(shù)據(jù)結(jié)構(gòu)之樹(shù)的概念內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論