什么是樹(shù)

相信大家剛學(xué)數(shù)據(jù)結(jié)構(gòu)的時(shí)候最先接觸的就是順序表,棧,隊(duì)列等線性結(jié)構(gòu).
而樹(shù)則是一種非線性存儲(chǔ)結(jié)構(gòu),存儲(chǔ)的是具有“一對(duì)多”關(guān)系的數(shù)據(jù)元素的集合

非線性 體現(xiàn)在它是由n個(gè)有限結(jié)點(diǎn)(可以是零個(gè)結(jié)點(diǎn))組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的
一對(duì)多 體現(xiàn)在比如對(duì)圖中A來(lái)說(shuō),A對(duì)于和B,C都存在聯(lián)系,同理B,C與其他的也均存在關(guān)系

樹(shù)的常見(jiàn)術(shù)語(yǔ)

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱為該節(jié)點(diǎn)的度(上圖A的為2)
葉節(jié)點(diǎn)/終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)(上圖DEFGH節(jié)點(diǎn)為葉節(jié)點(diǎn))
非終端節(jié)點(diǎn)/分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn),(上圖A,B,C)
雙親節(jié)點(diǎn)/父節(jié)點(diǎn)：若一節(jié)點(diǎn)含有子節(jié)點(diǎn),此節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)(上圖A是B的父節(jié)點(diǎn))
孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一節(jié)點(diǎn)含有的子樹(shù)的根節(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)(B、C是兄弟節(jié)點(diǎn))
樹(shù)的度：一棵樹(shù)中,最大的節(jié)點(diǎn)的度稱為樹(shù)的度(上圖B的度最大,故樹(shù)的度為3)
堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟(如上圖D,E互為兄弟節(jié)點(diǎn))
節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)(上圖A是所有節(jié)點(diǎn)的祖先)
子孫：以某節(jié)點(diǎn)為根的子樹(shù)中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫(上圖所有節(jié)點(diǎn)都是A的子孫)
森林：由n(n>0)棵互不相交的樹(shù)的集合稱為森林

此外,另有兩個(gè)術(shù)語(yǔ)需要單獨(dú)討論一下,即

節(jié)點(diǎn)的層次：從根開(kāi)始定義起，有兩種說(shuō)法
①根為第1層，根的子節(jié)點(diǎn)為第2層…
②根為第0層，根的子節(jié)點(diǎn)為第1層…
樹(shù)的高度或深度：樹(shù)中結(jié)點(diǎn)的最大層次

比如,只有一個(gè)節(jié)點(diǎn),A是第0層,也可以說(shuō)是第1層,兩者都是正確的
但是我更推薦說(shuō)A是第1層,因?yàn)槿绻鸄是第0層,高度或深度就為0,
那么對(duì)于空樹(shù)來(lái)說(shuō),它就只能是-1層,顯然不合理
那么如果A是第1層,高度或深度就為1;而空樹(shù)的高度或深度就為0了,個(gè)人認(rèn)為這種安排更加合理

樹(shù)的表示

樹(shù)有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等.

首先我們來(lái)看一種比較差的表示

struct TreeNode
{
	int val;
	struct  TreeNode* child1;
	struct  TreeNode* child2;
	struct  TreeNode* child3;
	//...
};    //缺點(diǎn)很明顯,浪費(fèi)空間,對(duì)于度只有1或0的節(jié)點(diǎn)就會(huì)浪費(fèi)結(jié)構(gòu)體內(nèi)的空間

//或者稍微改進(jìn)一下
struct TreeNode
{
	int val;
	struct  TreeNode* childArray[5];
};  //同理,如果沒(méi)有5個(gè)孩子的節(jié)點(diǎn)也會(huì)浪費(fèi)空間

現(xiàn)在介紹一種非常常用且厲害的方法: 孩子兄弟表示法

struct TreeNode
{
	int val;
	struct  TreeNode* firstChild;
	struct  TreeNode* brother;
};    

此方法的思路流程如下:(鏈表)

再比如 雙親表示法:只存在父親節(jié)點(diǎn)的指針或者下標(biāo)

#define size 100//樹(shù)中結(jié)點(diǎn)的最大數(shù)量
#define dataType int//樹(shù)結(jié)構(gòu)中數(shù)據(jù)類型
//節(jié)點(diǎn)
typedef struct TreeNode{
    dataType data;//樹(shù)中結(jié)點(diǎn)的數(shù)據(jù)類型
    int parent;//它的父結(jié)點(diǎn)在數(shù)組中的位置下標(biāo)
}TreeNode;
//樹(shù)結(jié)構(gòu):  (上面的方法沒(méi)有寫(xiě)這個(gè)樹(shù)結(jié)構(gòu)是因?yàn)樯厦媸潜举|(zhì)是鏈表,而這里是數(shù)組)
typedef struct {
    PTNode nodes[size];//存放樹(shù)中所有結(jié)點(diǎn)
    int r,nums;//根的位置下標(biāo)和結(jié)點(diǎn)數(shù)
}Tree;

邏輯思路如下(數(shù)組)

樹(shù)的應(yīng)用

1.文件系統(tǒng)：計(jì)算機(jī)的文件系統(tǒng)通常采用樹(shù)形結(jié)構(gòu)來(lái)組織文件和目錄。根節(jié)點(diǎn)是文件系統(tǒng)的根目錄，每個(gè)目錄可以包含子目錄和文件，這種結(jié)構(gòu)可以方便地組織和訪問(wèn)文件。
2.數(shù)據(jù)庫(kù)索引：數(shù)據(jù)庫(kù)中的索引通常使用B樹(shù)或B+樹(shù)這樣的樹(shù)形結(jié)構(gòu)來(lái)實(shí)現(xiàn)。樹(shù)的節(jié)點(diǎn)包含關(guān)鍵字和指向其他節(jié)點(diǎn)的指針，可以快速地搜索和訪問(wèn)數(shù)據(jù)庫(kù)中的數(shù)據(jù)。
3.解析樹(shù)：編譯器常使用樹(shù)形結(jié)構(gòu)來(lái)表示程序的語(yǔ)法結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)代表一個(gè)語(yǔ)法規(guī)則或語(yǔ)句，子節(jié)點(diǎn)表示該語(yǔ)句的組成部分，這種結(jié)構(gòu)可以方便地進(jìn)行語(yǔ)法分析和代碼生成。

注:這只是樹(shù)形結(jié)構(gòu)在實(shí)際中的一部分應(yīng)用，它的靈活性和易于理解性使其成為許多領(lǐng)域中常用的數(shù)據(jù)結(jié)構(gòu)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-704586.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】樹(shù)的基礎(chǔ)入門的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！