可以做皮膚測(cè)試的網(wǎng)站關(guān)鍵詞排名優(yōu)化如何
目錄
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)呢。?