前言

今天要解釋的部分就是 Binary Tree 二元樹，也可以簡稱為 BT，這邊要特別注意一點，BT 與前一章節所提的 Tree 是不一樣的！

二元樹的定義

與 Tree 不同的點是，二元樹可以為空，然而樹卻不能為空，此外若二元樹非空，則擁有以下特性

1. 有 Root, Left subtree, right subtree
2. Left subtree, right subtree 也必須都為二元樹
   (註) 在二元樹左右是有差異的，在樹則沒有差異

二元樹的種類

由於二元樹長相非常多樣，可以先將二元樹歸類為下列幾類

1. Skewed BT
   分為左斜（只有左子點）跟右斜（只有右子點）
   若 K 個資料，則 K即高度
2. Complete BT
   令高度=k, 節點數=n 須滿足以下兩點
   
   node 增長方式為上至下，左至右增長
3. Full BT
   高度為 k 並擁有 個子點的 B.T
4. Strict BT
   每個 non-leaf 節點必須都有兩個 child

二元樹的三個定理

根據 Complete BT 以及 Full BT 的長相，可以發現它的高度為最小樹高，而 Skewed BT 的高度為最大樹高

1. 若給予 n 個葉節點，將其想像成 Full BT，且高度為 i 可以得出
   此式，在雙方取 log 即可得最小樹高 i
2. 若給予 n 個節點總數，且高度為 i 可以得出
   在雙方取 log 即可得最小樹高 i
3. 
   可以由節點總數 = Degree-0 Nodes + Degree-1 Nodes + Degree-2 Nodes 所組成，也等同於 B(有效連結)+1
   
   只要做移向便可以得到此定理的式子！