樹是啥,現實中的樹嗎，是這個小王子里面的猴面包樹？？
又或者是北歐神話里面的世界樹
其實不是，在計算機中，樹是一種資料結構，他的邏輯結構呈現了一棵樹的狀態，如圖：
這個看著像北歐神話里面的世界樹根呀，對其實也可以看成樹的根，或是倒過來的樹
如圖：
在生活中樹的結構也無處不在,比如常用的思維導圖，家里的族譜，計算機的檔案系統……
樹
- 樹是一種非線性存盤的結構
- 且樹的節點個數是 ≥0 的, 等于0則為空樹
- 根有且只有一個
樹的概念
- 父節點
- 他含有兒子(含有子節點)
- 節點的度
- 有多少個兒子(該節點有多少個子節點)
- 葉節點or終端節點
- 孤寡老人(他沒有兒子，度為 0 )
- 兄弟節點
- 同一個爹生的就是（倆子節點都指向同一個父節點）
- 堂兄弟節點
- 同輩兄弟不是一個爹生的(同一層上面的節點，但不是同一個父節點)
- 祖先節點
- 就是根節點
- 樹的度
- 祖先有多少個兒子(祖先節點有多少個子節點)
- 樹的深度
- 家族到了第幾代了（有多少層）
- 子孫節點
- 除根節點以外的都是
- 森林
- 一棵樹叫樹，那么多棵樹那么就是森(且不相交)
圖解:
注：
這兒一個孩子 只有一個父親（不可以認別認做干爹），反之父親節點也不可以認干兒子，
既然樹是一種資料結構那么他是如何存盤的呢？
樹的存盤
樹是如何存盤的呢？他是非線性的如何存，上圖看著似乎不太好存，用順序表嗎？或者用鏈表嗎？單單用簡單的順序表與鏈表是無發體現出樹的邏輯結構畢竟之前順序表與鏈表似乎每個節點后面都只有一個，如果是單節點的樹(后面會說到)用順序表真的是完美，可是他有多個孩子咋辦
這里就有一種方法可以解決叫做雙親表示法
雙親表示法：
父節點只存他左邊的孩子的地址(第一個孩子)，然后左孩子指向他旁邊的兄弟節點，如此反復，如果沒有兄弟那么就指向空
圖解結構
左邊為邏輯結構 ，右邊為物理結構
雙親表示法的結構代碼
typedef int DataType
struct Node
{
struct Node*firstChild;//一層里面第一個孩子(左孩子)
struct Node*borther;//其他親兄弟節點
DataType data;//資料
}
二叉樹
樹里面有一種特殊的樹，二叉樹，是啥樣的呢？怎么理解吧，前面的樹是計劃生育前，你想要幾個孩子都可以，計劃生育后你最多只能有倆個孩子如圖：
上面看到其實不是每一個節點都是倆個(現實中一個孩子的也很多，家里獨寵)，其實以下情況也是二叉樹
二叉樹中里有倆特殊二叉樹
滿二叉樹 完全二叉樹
上圖對比可以得出完全二叉樹其實就是節點不是滿的，且完全二叉樹也是嚴格要求的，他的節點之間必須挨著存放的，錯誤與正確示范如圖：
二叉樹和樹一樣也有一些定義
- 節點個數的計算
2(H)-1 h為二叉樹的深度or高度
- 二叉樹個數就和卵細胞分裂類似但是差點,二叉樹第一層只有一個節點，而細胞分裂一次就是倆個所以公式是2H-1
如圖：
- 二叉樹的高度計算
log2(n+1)->這里的log是以二為底(一些書中會寫成lgN+1)，n為節點個數
這兒就和上面是差不多就是反過推就好了
- 葉子節點的計算
N0=N2+1,N0為葉子節點，而N2為度為2的節點，知道N0的節點也可以反推N2的節點個數
如圖：
- 完全二叉樹的最少/最多，有多少個節點
最少與最多的情況：
如圖：
由上面可以看出滿二叉樹其實也是完全二叉樹是最多的情況(公式如上)，那么最少的情況如何算呢： 2(H-2):
2(H-1) 就是從完全二叉樹那里推出來的，滿二叉樹公式2(H)-1,最少的情況比他少一層，所以高度減1，但他必須有一個節點所以要加回去2(h-1)+1-1 -->2(H-1)
- 第i層的節點個數：
2(i-1) 假設我們要求第一層的節點 2^(1-1)=1， 因為層數是從 1開始而節點個數的指數是從 0所以減一
切瓜環節
某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為( )
A 不存在這樣的二叉樹
B 200
C 198
D 199
在具有 2n 個結點的完全二叉樹中，葉子結點個數為( )
An
B n+1
C n-1
D n/2
一棵完全二叉樹的節點數位為531個，那么這棵樹的高度為( )
A 11
B 10
C8
D 12
一個具有767個節點的完全二叉樹，其葉子節點個數為()
A 383
B 384
C 385
D 386
- 第一題B，度為 2 的節點有199,求葉子節點，知道度為二的節點求葉子，套用公式猶如砍菜切瓜N0=N2+1
- 第二題A，這道推理題且要記住一個公式
N0+N2+N1=N（N0葉子,N2度為二的節點……）
圖解：
- 第三題B，求樹的高度還告訴了你節點個數，你說說這是啥，送分題呀，套公式log(N+1)–>log(531) 210=1024 29=512
- 第四題B，通過上面推導得出N0+N1+N2=N,且N1=節點奇數為0，偶數為1
- 2N0+N1=767 2N=767
學到這里對樹已經有一個基礎的認識了，可以算是下了一個新的副本的前幾層，顯然副本的難度并不是很高，這里算是暴風前的寧靜了，下一層就是boss就是（順序表二叉樹）：堆，下下層為究極boss（鏈式二叉樹），遞回，記得拾起裝備迎接后續的挑戰
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299982.html
標籤：其他