🌟🌟hello，各位讀者大大們你們好呀🌟🌟
🚀🚀系列專欄：【數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)】
📝📝本篇內(nèi)容：樹的概念；樹的相關(guān)概念；樹的表示；樹在實(shí)際中的運(yùn)用；二叉樹概念及結(jié)構(gòu)；特殊二叉樹；二叉樹的性質(zhì)
????上一篇：Linux進(jìn)程概念（二）
💖💖作者簡介：軒情吖，請多多指教(> ????? ) ??-

1.樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點(diǎn)組成的一個有層次關(guān)系的集合
有一個特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)
除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M（M>0）個互不相交的集合，其中每一個集合又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根節(jié)點(diǎn)有且只有一個前驅(qū)，可以有0個或者多個后繼
任何一棵樹，分解為根和N棵子樹（N>=0）
因此樹是遞歸定義的
注意：
①樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)
②子樹是不相交的
③除了根結(jié)點(diǎn)外，每個結(jié)點(diǎn)有且只有一個父節(jié)點(diǎn)
④一棵N個結(jié)點(diǎn)的樹有N-1條邊

2.樹的相關(guān)概念

結(jié)點(diǎn)的度：一個結(jié)點(diǎn)含有的子樹個數(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)：若一個結(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)；如上圖：A是B的父結(jié)點(diǎn)
孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：一個結(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)的層次：從根開始定義起，根為第一層，根的子結(jié)點(diǎn)為第二層，以此類推
樹的高度或深度：樹中結(jié)點(diǎn)的最大層次；如上圖：樹的高度為4
堂兄弟結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)互為堂兄弟；如上圖：H、L互為堂兄弟結(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>0）棵互不相交的樹的集合稱為森林

3.樹的表示

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

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

4.樹在實(shí)際中的運(yùn)用

Linux樹狀目錄結(jié)構(gòu)

我們的windows的文件系統(tǒng)是樹林，它分為好幾棵樹，對應(yīng)C盤D盤等

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

一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合：
①為空
②由一個根節(jié)點(diǎn)加上兩棵別稱左子樹和右子樹組成

①二叉樹不存在度大于2的結(jié)點(diǎn)
②二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
③對于任何的二叉樹都是由以下幾種情況復(fù)合而成的：空樹、只有根節(jié)點(diǎn)、只有左子樹、只有右子樹、左子樹右子樹均存在

6.特殊的二叉樹

①滿二叉樹：一個二叉樹，如果每一層的結(jié)點(diǎn)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為k，且結(jié)點(diǎn)總數(shù)是2^k-1,則他就是滿二叉樹

上圖可以清晰地看出，每一層的結(jié)點(diǎn)數(shù)是2^（層數(shù)-1）個
第h層滿了，則k層有2^(h-1)個結(jié)點(diǎn)
現(xiàn)在我們就可以推出高度為k的滿二叉樹的總結(jié)點(diǎn)數(shù)為2^h-1
假設(shè)滿二叉樹有N個結(jié)點(diǎn)，高度為h=log(N+1)
②完全二叉樹：前N-1層是滿的，最后一層可以不滿，但是必須從左往右是連續(xù)的。要注意的是滿二叉樹是一種特殊的完全二叉樹

假設(shè)完全二叉樹的高度為h
最多結(jié)點(diǎn)：也就是滿二叉樹2^h-1個結(jié)點(diǎn)
最少結(jié)點(diǎn)：相等于最后一層的結(jié)點(diǎn)數(shù)為1個，因此結(jié)果為2^(h-1)

7.二叉樹的性質(zhì)

①若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^（i-1）個結(jié)點(diǎn)
②若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h-1個
③對于任何一棵二叉樹，如果度為0其葉結(jié)點(diǎn)個數(shù)為x，度為2的分支節(jié)點(diǎn)個數(shù)為y，則有y+1=x
④若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個結(jié)點(diǎn)的滿二叉樹的深度為h=log（n+1）
⑤對于具有n個結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左到右的數(shù)組順序?qū)λ薪Y(jié)點(diǎn)從0開始編號，則對于序號為i的結(jié)點(diǎn)有以下的特點(diǎn)：

若i>0,i位置結(jié)點(diǎn)的雙親序號：（i-1）/2=parent；i=0，i為根節(jié)點(diǎn)編號，無雙親結(jié)點(diǎn)
設(shè)n為數(shù)組的大小，若2i+1<n,左孩子序號：2i+1=leftchild；2i+1>=n否則無左孩子
設(shè)n為數(shù)組的大小，若2i+2<n,右孩子序號：2i+2=rightchild；2i+2>=n否則無右孩子

🌸🌸二叉樹（一）的知識大概就講到這里啦，博主后續(xù)會繼續(xù)更新更多數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識，干貨滿滿，如果覺得博主寫的還不錯的話，希望各位小伙伴不要吝嗇手中的三連哦！你們的支持是博主堅(jiān)持創(chuàng)作的動力！💪💪