目錄

1.樹(shù)的概念

2.樹(shù)的相關(guān)概念?

3.樹(shù)的表示

（1）直接表示法

（2）雙親表示法?

(3)左孩子右兄弟表示法?

? 4.樹(shù)在實(shí)際中的運(yùn)用（表示文件系統(tǒng)的目錄樹(shù)結(jié)構(gòu)）

---

1.樹(shù)的概念

? ?樹(shù)是一種非線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。我們現(xiàn)實(shí)中的樹(shù)是這樣的：

而我們數(shù)據(jù)結(jié)構(gòu)中的樹(shù)是這樣的：

有一個(gè)特殊的結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個(gè)互不相交的集合T1、T2、……、Tm，其中每一個(gè)集合Ti(1又是一棵結(jié)構(gòu)與樹(shù)類(lèi)似的子樹(shù)。

每棵子樹(shù)的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼 因此，樹(shù)是遞歸定義的。

在這里有一個(gè)要注意的點(diǎn)就是：在樹(shù)形結(jié)構(gòu)中，子樹(shù)之間不能有交集，否則就不是樹(shù)形結(jié)構(gòu)。什么意思呢？例如B和C是A的子樹(shù)，而在樹(shù)形結(jié)構(gòu)中，它們不能有任何交集，類(lèi)似于：

如果一個(gè)樹(shù)形結(jié)構(gòu)的字樹(shù)相交的話(huà)，這個(gè)結(jié)構(gòu)就不能稱(chēng)之為樹(shù)形結(jié)構(gòu)。

2.樹(shù)的相關(guān)概念?

?這里有一張圖，我們接下來(lái)關(guān)于樹(shù)的各個(gè)概念都是圍繞這張圖展開(kāi)的：

節(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度； 如上圖：A的為6

葉結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)； 如上圖：B、C、H、I...等結(jié)點(diǎn)為葉結(jié)點(diǎn)，

簡(jiǎn)單來(lái)說(shuō)，沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)就被稱(chēng)為葉子節(jié)點(diǎn)。

非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)； 如上圖：D、E、F、G...等結(jié)點(diǎn)為分支結(jié)點(diǎn)，

所以我們可以說(shuō)一棵樹(shù)是由所有分支節(jié)點(diǎn)加所有葉子節(jié)點(diǎn)組成的。

雙親結(jié)點(diǎn)或父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱(chēng)為其子結(jié)點(diǎn)的父結(jié)點(diǎn)； 如上圖：A是B的父結(jié)點(diǎn)

孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹(shù)的根結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)； 如上圖：B是A的孩子結(jié)點(diǎn)

兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互稱(chēng)為兄弟結(jié)點(diǎn)； 如上圖：B、C是兄弟結(jié)點(diǎn)

樹(shù)的度：一棵樹(shù)中，最大的結(jié)點(diǎn)的度稱(chēng)為樹(shù)的度； 如上圖：樹(shù)的度為6，因?yàn)樵谶@棵樹(shù)中，度最大的結(jié)點(diǎn)是A，它有六個(gè)子節(jié)點(diǎn)，也是這棵樹(shù)中子節(jié)點(diǎn)最多的結(jié)點(diǎn)，所以A的度就是這棵樹(shù)的度。

結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子結(jié)點(diǎn)為第2層，以此類(lèi)推；

樹(shù)的高度或深度：樹(shù)中結(jié)點(diǎn)的最大層次； 如上圖：樹(shù)的高度為4

堂兄弟結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟結(jié)點(diǎn)

結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)；如上圖：A是所有結(jié)點(diǎn)的祖先，對(duì)于Q來(lái)說(shuō)J，E，A是它的祖先

子孫：以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的子孫。如上圖：所有結(jié)點(diǎn)都是A的子孫

森林：由m（m>0）棵互不相交的樹(shù)的集合稱(chēng)為森林；?什么意思呢？只要有兩棵及以上不相交的樹(shù)，我們就可以將其稱(chēng)為森林。

3.樹(shù)的表示

樹(shù)結(jié)構(gòu)相對(duì)線(xiàn)性表就比較復(fù)雜了，要存儲(chǔ)表示起來(lái)就比較麻煩了，既要保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系，實(shí)際中樹(shù)有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法 等。我們?cè)谶@里簡(jiǎn)單的介紹這些方法：

（1）直接表示法

? ?使用直接表示法我們要先了解樹(shù)的度，如果樹(shù)的度是6，我們就要定義6個(gè)指針表示它們：

struct TreeNode
{int data;//數(shù)據(jù)struct TreeNode* child1;//指向孩子節(jié)點(diǎn)的指針struct TreeNode* child2;//...struct TreeNode* child6;}

（2）雙親表示法?

二十五雙親表示法比較簡(jiǎn)單，只要定義一個(gè)指向父節(jié)點(diǎn)的指針就可以：

struct TreeNode
{int data;struct TreeNode* parent;
}

(3)左孩子右兄弟表示法?

我們先將這種方法的表示寫(xiě)出來(lái)：

struct TreeNode
{int val;struct TreeNode* letfchild;struct TreeNode* rightbrother;
}

“左孩子”表示這個(gè)指針只指向該結(jié)點(diǎn)的最左邊的子結(jié)點(diǎn)，而它的子節(jié)點(diǎn)的“左孩子”也指向它自己最左邊的子結(jié)點(diǎn)：

而它的“右兄弟”指針則向右邊尋找兄弟結(jié)點(diǎn)，如果有兄弟結(jié)點(diǎn)，則指向它，然后繼續(xù)向右找，直至右邊找不到兄弟結(jié)點(diǎn)，“右兄弟”指針就指向空，這樣一來(lái)，無(wú)論這棵樹(shù)有多少子結(jié)點(diǎn)都可以用兩個(gè)指針表示，“左孩子右兄弟”表示法也因其巧妙而被廣泛使用。

? 4.樹(shù)在實(shí)際中的運(yùn)用（表示文件系統(tǒng)的目錄樹(shù)結(jié)構(gòu)）

? 樹(shù)在實(shí)際生活中出現(xiàn)得最多的場(chǎng)景就是在我們計(jì)算機(jī)中資源管理器文件系統(tǒng)的目錄結(jié)構(gòu)中，我們打開(kāi)一個(gè)文件夾，里面有若干個(gè)文件，那么這個(gè)文件夾就是根結(jié)點(diǎn)，那若干個(gè)文件就是它的子結(jié)點(diǎn)：

?怎么樣，以這樣的方式展開(kāi)文件夾，它是不是就是我們數(shù)據(jù)結(jié)構(gòu)中的樹(shù)形結(jié)構(gòu)呢。?