# 介紹
## 特點
二叉樹： `最多只有兩個` 子節點的樹。度為2的數。
## 分類
二叉樹分為：
- 滿二叉樹
- 完全二叉樹
- 平衡二叉樹
- 二叉搜索樹
### 滿二叉樹
除了最后一層葉子結構之外，其他節點都有兩個子節點的樹。
### 完全二叉樹
除了最后缺的幾個節點不考慮之外，剩下的節點和一個滿二叉結構節點數完全相同。
### 平衡二叉樹
任一節點左右子節點的 `高度差` 小于等于 |1|。
節點高度：從這個節點到葉子節點最多的邊數。
### 二叉搜索樹（BST-Binary Search Tree）
規則：
1. 任意一個節點的左子節點都小于這個節點
2. 任意一個節點的右子節點都大于這個節點
## 存儲方式
二叉樹的存儲方式：
- 順序存儲（用數組）
- 鏈式存儲（用鏈表）
### 鏈式存儲
每個節點都有 左、右 兩個指針，指向左右兩個子節點。
節點類：
~~~
class Node {
construct(data) {
this.data = data // 數據
this.left = null // 左子節點
this.right = null // 右子節點
}
}
~~~
### 順序存儲
使用數組存儲二叉樹。
存儲完之后必須要滿公式：
情況一、（如果根節點保存在 0 這個下標時的公式）
第i個節點的左子節點下標：2i+1
第i個節點的右子節點下標：2i+2
第i個節點的父節點下標；Math.floor((i-1)/2)
情況二、根節點保存在1這個位置時：
順序存儲比較適合 `完全二叉樹`，否則會比較浪費空間（有很多空位）：
