??write in front??
??所屬專欄： 初階數(shù)據(jù)結(jié)構(gòu)
???博客主頁(yè)：睿睿的博客主頁(yè)
???代碼倉(cāng)庫(kù)：??VS2022_C語(yǔ)言倉(cāng)庫(kù)
??您的點(diǎn)贊、關(guān)注、收藏、評(píng)論，是對(duì)我最大的激勵(lì)和支持?。。?br>關(guān)注我，關(guān)注我，關(guān)注我，你們將會(huì)看到更多的優(yōu)質(zhì)內(nèi)容?。?/p>

前言

一.樹概念及結(jié)構(gòu)

1.樹的概念：

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

特點(diǎn)：

• 有一個(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，其中每一個(gè)集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼
• 樹是遞歸定義的。
  
  

注意：
??樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)，對(duì)于N個(gè)節(jié)點(diǎn)都有N-1條邊與之對(duì)應(yīng)，

2 樹的相關(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)； 如上圖：B、C、H、I…等節(jié)點(diǎn)為葉節(jié)點(diǎn)
• 非終端節(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)：若一個(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)； 如上圖：B、C是兄弟節(jié)點(diǎn)
• 樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度； 如上圖：樹的度為6
  節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
• 樹的高度或深度：樹中節(jié)點(diǎn)的最大層次； 如上圖：樹的高度為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)的祖先
• 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫
• 森林：由m（m>0）棵互不相交的樹的集合稱為森林；

3.樹的表示

樹結(jié)構(gòu)要存儲(chǔ)表示起來(lái)就比較麻煩了，既然保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系，實(shí)際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法：

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一個(gè)孩子結(jié)點(diǎn)
 struct Node* _pNextBrother; // 指向其下一個(gè)兄弟結(jié)點(diǎn)
 DataType _data; // 結(jié)點(diǎn)中的數(shù)據(jù)域
};

在這里就是通過第一個(gè)孩子，這個(gè)孩子的兄弟關(guān)系來(lái)存儲(chǔ)相應(yīng)的關(guān)系，圖解如下：

4 樹在實(shí)際中的運(yùn)用（表示文件系統(tǒng)的目錄樹結(jié)構(gòu)）

二.二叉樹概念及結(jié)構(gòu)

1.概念：

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

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

從上圖可以看出：

1. 二叉樹不存在度大于2的結(jié)點(diǎn)
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

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

我們可以看看現(xiàn)實(shí)里的二叉樹：

2.特殊的二叉樹：

滿二叉樹：

??一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說(shuō)，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是 ，則它就是滿二叉樹。

完全二叉樹：

完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來(lái)的。對(duì)于n層二叉樹，只要前n-1層是滿的 ，最后一層要求從左到右是連續(xù)的，那么這就是一顆完全二叉樹！ 要注意的是滿二叉樹是一種特殊的完全二叉樹。

3.二叉樹的性質(zhì)：

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

• 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的滿二叉樹的最大結(jié)點(diǎn)數(shù)是 2^(h)-1個(gè)結(jié)點(diǎn)（等比數(shù)列求和）.
• 高度為h的完全二叉樹，節(jié)點(diǎn)數(shù)量的范圍是[2^(h-1), 2^h-1].
• 對(duì)任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為n0 , 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為n2 ,則有 n0=n2+1.
• 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h= log2(n+1). (ps： 是log以2為底，n+1為對(duì)數(shù))
• 完全二叉樹里度為1的節(jié)點(diǎn)只有1個(gè)或0個(gè)。

三.相關(guān)練習(xí)題：

例1：

答案：B

解析：根據(jù)n0=n2+1

例2：

答案：A

例3：

答案：B

例3：

答案：B
解析：有的同學(xué)可能會(huì)問為什么不直接用767-512，這樣算出來(lái)的結(jié)點(diǎn)是最后一層的結(jié)點(diǎn)數(shù)，并不是葉子結(jié)點(diǎn)（第n-1層也有葉子結(jié)點(diǎn)），所以我們不能這樣算。
正確方法：

總結(jié)

??更新不易，辛苦各位小伙伴們動(dòng)動(dòng)小手，??三連走一走???? ~ ~ ~ 你們真的對(duì)我很重要！最后，本文仍有許多不足之處，歡迎各位認(rèn)真讀完文章的小伙伴們隨時(shí)私信交流、批評(píng)指正！

專欄訂閱：
每日一題
c語(yǔ)言學(xué)習(xí)
算法
智力題
初階數(shù)據(jù)結(jié)構(gòu)
更新不易，辛苦各位小伙伴們動(dòng)動(dòng)小手，??三連走一走???? ~ ~ ~ 你們真的對(duì)我很重要！最后，本文仍有許多不足之處，歡迎各位認(rèn)真讀完文章的小伙伴們隨時(shí)私信交流、批評(píng)指正！

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-422119.html

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