樹是一個程序中算是很難的知識點了，up在這里講解一下，希望能幫助大家（打字辛苦，點一個免費的贊吧）

認識樹結構

樹結構呢有很像下面的圖片一樣，由主干到分支

接下來我們在了解一下樹

結點就是樹中的每一個元素：1,2,3,4,5,6,7,8

根節(jié)點就是整棵樹的起始結點：1

子樹可以看成整棵樹中的小樹，比如2,5,6就是整棵樹的小樹即子樹

?

然后呢我們在認識一下樹的概念。

比如在整棵樹中1是根節(jié)點，而2,5,6這個小樹的根節(jié)點則是2.

度：1.比如1的度為3，即2,3,4。? ? 再比如2的度為2，即5,6。? ? ??

? ? ? ?2.像5,6,3,8這種沒有度的結點，我們稱之為葉結點。? ? ?

? ? ? ?3.那這個數(shù)的度為多少？我們依照第3點可以看出，這棵樹結點最多的是1，有3個度，所以這棵樹的度就為3。

深度：這個就很好理解了，從上往下數(shù)，分別有125 (3),126 (3)，13 (2),1478 (4)，而1478的層次是最多的，所以這棵樹的深度就是4

學到這里，你已經(jīng)掌握了關于樹的基本結構。加油，繼續(xù)看下去

接下來是重點內容——二叉樹

二叉樹即BT樹，額，還真就很形象呢

空二叉樹：沒有任何結點

上面的內容還是比較簡單的，現(xiàn)在我們再來看看二叉樹的特點

我們來驗證一下

第一行：結點數(shù)=2^(1-1)=2^0=1

第二行：結點數(shù)=2^(2-1)=2^1=2

第三行：結點數(shù)=2^(3-1)=2^2=4

第四行：結點數(shù)=2^(4-1)=2^3=8

。。。

綜上所述在二叉樹的第i層最多有2^(i-1)

所以我們的結果是對的

我們再來看看第二個特點（公式）

老樣子，沒有驗證怎么可以直接說出來呢？

深度為k這里我們來看一下以下4種情況：

1.當k=1時：節(jié)點個數(shù)=2^1-1=1

2.當k=2時：節(jié)點個數(shù)=2^2-1=3

3.當k=3時：節(jié)點個數(shù)=2^3-1=7

4.當k=4時：節(jié)點個數(shù)=2^4-1=15

這里我們也是可以得出這個結論是正確的的：

即深度為k的二叉樹至多有2^k-1個節(jié)點

最后我們再來看二叉樹的第3個特點：

即：

所以以上3個特點有兩個公式需要記憶：

1.在二叉樹的第i層最多有2^(i-1)

2.深度為k的二叉樹至多有2^k-1個節(jié)點

然后我們也要認識滿二叉樹，懂得滿二叉樹的運用及判斷。

沒想到吧，又學完一個知識點了最后我們來學習

完全二叉樹

接著上面，我們再來看二叉樹的第4個特點——完全二叉樹

像下面這些也屬于完全二叉樹：

也就是說除最后一層以外的，這棵樹必須是滿二叉樹。

就像上面的圖一樣除8,9,10,11,12||8,9,10,11,12,13||8,9,10,11以外都是滿二叉樹，對不對？

那最后一句話“在最后一層上只缺少右邊的若干結點”是什么意思呢？

我們來看看錯誤完全二叉樹的示例吧！

圖一錯誤點：根據(jù)我們完全二叉樹的定義除最后一層外,每一層上的結點數(shù)均達到最大值可以? ? 判斷這是錯的（除6,7以外，3下面沒有子節(jié)點應該是錯的）正確來說應該在3下面多加一個左孩子和一個右孩子。

圖二錯誤點：雖然它第一個條件滿足了，但是第二個條件在最后一層上只缺少右邊的若干結點卻沒有滿足，那個6不應該出現(xiàn)在右邊的，如果6是3的左孩子的話，那就對了。

總結：

完全二叉樹應該滿足以下兩個特征：

1.除最后一層外，每一層上的結點數(shù)均達到最大值。

2.在最后一層上只缺少右邊的若干結點。

接下來我們來練習一下吧

練一練

第一題

思考一下。

答案是?A

你答對了嗎？

解答：套公式！深度為k的二叉樹至多有2^k-1個節(jié)點

所以答案為：2^5-1=31，所以答案是A

第二題

思考一下

答案選B

你答對了嗎？

解答：老樣子套公式！誰的2次方-1最接近61？6！

2^6-1=61所以答案為6！

尾聲：

二叉樹的基本知識你已經(jīng)掌握的差不多了

up會持續(xù)更新關于二叉樹的知識，大家記得關注哦

再見了！

感謝觀看