Python 數(shù)據(jù)結(jié)構(gòu)之樹的概念詳解

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

一、樹簡介

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

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

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

二、樹的術(shù)語

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

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

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

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

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

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

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

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

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

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

9. 樹的深度：又稱為樹的高度，一棵樹中，最大的節(jié)點深度稱為樹的深度。如下圖中的樹深度為4。

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

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

11. 樹的度：一棵樹中，最大的節(jié)點度稱為樹的度。如下圖中，最大的節(jié)點度是4，則樹的度為4。

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

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

三、樹的特點

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

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

2. 沒有父節(jié)點的節(jié)點稱為根節(jié)點。根節(jié)點是沒有父節(jié)點的。

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

4. 每個節(jié)點有零個或多個子節(jié)點。

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

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

四、樹的分類

所有樹都滿足以上的特點，除此之外，一些樹還具有專有的特點。根據(jù)專有的特點，可以對樹進行分類。

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

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

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

無序樹的節(jié)點之間沒有順序關(guān)系，節(jié)點之間的關(guān)系不能通過代碼來模擬和控制，所以基本沒有實際的應(yīng)用場景。

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

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

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

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

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

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