個(gè)人主頁：平行線也會(huì)相交
歡迎 點(diǎn)贊?? 收藏? 留言? 加關(guān)注??本文由 平行線也會(huì)相交 原創(chuàng)
收錄于專欄【數(shù)據(jù)結(jié)構(gòu)初階（C實(shí)現(xiàn)）】
今天的內(nèi)容可是一個(gè)大頭，比以往學(xué)的內(nèi)容上了一個(gè)檔次。大家對(duì)于這塊內(nèi)容一定要好好學(xué)，不是很理解的地方一定要及時(shí)解決，要不然到了后面的內(nèi)容只會(huì)更加的痛苦。不過大家只要堅(jiān)持學(xué)習(xí)的話，沒有什么問題是我們解決不了的。大家一起加油啦！??！
樹的概念及結(jié)構(gòu)
樹的概念
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合，之所以叫做樹是因?yàn)樗雌饋砭拖褚活w倒著掛的樹，只不過這棵樹是根朝上，葉朝下的。
- 有一個(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)。
樹的基本概念
接下來：以上圖為例子來解釋樹的基本概念。
結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度；A結(jié)點(diǎn)的度為3。
葉結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)（或終端結(jié)點(diǎn)），簡(jiǎn)單來說就是沒有孩子的結(jié)點(diǎn)就是葉結(jié)點(diǎn)；E、K、L、M結(jié)點(diǎn)稱為葉結(jié)點(diǎn)。
非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：該結(jié)點(diǎn)指度不為0的結(jié)點(diǎn)；如B、F、C、D、J。注意：A結(jié)點(diǎn)也可以是分支結(jié)點(diǎn)。
雙親結(jié)點(diǎn)或父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則該結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)；如A是B、C、D結(jié)點(diǎn)的父結(jié)點(diǎn)。
孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)；如B、C、D結(jié)點(diǎn)是A結(jié)點(diǎn)的子結(jié)點(diǎn)。
這里也要注意一點(diǎn)，有的地方也會(huì)把**F、J**稱為是A結(jié)點(diǎn)的子結(jié)點(diǎn)，其實(shí)可以這么說但是不嚴(yán)謹(jǐn)，我們正常情況下還是會(huì)默認(rèn)把F、J稱為是子孫結(jié)點(diǎn)。
兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)，注意這里是指親兄弟，堂兄弟表兄弟都不算數(shù)；如H、I、G可以互稱為D結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。
樹的度：一棵樹中，最大的結(jié)點(diǎn)的度稱為樹的度；上圖樹的度為3。
結(jié)點(diǎn)的層次：從根開始定義起，根稱為第一層，根的子結(jié)點(diǎn)稱為第二層。
樹的高度或深度：樹中結(jié)點(diǎn)的最大層次；上圖的樹的高度為4。也有的地方收到數(shù)組的影響，從0開始計(jì)數(shù)，即樹的高度是3，但還是建議按照第一種方式來計(jì)樹的高度。假如說我們按照第二種方式，如果只有1個(gè)結(jié)點(diǎn)的話我們可以說樹的高度是0，但是如果是空樹的情況呢？空樹只能是-1了，這樣其實(shí)也可以，但是非常別扭。所以建議用第一種方式來計(jì)算樹的高度。
堂兄弟結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)會(huì)稱為堂兄弟；如
結(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結(jié)點(diǎn)的子孫。
森林：有m（m>0）棵互不相交的樹的集合稱為森林。
小總結(jié)：任何一棵樹都是由根和子樹組成的。而子樹又是由根和子樹組成的，子樹又是由根和子樹組成的，所以我們說樹是遞歸定義的，結(jié)束的標(biāo)標(biāo)志就是葉結(jié)點(diǎn)，即沒有子樹就遞歸結(jié)束。而二叉樹是一種特殊的樹，只能有兩棵子樹。
這棵樹就是由根A和三棵子樹組成的。
下面是樹的一些特點(diǎn)：
- 子樹是不相交的；
- 除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)父結(jié)點(diǎn)；
- 一棵N個(gè)結(jié)點(diǎn)的樹由N-1條邊。
樹的結(jié)構(gòu)
樹結(jié)構(gòu)非常復(fù)雜，表示起來也是復(fù)雜一些。我們既要保存值域，也要保存各個(gè)結(jié)點(diǎn)之間的關(guān)系。樹的表示方法有很多種：雙親表示法、孩子表示法、雙親孩子表示法以及孩子兄弟表示法等。
現(xiàn)在，我們來看看最常用的孩子表示法。
typedef int DataType;
struct TreeNode
{
struct TreeNode* firstChile1;//第一個(gè)孩子結(jié)點(diǎn)
struct TreeNode* pNextBrother;//指向下一個(gè)兄弟結(jié)點(diǎn)
DataType data;//結(jié)點(diǎn)種的數(shù)據(jù)域
};
這種表示方法也叫左孩子右兄弟表示法。
我們還是以下面這張圖為例：
我們現(xiàn)在就用孩子表示法來表示該圖，請(qǐng)看：
這種左孩子有兄弟表示法能夠很好的表示這個(gè)樹形結(jié)構(gòu)。但是在實(shí)際當(dāng)中用途不大，樹在實(shí)際當(dāng)中的應(yīng)用場(chǎng)景就比如文件系統(tǒng)；在數(shù)據(jù)結(jié)構(gòu)中，最常用的還是二叉樹。
二叉樹概念及結(jié)構(gòu)
概念
一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合：要么為空；要么就是由一個(gè)根結(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成的。
二叉樹特點(diǎn)：
1.二叉樹不存在度度大于2的結(jié)點(diǎn)。
2.二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。
這里需要注意的是：對(duì)于任意的二叉樹都是由一下幾種情況復(fù)合而成的。
特殊的二叉樹
特殊的二叉樹總共有兩種：滿二叉樹和完全二叉樹。
滿二叉樹：一個(gè)二叉樹中如果每一個(gè)層的結(jié)點(diǎn)都達(dá)到最大值，則這個(gè)數(shù)就是滿二叉樹。如果我們?cè)O(shè)一個(gè)二叉樹的層數(shù)為k，且總結(jié)點(diǎn)數(shù)是2的k次方-1，那么這個(gè)樹就是滿二叉樹。
完全二叉樹：完全二叉樹是由滿二叉樹引出來的。對(duì)于深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹種編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。
簡(jiǎn)單來說，滿二叉樹就是除了最后一層之外，其余每層的結(jié)點(diǎn)都只有兩個(gè)子結(jié)點(diǎn)。
滿二叉樹是也是完全二叉樹，但是完全二叉樹不一定就是滿二叉樹。類似于長(zhǎng)方形與正方形的關(guān)系。
二叉樹結(jié)論
1.對(duì)于任何一棵二叉樹（樹為非空），如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的分支結(jié)點(diǎn)個(gè)數(shù)為n2，則有n0=n2+1。簡(jiǎn)單來說就是度為0的永遠(yuǎn)比度為2的多一個(gè)。
舉個(gè)例子：某二叉樹共有399個(gè)結(jié)點(diǎn)，其中199個(gè)度為2的結(jié)點(diǎn)，則該二叉樹種的葉子結(jié)點(diǎn)（就是度為0的結(jié)點(diǎn)）為200個(gè)。
2.二叉樹中度為1的要么只有1個(gè)，要么就是沒有（滿二叉樹中度只有度為0和度為2的，沒有度為1的；而完全二叉樹中度為1的要么有1個(gè)要么就是沒有）。
例題：在具有2n個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為（）？
由這個(gè)題我們就可以得出一個(gè)結(jié)論：在具有2n個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為n。
再來看一個(gè)題：
一個(gè)具有767個(gè)結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)個(gè)數(shù)為？
二叉樹的存儲(chǔ)結(jié)構(gòu)
二叉樹一般分為兩種結(jié)構(gòu)存儲(chǔ)，分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。
順序存儲(chǔ)
順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來存儲(chǔ)，一般使用數(shù)組只適合完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空間的浪費(fèi)。而現(xiàn)實(shí)中只有堆才會(huì)使用數(shù)組來存儲(chǔ)。所以，二叉樹順序存儲(chǔ)在物理上其實(shí)就是一個(gè)數(shù)組，在邏輯上就是我們想象出來的一棵樹。
現(xiàn)在我們來看一下二叉樹順序存儲(chǔ)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。
二叉樹順序存儲(chǔ)的邏輯結(jié)構(gòu)（邏輯結(jié)構(gòu)是我們自己想象出來的）就是一棵樹；
物理結(jié)構(gòu)就是一個(gè)數(shù)組。
如果我們知道孩子結(jié)點(diǎn)的下標(biāo)，如何推算父結(jié)點(diǎn)的下標(biāo)呢？
比如：下標(biāo)為5和6的結(jié)點(diǎn)，它們的父結(jié)點(diǎn)是下標(biāo)為2的結(jié)點(diǎn)。這里就直接說結(jié)論吧，知道子節(jié)點(diǎn)來求父結(jié)點(diǎn)，二者之間的關(guān)系就是parent=（chile-1）/2。
如果我們知道父結(jié)點(diǎn)的下邊如何推算子節(jié)點(diǎn)的下標(biāo)呢？
比如：下標(biāo)為1的結(jié)點(diǎn)是下標(biāo)為3和4結(jié)點(diǎn)的父結(jié)點(diǎn)。知道父結(jié)點(diǎn)想要求子節(jié)點(diǎn)的話，此時(shí)二者之間就是leftchild=parent*2+1；rightchild=parent*2+2。
以上就表示二叉樹的值在數(shù)組位置中父子下標(biāo)關(guān)系。注意，這里規(guī)定的是下標(biāo)必須是從0開始的，否則關(guān)系就亂套了。
二叉樹的順序存儲(chǔ)適合滿二叉樹或者完全二叉樹，如果不是滿二叉樹或者完全二叉樹的話就很有可能造成空間浪費(fèi)。就比如說下面這棵樹就不適合用二叉樹的順序結(jié)構(gòu)來存儲(chǔ)。
上圖這棵樹如果非要用二叉樹的順序結(jié)構(gòu)來存儲(chǔ)的話就會(huì)造成空間浪費(fèi)。
所以，二叉樹的順序存儲(chǔ)適合完全二叉樹（滿二叉樹是一種特殊的完全二叉樹）。
鏈?zhǔn)酱鎯?chǔ)
二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈表來指示元素的邏輯關(guān)系。通常的方法是鏈表中的每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針域分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。鏈?zhǔn)酱鎯?chǔ)又分為二叉鏈和三叉鏈，這里我們先來學(xué)習(xí)二叉鏈，一般紅黑樹會(huì)用到三叉鏈。
下面是二叉樹和三叉樹的結(jié)構(gòu)：
typedef int STDataType;
//二叉樹
struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
STDataType data;
};
//三叉樹
struct TreeNode
{
struct TreeNode* parent;
struct TreeNode* left;
struct TreeNode* right;
STDataType data;
};
二叉樹的順序結(jié)構(gòu)
在這之前，我們之前的數(shù)據(jù)結(jié)構(gòu)，無論是順序表、鏈表、還是棧和隊(duì)列那里，都只是單純的的存儲(chǔ)數(shù)據(jù)。而現(xiàn)在這里，我們可以通過二叉樹這個(gè)數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)一些其它的價(jià)值，就比如說排序…
普通的二叉樹不適合用數(shù)組來存儲(chǔ)，因?yàn)榭赡軙?huì)有大量的空間浪費(fèi)。而完全二叉樹很適合使用順序結(jié)構(gòu)來存儲(chǔ)。現(xiàn)實(shí)中我們通常把堆（一種二叉樹）使用順序結(jié)構(gòu)的數(shù)組來存儲(chǔ)，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個(gè)是數(shù)據(jù)結(jié)構(gòu)，一個(gè)是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
堆的概念及結(jié)構(gòu)
堆的數(shù)據(jù)結(jié)構(gòu)是完全二叉樹或一堆數(shù)組，因?yàn)槎言谶壿嬌鲜且豢猛耆鏄洌谖锢斫Y(jié)構(gòu)上是一個(gè)一維數(shù)組。
堆的性質(zhì)文章來源：http://www.zghlxwxcb.cn/news/detail-409806.html
- 堆的某個(gè)結(jié)點(diǎn)總是不大于或者不小于其父結(jié)點(diǎn)的值；
- 堆總是一棵完全二叉樹
小根堆：樹中所有的父結(jié)點(diǎn)都小于或等于自己的孩子結(jié)點(diǎn)。
大根堆：樹中所有的父結(jié)點(diǎn)都大于或等于自己的孩子結(jié)點(diǎn)。文章來源地址http://www.zghlxwxcb.cn/news/detail-409806.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)入門】-二叉樹的基本概念的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
