---
# System prepended metadata

title: Data Structure / Tree Structures
tags: [Data Structure]

---

# Data Structure / Tree Structures

## 1. 基本概念

### 1.1 介紹與定義

#### 樹狀結構是一種階層式的資料結構，可以以遞迴定義為：

1. 空結構是一棵空樹
2. 若 t₁, t₂, ..., tₖ 是不相交的樹，則具有根節點且其子節點為 t₁, t₂, ..., tₖ 的根節點的結構也是一棵樹（白話文：如果現在有幾棵不相關的樹，將它們連結在一起時，這棵新樹會產生一個根節點，下面依附著小樹們🌳）
3. 只有透過上述兩條規則產生的結構才是樹

#### 一棵樹具有以下特性：
- 有一個特別指定的節點稱為根節點（root）
- 其餘節點可分為 n ≥ 0 個互不相交的集合 t₁, t₂, ..., tₙ，每個集合本身都是一棵樹，稱為子樹（subtree）
- 移除根節點後，這些子樹構成一個森林 (Forest)。

#### 常見的樹型結構類型包括：

- 二元樹（Binary Tree）：每個節點最多有兩個子節點。
- 二元搜尋樹（Binary Search Tree, BST）：左子節點的值小於根，右子節點的值大於根。
- AVL樹、紅黑樹（Red-Black Tree）、B樹等。

---

有一天就讀資工系的喬治問珍妮，樹究竟是向下長還是向上，珍妮回答那要看是蘋果樹還是紅黑樹，那一刻喬治知道，~~他必須娶珍妮~~。

### 1.2 常用術語

中文翻譯還是需要一點時間反應，推薦直接看英文定義會比較準確耶一些。

1. **路徑（Path）**：從根節點到特定節點的唯一序列
2. **路徑長度（Length）**：路徑中邊的數量
3. **層級（Level）**：從根節點到某節點的路徑長度加 1
4. **高度（Height）**：樹中最大的層級數
5. **度數（Degree）**：節點的子節點數量
6. **關係術語**：
    - 父節點/子節點/兄弟節點（Parent/Child/Sibling）：樹中的親屬關係
    - 祖先/後代（Ancestor/Descendant）：節點在樹中的前輩或後輩
    - 終端節點（Terminal Node）：又稱葉節點（Leaf），無子節點的節點。
    - 非終端節點（Non-terminal Node）：又稱內部節點（Internal Node），具有子節點的節點。

## 2. 二元樹 Binary Tree

### 2.1 定義

二元樹可說是最常見的樹狀結構，其中每個節點最多有兩個子節點，並且明確區分為左子節點和右子節點。

### 2.2 二元樹的類型

1. **完滿二元樹（Full Binary Tree）**
   - 每個非葉節點都有兩個子節點
2. **完整二元樹（Complete Binary Tree）**
   - 除了最後一層外，其他層級都填滿節點
   - 最後一層的節點都靠左排列
3. **平衡二元樹（Balanced Binary Tree）**
   - 任何節點的左右子樹高度差不超過 1

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


### 2.3 基本實作

以下是二元樹節點的實作：

```java=
class TreeNode {
    protected int value;
    protected TreeNode left, right;
    
    public TreeNode() {
        left = right = null;
    }
    
    public TreeNode(int value) {
        this(value, null, null);
    }
    
    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
```

## 3. 二元樹的走訪

### 3.1 深度優先走訪（Depth-First Traversal）

1. **前序走訪（Preorder）**：根節點 → 左子樹 → 右子樹

```java=
protected void preorder(TreeNode p) {
    if (p != null) {
        System.out.print(p.value + " "); // 訪問節點
        preorder(p.left);                // 走訪左子樹
        preorder(p.right);               // 走訪右子樹
    }
}
```

2. **中序走訪（Inorder）**：左子樹 → 根節點 → 右子樹

```java=
protected void inorder(TreeNode p) {
    if (p != null) {
        inorder(p.left);                 // 走訪左子樹
        System.out.print(p.value + " "); // 訪問節點
        inorder(p.right);                // 走訪右子樹
    }
}
```

