腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)系列之樹的概念結(jié)構(gòu)和常見表示方法

更新時(shí)間：2022年02月24日 16:18:26 作者：檸檬葉子C

本章將正式開啟數(shù)據(jù)結(jié)構(gòu)中?“樹”?部分的講解，本章將介紹樹的概念和結(jié)構(gòu)，以及樹的表示方法，感興趣的朋友進(jìn)來(lái)看看吧

0x00 樹的概念

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

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

?? 我們之所以把它成為 "樹"，是因?yàn)樗芟裎覀儸F(xiàn)實(shí)生活中的樹。只是它是倒過(guò)來(lái)的，根朝上葉子朝下。

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

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

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

③ 因此，樹是遞歸定義的。因?yàn)槿魏螛涠紩?huì)被分成根和子樹。

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

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

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

?? 葉子結(jié)點(diǎn)：又稱終端節(jié)點(diǎn)，度為0的節(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。比如上圖中，BCHIPQ等節(jié)點(diǎn)就是葉子結(jié)點(diǎn)，因?yàn)樗鼈兊亩葹?。

? 分支節(jié)點(diǎn)：又稱非終端節(jié)點(diǎn)，度不為0的節(jié)點(diǎn)稱為分支節(jié)點(diǎn)。比如上圖中，DEFG等節(jié)點(diǎn)就是分支節(jié)點(diǎn)，因?yàn)樗麄兊亩炔粸?。

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

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

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

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

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

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

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

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

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

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

0x02 樹的表示

? 以前學(xué)單鏈表時(shí)只有一個(gè)指針，雙鏈表兩個(gè)指針，但是樹有多少個(gè)指針是不確定的，因?yàn)闃錄](méi)有規(guī)定一個(gè)節(jié)點(diǎn)最多有多少個(gè)孩子。那我們?cè)撊绾味x結(jié)構(gòu)呢？

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

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

問(wèn)題點(diǎn)：

① 可能會(huì)存在不少的空間浪費(fèi)。

② 萬(wàn)一沒(méi)有限定樹的度為多少呢？這個(gè)方式就廢了。

?? 方式二：vector

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

（C++中這里可以用 vector，但是C里沒(méi)有）

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

?? 方式三：雙親表示法

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

struct TreeNode {
    int parenti;
    int data;
};

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

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

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

? 上列的方式各有優(yōu)缺點(diǎn)，那么有沒(méi)有最優(yōu)的方法？

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

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

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

0x03 樹在實(shí)際中的運(yùn)用

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

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

您可能感興趣的文章: