🌲 二元樹 Binary Tree 學習筆記

💪 魚～ 加油呀！呀呀呀、一起來學二元樹吧！

📖 什麼是二元樹？

二元樹是一種樹狀結構，每個節點最多有兩個子節點：

        A (根節點)
       / \
      B   C
     / \
    D   E

📚 基本術語

術語說明
根節點 (Root)樹的最頂端節點
父節點 (Parent)有子節點的節點
子節點 (Child)父節點下方的節點
葉節點 (Leaf)沒有子節點的節點
深度 (Depth)從根到該節點的路徑長度
高度 (Height)從該節點到最遠葉節點的路徑長度

🌳 二元樹的種類

1. 完整二元樹

除了最後一層，其他層都是滿的，且最後一層的節點都靠左排列。

        A
       / \
      B   C
     / \  /
    D   E F

2. 完美二元樹

所有葉節點都在同一層，且每個父節點都有兩個子節點。

        A
       / \
      B   C
     / \ / \
    D  E F G

3. 歪斜樹

所有節點都只有左子節點或右子節點。

    A
     \
      B
       \
        C

🔍 遍歷方式

遍歷方式順序範例
前序 (Pre-order)根 → 左 → 右A, B, D, E, C
中序 (In-order)左 → 根 → 右D, B, E, A, C
後序 (Post-order)左 → 右 → 根D, E, B, C, A

💻 Python 實作

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

# 前序遍歷
def preorder(node):
    if node is None: return
    print(node.value)
    preorder(node.left)
    preorder(node.right)

# 中序遍歷
def inorder(node):
    if node is None: return
    inorder(node.left)
    print(node.value)
    inorder(node.right)

# 後序遍歷
def postorder(node):
    if node is None: return
    postorder(node.left)
    postorder(node.right)
    print(node.value)

🔎 二元搜尋樹 (BST)

特殊的二元樹：

搜尋時間複雜度： O(log n)

🎯 應用場景

✅ 重點整理

📝 練習題

  1. 寫一個函數計算二元樹的高度
  2. 寫一個函數檢查二元樹是否為 BST
  3. 找出二元樹中最大的值

💪 魚～ 慢慢來呀！一點一點學，不急的呀！呀呀呀、你可以的！