3. **後序走訪（Postorder）**：左子樹 → 右子樹 → 根節點

```java=
protected void postorder(TreeNode p) {
    if (p != null) {
        postorder(p.left);               // 走訪左子樹
        postorder(p.right);              // 走訪右子樹
        System.out.print(p.value + " "); // 訪問節點
    }
}
```

歡迎參考：[UVa 10858 - Unique Factorization](https://hackmd.io/H_Ky32_ZTPKKtsFdgMw1Gw?view#Depth-First-Search%EF%BC%88DFS%EF%BC%8C%E6%B7%B1%E5%BA%A6%E5%84%AA%E5%85%88%E6%90%9C%E5%B0%8B%EF%BC%89)

### 3.2 廣度優先走訪（Breadth-First Traversal）

也稱為層序走訪（Level-order traversal），會用到 [Queue](https://hackmd.io/@marvelcn015/SJLmec4xke) 實作：

```java=
public void breadthFirst() {
    if (root == null) return;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.value + " ");
        
        if (node.left != null)
            queue.offer(node.left);
        if (node.right != null)
            queue.offer(node.right);
    }
}
```

## 4. 二元搜尋樹 Binary Search Tree

### 4.1 定義

- 對於任何節點 n，其左子樹中的所有節點值都小於 n 的值
- 對於任何節點 n，其右子樹中的所有節點值都大於 n 的值

### 4.2 基本操作

1. **搜尋**

```java=
protected TreeNode search(TreeNode p, int target) {
    while (p != null) {
        if (target == p.value) return p;
        else if (target < p.value) p = p.left;
        else p = p.right;
    }
    return null;
}
```

2. **插入**

```java=
public void insert(int value) {
    TreeNode p = root;
    TreeNode prev = null;
    
    while (p != null) {
        prev = p;
        if (value < p.value) p = p.left;
        else p = p.right;
    }
    
    if (root == null)
        root = new TreeNode(value);
    else if (value < prev.value)
        prev.left = new TreeNode(value);
    else
        prev.right = new TreeNode(value);
}
```

3. **刪除**：分為三種情況
   - 刪除葉節點
   - 刪除具有一個子節點的節點
   - 刪除具有兩個子節點的節點

```java=
public void delete(int value) {
        root = deleteRec(root, value);
    }

    private TreeNode deleteRec(TreeNode root, int value) {
        if (root == null)
            return root;

        if (value < root.value)
            root.left = deleteRec(root.left, value);
        else if (value > root.value)
            root.right = deleteRec(root.right, value);
        else {
            // 節點只有一個子節點或沒有子節點的情況
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // 節點有兩個子節點的情況，找到右子樹的最小值替代被刪除的節點
            root.value = minValue(root.right);

            // 刪除右子樹中的最小值節點
            root.right = deleteRec(root.right, root.value);
        }

        return root;
```

## 5. 完整程式碼 Demo
```java=
import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    protected int value;
    protected TreeNode left, right;

    public TreeNode() {
        left = right = null;
    }		

    public TreeNode(int value) {
        this(value, null, null);
    }

    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

class BinaryTree {
    protected TreeNode root;

    // 深度優先走訪 - 前序
    protected void preorder(TreeNode p) {
        if (p != null) {
            System.out.print(p.value + " "); // 訪問節點
            preorder(p.left); // 走訪左子樹
            preorder(p.right); // 走訪右子樹
        }
    }

    // 深度優先走訪 - 中序
    protected void inorder(TreeNode p) {
        if (p != null) {
            inorder(p.left); // 走訪左子樹
            System.out.print(p.value + " "); // 訪問節點
            inorder(p.right); // 走訪右子樹
        }
    }

    // 深度優先走訪 - 後序
    protected void postorder(TreeNode p) {
        if (p != null) {
            postorder(p.left); // 走訪左子樹
            postorder(p.right); // 走訪右子樹
            System.out.print(p.value + " "); // 訪問節點
        }
    }

    // 廣度優先走訪
    public void breadthFirst() {
        if (root == null)
            return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.value + " ");

            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
    }
}

class BinarySearchTree extends BinaryTree {

    // 二分搜尋
    protected TreeNode search(TreeNode p, int target) {
        while (p != null) {
            if (target == p.value)
                return p;
            else if (target < p.value)
                p = p.left;
            else
                p = p.right;
        }
        return null;
    }

    // 插入
    public void insert(int value) {
        TreeNode p = root;
        TreeNode prev = null;

        while (p != null) {
            prev = p;
            if (value < p.value)
                p = p.left;
            else
                p = p.right;
        }

        if (root == null)
            root = new TreeNode(value);
        else if (value < prev.value)
            prev.left = new TreeNode(value);
        else
            prev.right = new TreeNode(value);
    }

    // 刪除節點
    public void delete(int value) {
        root = deleteRec(root, value);
    }

    private TreeNode deleteRec(TreeNode root, int value) {
        if (root == null)
            return root;

        if (value < root.value)
            root.left = deleteRec(root.left, value);
        else if (value > root.value)
            root.right = deleteRec(root.right, value);
        else {
            // 節點只有一個子節點或沒有子節點的情況
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // 節點有兩個子節點的情況，找到右子樹的最小值替代被刪除的節點
            root.value = minValue(root.right);

            // 刪除右子樹中的最小值節點
            root.right = deleteRec(root.right, root.value);
        }

        return root;
    }

    private int minValue(TreeNode root) {
        int minValue = root.value;
        while (root.left != null) {
            minValue = root.left.value;
            root = root.left;
        }
        return minValue;
    }
}

// 測試程式碼
public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        System.out.println("前序走訪:");
        bst.preorder(bst.root);

        System.out.println("\n中序走訪:");
        bst.inorder(bst.root);

        System.out.println("\n後序走訪:");
        bst.postorder(bst.root);

        System.out.println("\n廣度優先走訪:");
        bst.breadthFirst();

        System.out.println("\n搜尋節點 40:");
        System.out.print(bst.search(bst.root, 40).value);

        System.out.println("\n---刪除節點 20---");
        bst.delete(20);

        System.out.println("前序走訪:");
        bst.preorder(bst.root);

        System.out.println("\n---刪除節點 30---");
        bst.delete(30);

        System.out.println("前序走訪:");
        bst.preorder(bst.root);

        System.out.println("\n---刪除節點 50---");
        bst.delete(50);

        System.out.println("前序走訪:");
        bst.preorder(bst.root);
    }
}
```

## 6. 進階樹的概念

### 6.1 執行序樹（Threaded Tree）

執行序樹是一種特殊的二元樹，其主要特點是能夠高效地進行遍歷，尤其是中序遍歷。這種樹的每個節點除了有指向其左右子樹的指標外，還有指向其子父節點的指標，這樣可以在不使用堆疊或遞迴的情況下進行遍歷。

### 6.2 表達式樹（Expression Tree）

表達式樹是一種特殊的二元樹，用於表示算術表達式：
- 葉節點為運算元（operand）
- 內部節點為運算子（operator）

範例：表達式 `(3+4)*(5+6/7)` 的表達式樹：

```
     *
   /   \
  +     +
 / \   / \
3   4 5   /
         / \
        6   7
```

### 6.3 效能考量

1. **時間複雜度**
   - 平衡樹的搜尋、插入、刪除操作：O(log n)
   - 非平衡樹的最差情況：O(n)
2. **空間複雜度**
   - 基本儲存：O(n)
   - 額外的走訪空間：
     - 遞迴實作：O(h)，其中 h 為樹高
     - 迭代實作：O(w)，其中 w 為樹的最大寬度

### 6.4 應用場景

1. 檔案系統的目錄結構
2. 編譯器中的語法樹
3. 資料庫索引
4. 決策樹
5. 遊戲中的 AI 決策系統