??樹(shù)型結(jié)構(gòu)

?????什么是樹(shù)型結(jié)構(gòu)

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：

• 有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(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 <= i <=m) 又是一棵與樹(shù)類似的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼

• 樹(shù)是遞歸定義的

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

?????樹(shù)型結(jié)構(gòu)的概念

對(duì)于下面這樣一個(gè)樹(shù)型結(jié)構(gòu)，我們必須要明白如何描述它

結(jié)點(diǎn)的度 ：一個(gè)結(jié)點(diǎn)含有子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度； 如上圖：A的度為6

樹(shù)的度：一棵樹(shù)中，所有結(jié)點(diǎn)度的最大值稱為樹(shù)的度； 如上圖：樹(shù)的度為6

葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)； 如上圖：B、C、H、I…等節(jié)點(diǎn)為葉結(jié)點(diǎ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)含有的子樹(shù)的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)； 如上圖：B是A的孩子結(jié)點(diǎn)

根結(jié)點(diǎn)：一棵樹(shù)中，沒(méi)有雙親結(jié)點(diǎn)的結(jié)點(diǎn)；如上圖：A

結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子結(jié)點(diǎn)為第2層，以此類推

樹(shù)的高度或深度：樹(shù)中結(jié)點(diǎn)的最大層次； 如上圖：樹(shù)的高度為4

非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)； 如上圖：D、E、F、G…等節(jié)點(diǎn)為分支結(jié)點(diǎn)

兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)； 如上圖：B、C是兄弟結(jié)點(diǎn)

堂兄弟結(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)的祖先

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

森林：由m（m>=0）棵互不相交的樹(shù)組成的集合稱為森林

?????樹(shù)的表示形式

樹(shù)結(jié)構(gòu)相對(duì)線性表就比較復(fù)雜了，要存儲(chǔ)表示起來(lái)就比較麻煩了，實(shí)際中樹(shù)有很多種表示方式，如：雙親表示法，孩子表示法、孩子雙親表示法、孩子兄弟表示法等等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法

使用如下：

class Node {
	int value; // 樹(shù)中存儲(chǔ)的數(shù)據(jù)
	Node firstChild; // 第一個(gè)孩子引用
	Node nextBrother; // 下一個(gè)兄弟引用
}

圖解：

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

如我們?nèi)粘Ｉ罾锏奈募鎯?chǔ)。文件系統(tǒng)管理（目錄和文件）

??二叉樹(shù)

?????二叉樹(shù)的概念

一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合：

1. 或者為空

2. 或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。
   

從上圖可以看出：

1. 二叉樹(shù)不存在度大于2的結(jié)點(diǎn)

2. 二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒，因此二叉樹(shù)是有序樹(shù)

注意：對(duì)于任意的二叉樹(shù)都是由以下幾種情況復(fù)合而成的：

?????兩種特殊的二叉樹(shù)

1. 滿二叉樹(shù): 一棵二叉樹(shù)，如果每層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這棵二叉樹(shù)就是滿二叉樹(shù)。也就是說(shuō)，如果一棵二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是2^k-1 ，則它就是滿二叉樹(shù)。

2. 完全二叉樹(shù): 完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從0至n-1的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹(shù)。 要注意的是滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。

?????二叉樹(shù)的性質(zhì)

1. 若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹(shù)的第i層上最多有 (i>0)個(gè)結(jié)點(diǎn)

2. 若規(guī)定只有根結(jié)點(diǎn)的二叉樹(shù)的深度為1，則深度為K的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是 (k>=0)

3. 對(duì)任何一棵二叉樹(shù), 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0＝n2＋1

4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度k為
   
   注意：向上取整

5. 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上至下從左至右的順序?qū)λ泄?jié)點(diǎn)從0開(kāi)始編號(hào)，則對(duì)于序號(hào)為i的結(jié)點(diǎn)有：

若i>0，雙親序號(hào)：(i-1)/2；i=0，i為根結(jié)點(diǎn)編號(hào)，無(wú)雙親結(jié)點(diǎn)
若2i+1<n，左孩子序號(hào)：2i+1，否則無(wú)左孩子
若2i+2<n，右孩子序號(hào)：2i+2，否則無(wú)右孩子

?????二叉樹(shù)性質(zhì)練習(xí)

??練習(xí)一

1. 某二叉樹(shù)共有 399 個(gè)結(jié)點(diǎn)，其中有 199 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為（ ）
   A 不存在這樣的二叉樹(shù) B 200
   C 198 D 199

答案：B

??解析：

利用二叉樹(shù)性質(zhì)三：對(duì)任何一棵二叉樹(shù), 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0＝n2＋1

所以葉結(jié)點(diǎn) = 度為2的結(jié)點(diǎn) + 1；為200，選B

??練習(xí)二

2. 在具有 2n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，葉子結(jié)點(diǎn)個(gè)數(shù)為（ ）
   A n B n+1 C n-1 D n/2

答案：A

??解析：

2n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，二叉樹(shù)大概樣子為如下：

從上圖我們可以得出：

• 度為1的節(jié)點(diǎn)：1個(gè)

度為0與度為2節(jié)點(diǎn)的個(gè)數(shù)不知道，但是我們知道度為二的節(jié)點(diǎn)數(shù)等于度為0的結(jié)點(diǎn)數(shù)減一，我們?cè)O(shè)度為0的結(jié)點(diǎn)為x

則有以下公式：

2n = x + x -1 +1；
解得：x = n；

所以選擇A

??練習(xí)三

3. 一個(gè)具有767個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，其葉子節(jié)點(diǎn)個(gè)數(shù)為（）
   A 383 B 384 C 385 D 386

答案：B

??解析：

這題與上題同理，只不過(guò)結(jié)點(diǎn)數(shù)為奇數(shù)

• 此時(shí)度為1的節(jié)點(diǎn)：1個(gè)

度為0與度為2節(jié)點(diǎn)的個(gè)數(shù)不知道，但是我們知道度為二的節(jié)點(diǎn)數(shù)等于度為0的結(jié)點(diǎn)數(shù)減一，我們?cè)O(shè)度為0的結(jié)點(diǎn)為x

則有以下公式：

767 = x + x -1；
解得：x = 384；

??練習(xí)四

4. 一棵完全二叉樹(shù)的節(jié)點(diǎn)數(shù)為531個(gè)，那么這棵樹(shù)的高度為（ ）
   A 11 B 10 C 8 D 12

答案：B

??解析：

直接運(yùn)用性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度k為

注意：向上取整

所以答案為10，選B

?總結(jié)

關(guān)于《【數(shù)據(jù)結(jié)構(gòu)】樹(shù)與二叉樹(shù)》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評(píng)指正，如果文章對(duì)您有幫助或者覺(jué)得作者寫(xiě)的還不錯(cuò)可以點(diǎn)一下關(guān)注，點(diǎn)贊，收藏支持一下！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-679816.html

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