前言

? ? ? ? 在數(shù)據(jù)結(jié)構(gòu)中樹是一種很重要的數(shù)據(jù)結(jié)構(gòu)，很多其他的數(shù)據(jù)結(jié)構(gòu)和算法都是通過樹衍生出來的，比如：堆，AVL樹，紅黑色等本質(zhì)上都是一棵樹，他們只是樹的一種特殊結(jié)構(gòu)，還有其他比如linux系統(tǒng)的文件系統(tǒng)就是一棵樹。下面讓我們一起來學(xué)習(xí)一下樹的結(jié)構(gòu)和特點吧！

1.樹的概念

? ? ? ? 樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n >= 0）個有限的節(jié)點組成的具有層次結(jié)構(gòu)的集合，把它叫做樹，是因為它看起來像一顆倒掛的樹，也就是說它根朝上，而葉子朝下的。

? ? ? ? 》有一個特殊的節(jié)點?稱為根節(jié)點，根節(jié)點沒有前驅(qū)節(jié)點

? ? ? ? 》除了根節(jié)點外，其余節(jié)點被分為M（M>0）個相互不想交的集合T1，T2，T3,...Tm,其中每一個集合Ti（1 <= i <=m）又是一顆結(jié)構(gòu)與樹類似的子樹。每棵子樹的根節(jié)點有且只有一個前驅(qū)，可以有多個后繼。

? ? ? ? 》因此樹是遞歸定義的

? ? ? ?

?

?

注意：樹的結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)

2.與樹相關(guān)

?????????

? ? ? ? 節(jié)點的度：一個節(jié)點含有子樹的個數(shù)，例如上圖中A的度為6，D的度為1。

? ? ? ? 葉子節(jié)點或者終端節(jié)點：度為零的節(jié)點被稱為葉子結(jié)點。例如H，I，P，Q。

? ? ? ? 非終端節(jié)點或者分支節(jié)點：度不為零的節(jié)點，上圖中的：B，C，D,E...

? ? ? ? 雙親節(jié)點或者父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點； 如上圖：A是B的父節(jié)點。

? ? ? ? 孩子節(jié)點或者子節(jié)點： 一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點，如上圖的B是A的孩子節(jié)點。

? ? ? ? 兄弟節(jié)點：具有相同父親節(jié)點的節(jié)點互稱為兄弟節(jié)點。

? ? ? ? 樹的度：一棵樹中，最大節(jié)點的度稱為樹的度，如上圖樹的度為6.

? ? ? ? 節(jié)點的層次：從根節(jié)點開始，根為第一層，根的子節(jié)點為第二層，以此類推。

? ? ? ? 樹的高度或者深度：樹中節(jié)點的最大層次，如上圖樹的高度為4.

? ? ? ? 堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟；如上圖：H，I互為堂兄弟。

? ? ? ? 節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點，如上圖，A是所有節(jié)點的祖先。

? ? ? ? 子孫：以某節(jié)點為根的子樹中的任意一節(jié)點都稱為該節(jié)點的子孫。如上圖A節(jié)點是所有節(jié)點的子孫。

? ? ? ? 森林：由M棵互不相交的樹的集合稱為森林。

3.樹的表示方法

? ? ? ? 樹的結(jié)構(gòu)相對線性表就復(fù)雜多了，要存儲起來很麻煩，既要保存值域，也要保存節(jié)點與節(jié)點之間的關(guān)系，實際中樹的表示方法有很多種，如：雙親表示法，孩子表示法?，孩子雙親保護法以及孩子兄弟保護法。在這里介紹最簡單的孩子兄弟保護法。

typedef int DataType;

struct Node

{

? ? ? ? struct Node* _firstChild1;//第一個孩子節(jié)點

? ? ? ? struct Node* _pNextBrother;//指向其下一個兄弟節(jié)點

? ? ? ? DataType _data;//節(jié)點中的數(shù)據(jù)域

};

??????????

4.樹的應(yīng)用

? ? ? ? ?樹可以表示文件系統(tǒng)的目錄樹結(jié)構(gòu)，如圖：?

?