# 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
### 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 決策系統
Sign in with Wallet
Connect another wallet