Tree

Tree 是一種階層式的非線性資料結構，適合表達具有「父子關係」的資料，例如檔案系統、分類階層、語法樹等。最常見的是二元樹（Binary Tree）。

---

一、基本術語

名稱	說明
Root	樹的起點節點（最上層）
Node	樹中的每個元素
Edge	節點之間的連結
Leaf	沒有子節點的節點（最底層）
Parent	有下層子節點的節點
Child	某節點的下層節點
Subtree	一個節點及其所有子節點構成的子樹
Height	從根到最深葉節點的最大距離（邊數）

---

二、樹的種類

類型	說明
二元樹（Binary Tree）	每個節點最多有兩個子節點（左子節點與右子節點）
完全二元樹（Complete Binary Tree）	除最後一層外皆為滿，且從左至右填滿
滿二元樹（Full Binary Tree）	每個節點要嘛沒有子節點，要嘛有兩個子節點
二元搜尋樹（Binary Search Tree）	左 < 根 < 右 的排序特性
平衡樹（Balanced Tree）	任意子樹的高度差不超過一定限制（如 AVL、Red-Black Tree）
堆積樹（Heap）	根節點是最大值或最小值（Max Heap / Min Heap）

---

三、基本節點與樹的結構（Python 範例）

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

---

四、樹的遍歷方式（Traversal）

1. 前序遍歷（Pre-order）

# 根 → 左 → 右

def preorder(node):
    if node:
        print(node.value)
        preorder(node.left)
        preorder(node.right)

2. 中序遍歷（In-order）

# 左 → 根 → 右（BST 中序會得到排序結果）

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value)
        inorder(node.right)

3. 後序遍歷（Post-order）

# 左 → 右 → 根

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value)

4. 層序遍歷（Level-order / BFS）

from collections import deque

def level_order(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

---

五、Tree 特性與應用

• 適合表示階層結構（如分類、公司組織、語法結構）

• 二元搜尋樹可快速查找與插入（平均 O(log n)）

• Heap 常用於優先佇列與資源排程

---

六、Tree vs Graph

特性	Tree	Graph
結構方向性	單向（從根向下）	可單向或雙向
是否有環	無環	可有環或無環
使用場景	分層結構、資料索引	網路結構、路徑搜尋

---

Tree 是許多進階資料結構（如 Heap、Trie、Segment Tree）與演算法（如 Huffman 編碼、AVL 平衡樹）的基礎，掌握它是深入演算法設計的關鍵。