0x00 樹的概念

?? 樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由 n（n >= 0）個有限節(jié)點組成的一個具有層次關(guān)系的集合。

? 那么為什么叫 "樹" 呢？

?? 我們之所以把它成為 "樹"，是因為它很像我們現(xiàn)實生活中的樹。只是它是倒過來的，根朝上葉子朝下。

0x01 樹的結(jié)構(gòu)

① 有一個特殊的節(jié)點，成為根節(jié)點，根節(jié)點不存在前驅(qū)節(jié)點。

② 除根節(jié)點外，其余節(jié)點被分成 M(M>0) 個互不相交的集合 T1、T2、……、Tm，期中沒一個集合 Ti(1 <= i <= m) 又是一顆結(jié)構(gòu)于樹類似的字?jǐn)?shù)。每顆子樹的節(jié)點有且只有一個前驅(qū)，可以有0個或多個后繼。

③ 因此，樹是遞歸定義的。因為任何樹都會被分成根和子樹。

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

0x02 樹的相關(guān)概念

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

?? 葉子結(jié)點：又稱終端節(jié)點，度為0的節(jié)點稱為葉子結(jié)點。 比如上圖中，BCHIPQ等節(jié)點就是葉子結(jié)點，因為它們的度為0。

? 分支節(jié)點：又稱非終端節(jié)點，度不為0的節(jié)點稱為分支節(jié)點。 比如上圖中，DEFG等節(jié)點就是分支節(jié)點，因為他們的度不為0。

?? 父節(jié)點：又稱雙親結(jié)點，若一個節(jié)點有子節(jié)點，則這個節(jié)點稱作其子節(jié)點的父節(jié)點。 比如上圖中，A是B的父節(jié)點。

?? 子節(jié)點：又稱孩子節(jié)點，若一個節(jié)點有根節(jié)點，則稱為該節(jié)點的子節(jié)點。 如上圖，B是A的子節(jié)點。

?? 兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互相稱為兄弟節(jié)點。 同一個父親生的才算。如上圖，B和C是兄弟節(jié)點，它們的父節(jié)點都是A。

?? 樹的度：一棵樹中最大的節(jié)點的度稱為樹的度。 如上圖，最大的節(jié)點是A，有6個子樹，故A的度為6，所以樹的度為6。

?? 節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推。 也有將根定義為第0層，根的子節(jié)點為第1層的。但是我們建議還是使用根為第1層來定義比較好。

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

??‍♂? 堂兄弟節(jié)點：父節(jié)點在同一層的節(jié)點，它們互為堂兄弟。如上圖，H 和 I 互為堂兄弟。

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

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

?? 森林：由 m(m > 0) 棵互不相交的樹的集合稱為森林。 比如并查集，多個樹構(gòu)成森林。

0x02 樹的表示

? 以前學(xué)單鏈表時只有一個指針，雙鏈表兩個指針，但是樹有多少個指針是不確定的，因為樹沒有規(guī)定一個節(jié)點最多有多少個孩子。那我們該如何定義結(jié)構(gòu)呢？

?? 方式一：假設(shè)說明了樹的度為N，才能勉強(qiáng)用

struct TreeNode {
    int data;
    struct TreeNode* sub[N]; // 指針數(shù)組
};

問題點：

① 可能會存在不少的空間浪費。 

② 萬一沒有限定樹的度為多少呢？這個方式就廢了。

?? 方式二：vector

// 假設(shè)我們定義了一個順序表
// typedef int STLDataType;  //順序表的數(shù)據(jù)類型
 
// 順序表中存節(jié)點的指針
typedef struct TreeNode* SLDataType; //SeqList
 
struct TreeNode {
    int data;
    SeqList s;  // s為SLDataType* array;
};

（C++中這里可以用 vector，但是C里沒有）

即使你沒有告訴我度是多少，我有多少個孩子我就存多少個孩子，所以這里不需要關(guān)心度的問題。但是這里 s 的結(jié)構(gòu)相對復(fù)雜，s 里面有一個類型為SLDataType* 的數(shù)組，這個數(shù)組已經(jīng)是二級指針了，SLDataType 展開后又是一個 struct TreeNode* 。

?? 方式三：雙親表示法

利用結(jié)構(gòu)數(shù)組存儲（更加復(fù)雜）

struct TreeNode {
    int parenti;
    int data;
};

[ A -1] [ B0 ] [ C0 ] [ D0 ] ...... [ H 3 ]  

   ??  每一個元素中存的是結(jié)構(gòu)體   struct TreeNode arr[10]

每個元素內(nèi)只存自己的值和父親的下標(biāo)（A沒有父親是-1，B的父親下標(biāo)是0…… H的父親是D下標(biāo)為3），可以通過一個值找到自己父親。

? 上列的方式各有優(yōu)缺點，那么有沒有最優(yōu)的方法？

? 當(dāng)然有，它就是 —— 《左孩子右兄弟表示法》  有了這個方法，其他的都是渣渣！

typedef int DataType;
 
struct Node {
    struct Node* _firstChind1;   // 永遠(yuǎn)指向第一個孩子
    struct Node* _pNextBrother;  // 指向孩子右邊的兄弟
    DataType _data;
};

?? 解讀：無論你有多少個孩子，它都只存兩個指針。一個指針永遠(yuǎn)指向第一個孩子，另一個指針指向孩子右邊的兄弟（親兄弟）。這個樹的度無論為多少，也不需要用順序表存，但是你任何一個節(jié)點有多少個孩子都能給你表示出來，通過第一個孩子把所有孩子都找出來。不復(fù)雜也沒有浪費，只用兩個指針就把鏈接關(guān)系都表示出來了，不得不說設(shè)計這個的人真是太????了！

 0x03 樹在實際中的運用

文件系統(tǒng)的目錄樹結(jié)構(gòu)、網(wǎng)絡(luò)拓?fù)?，最短路徑問題，搜索引擎、思維導(dǎo)圖等

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

最新評論