引言
現(xiàn)在是北京時間的2023年6月7號15點28分，剛考完了一課期末考試，回到宿舍就立馬準備發(fā)布這篇博客。距離完成本周復習指標還差兩篇博客。加油！
1.樹的概念
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。樹大致可以分成兩個部分構(gòu)成，即根和子樹。根節(jié)點就是樹最特殊的節(jié)點，它沒有前驅(qū)結(jié)點。除根節(jié)點外，其余結(jié)點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點有且只有一個前驅(qū)，可以有0個或多個后繼。因此樹是可以遞歸定義的。
注意： 子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)，就變成圖形結(jié)構(gòu)了。
1.1.樹的其他相關(guān)概念
節(jié)點的度： 個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度； 如上圖：A的為6
葉節(jié)點或終端節(jié)點： 度為0的節(jié)點稱為葉節(jié)點； 如上圖：B、C、H、I…等節(jié)點為葉節(jié)點
非終端節(jié)點或分支節(jié)點： 度不為0的節(jié)點； 如上圖：D、E、F、G…等節(jié)點為分支節(jié)點
雙親節(jié)點或父節(jié)點（重要）： 若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點； 如上圖：A是B的父節(jié)點
孩子節(jié)點或子節(jié)點（重要）： 一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點； 如上圖：B是A的孩子節(jié)點
兄弟節(jié)點： 具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點； 如上圖：B、C是兄弟節(jié)點
樹的度： 一棵樹中，最大的節(jié)點的度稱為樹的度； 如上圖：樹的度為6。大家常聽見的二叉樹也就是度為2的樹
節(jié)點的層次： 從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；
樹的高度或深度（重要）： 樹中節(jié)點的最大層次； 如上圖：樹的高度為4
堂兄弟節(jié)點： 雙親在同一層的節(jié)點互為堂兄弟；如上圖：H、I互為兄弟節(jié)點
節(jié)點的祖先（了解）： 從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；如上圖：A是所有節(jié)點的祖先
子孫（了解）： 以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。如上圖：所有節(jié)點都是A的子孫
森林： 由m（m>0）棵互不相交的樹的集合稱為森林；比如并查集這種數(shù)據(jù)結(jié)構(gòu)就是由森林構(gòu)成。
2.樹的代碼實現(xiàn)的結(jié)構(gòu)
前面已經(jīng)介紹了樹的基本概念，下面我們來看看樹要怎么用代碼來實現(xiàn)呢？
//這樣結(jié)構(gòu)定義樹可以嗎？
struct TreeNode
{
struct TreeNode* child1;
struct TreeNode* child2;
struct TreeNode* child3;
//...
int data;
};
答案是不行的，因為它沒有用樹的度來明確規(guī)定最多應該定義幾個孩子。所以這樣的結(jié)構(gòu)是錯誤的。下面我在給大家看一個結(jié)構(gòu)。假設樹的度為N，且看下面的代碼。
#define N 5
//假設N為5
struct TreeNode
{
struct TreeNode* ChildrenArr[N];
int data;
};
下面介紹一種很牛的表示結(jié)構(gòu)，左兄弟右孩子表示法。即用該樹結(jié)點只有兩個指向，分別指向第一個孩子和下一個兄弟結(jié)點。這種表示法可以構(gòu)造出所有的樹形結(jié)構(gòu)。
typedef int DataType;
struct TreeNode
{
struct TreeNode* _firstChild1; // 第一個孩子結(jié)點
struct TreeNode* _pNextBrother; // 指向其下一個兄弟結(jié)點
DataType _data; // 結(jié)點中的數(shù)據(jù)域
};
這種表示方法可以節(jié)省存儲空間，同時也提高了樹形結(jié)構(gòu)的遍歷效率，因為可以直接定位到每個節(jié)點的左孩子和右兄弟。
2.1.樹形結(jié)構(gòu)的應用
通常操作系統(tǒng)的磁盤文件結(jié)構(gòu)就是一個經(jīng)典的樹形結(jié)構(gòu)。這里我以Linux系統(tǒng)為例。
為什么要用樹形的結(jié)構(gòu)來當磁盤文件的系統(tǒng)呢?Linux系統(tǒng)的磁盤文件結(jié)構(gòu)采用樹形結(jié)構(gòu)，為用戶提供了清晰、簡單、方便、高效的文件管理方式。
3.二叉樹的概念
二叉樹其實就是度為二的樹。通常有以下幾種情況構(gòu)成。
二叉樹度為0的結(jié)點永遠比度為2的多一個。下面我就簡單舉兩個簡單場景來驗證這一結(jié)論。
3.1.特殊二叉樹的概念
3.1.1.完全二叉樹
對于一棵深度為k的二叉樹，若它的所有節(jié)點都在第1到第k層，且所有葉子結(jié)點都在第k層或者第k-1層且在第k層的順序必須從左到右連續(xù)，那么這棵二叉樹就是一棵完全二叉樹。滿二叉樹是特殊的完全二叉樹。
那么高度為h的完全二叉樹要怎么求出結(jié)點個數(shù)范圍呢？
同理反推可得，完全二叉樹的高度范圍log以2為底的（Sn）的對數(shù)+1 或者 log以二為底的（Sn+1）的對數(shù)。
3.1.2.滿二叉樹
一個二叉樹，如果每一個層的結(jié)點數(shù)都達到最大值，則這個二叉樹就是滿二叉樹。也就是
說，如果一個二叉樹的層數(shù)為h，且結(jié)點總數(shù)是2的h次方-1，則它就是滿二叉樹。
為什么滿二叉樹的結(jié)點總數(shù)是2的h次方－1呢？下面且看我的分析。
可以看到其實滿二叉樹的總結(jié)點是一個等差公式，當然其實直接記結(jié)論是滿二叉樹的總結(jié)點個數(shù)為2的h次方-1就好。同理反推可得滿二叉樹的高度等于 h = log以二為底的（Sn+1）的對數(shù)。
3.2.二叉樹試題講解
3.2.1.試題一
本題主要考核的是對于二叉樹的基本性質(zhì)的了解，即二叉樹中度為0的結(jié)點個數(shù)永遠比度為2的結(jié)點個數(shù)多一個，本題選B。
3.2.2.試題二
本題其實關(guān)鍵為完全二叉樹。這里就得根據(jù)完全二叉樹度為1 的結(jié)點只有可能是1個或者0個，再根據(jù)這一條件在加上二叉樹度為0永遠比度為2的多一個結(jié)點?？梢酝茢喑龆葹?的結(jié)點為1個，即葉子結(jié)點n0=2n / 2 = n。本題選A。
3.2.3.試題三
本題依舊是考驗對完全二叉樹概念的了解的。首先我們需要知道完全二叉樹的結(jié)點為：Sn=n0+n0-1+n1。根據(jù)Sn=767，又因為n0和n1必須是整數(shù)，所以n1 = 0。故2n0 = 768，n0等于384。本題選B。
4.二叉樹的存儲結(jié)構(gòu)
二叉樹的存儲結(jié)構(gòu)分為兩種，鏈式結(jié)構(gòu)二叉樹和順序結(jié)構(gòu)二叉樹。其底層實現(xiàn)對應的是鏈表和順序表。
4.1.順序結(jié)構(gòu)存儲
順序結(jié)構(gòu)二叉樹其實就是用數(shù)組來進行對數(shù)據(jù)的管理。一般只適合完全二叉樹使用，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，關(guān)于堆后面我會專門講解。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。
用數(shù)組的方式存儲二叉樹是帶有局限性性的，因為只適合完全二叉樹的存儲。
4.2.鏈式結(jié)構(gòu)存儲
二叉樹的鏈式存儲結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址 。鏈式結(jié)構(gòu)又分為二叉鏈和三叉鏈，當前學習的是二叉鏈，大名鼎鼎的紅黑樹用到的就是三叉鏈。文章來源：http://www.zghlxwxcb.cn/news/detail-475084.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-475084.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——樹的概念、二叉樹的概念的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
