# 二元樹 (Binary tree)

## 二元樹的遍歷方式

二元樹的遍歷方式主要有四種，而遍歷型式又分別分為兩種，一種是 **DFS(深度優先搜索)**，另一種是 **BFS(廣度優先搜索)**。

### DFS 深度優先搜索

1. 前序遍歷 Preorder traversal

前序遍歷的順序是 **middle -> left -> right**

2. 中序遍歷 Inorder traversal
中序遍歷的順序是 **left -> middle -> right**

如果遍歷的是二元搜索樹 Binary search tree，因為其特性，所以使用中序遍歷的時候，遍歷出來的結果會是升序排列的。

3. 後序遍歷 Postorder traversal

後序遍歷的順序是 **left -> right -> middle**

三種 DFS 遍歷都是使用 **棧** (stack)，來進行節點保存。

### BFS 廣度優先搜索

1. 層序遍歷

層序遍歷的順序是一層一層遍歷，主要使用 queue 來紀錄下一層的節點，每一輪從 queue拿一層節點出來遍歷，直到遍歷完成為止。

BFS 遍歷都是使用 **隊列** (queue)，來進行節點保存。

## 二元樹的類型

1. 二元樹

2. 二元搜索樹

二元搜索樹必須符合以下特性:

(1)**左子節點**必然比**根節點小**
(2)**右子節點**必然比**根節點大**

3. 高度平衡二元搜尋樹 (AVL tree)

高度平衡樹，就是調整**二元搜尋樹**的左右子樹的高度，來達到二元樹的平衡，因此，我們將AVL Tree又稱為**高度平衡二元搜尋樹**。

基本上，AVL樹必須要合乎下列兩個條件:

(1) 是一種二元搜尋樹。
(2) 高度須保持平衡狀態。

待補...

## 二元樹技巧

### 1. 使用二進制搜索二元樹中的節點

#### 使用二進位定位節點路徑

使用二進位的特性 例如 12 = 1100

故從根節點開始遍歷的路徑為 1[100] => 右 -> 左 -> 左