---
# System prepended metadata

title: 二元樹 (Binary tree)

---

# 二元樹 (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] => 右 -> 左 -> 左

![](https://hackmd.io/_uploads/BJUOXKwqn.png)