🌳
歡迎來到 Tree & BST
進度
高中資訊科 · 資料結構 · 第三單元

🌳 Tree & BST

資料夾、族譜、搜尋引擎——你每天都在用的樹狀結構

🤔 開始之前，說說你的直覺
電腦要在「100萬筆」資料裡找一個數字，你覺得最快的方法是什麼？

💡 先記住你的直覺——等等 BST 互動讓你親眼驗證！

從頭找到尾
最壞比 1,000,000 次
BST 每次砍一半
最壞只比 20 次！
A1先猜再做——建出平衡樹後，插入 25 會走幾步？

用下方「推薦數列 → ✅ 平衡樹」建樹，猜猜看：要插入 25，需要比較幾次才能找到位置？

Q. 🎯 我猜 次比較（建好樹後按確認）
A2自己建一棵 BST — 規則：左 < 根 < 右

每次插入一個數字，BST 自動比大小往左或右走，逐步長出樹的形狀。

推薦數列 →
自訂數列 →
👆 選擇推薦數列或自訂數列開始建樹
單個插入
搜尋
← 選推薦數列建樹，再用搜尋體驗 BST 的效率！
A3「插入順序」決定樹的形狀 → 形狀決定搜尋速度
✅ 平衡樹
50→30→70→20→40→60→80
高度=3，搜尋最多 3 次
❌ 不平衡
10→20→30→40→50→60→70
高度=7，搜尋最多 7 次
🎯 生活比喻：猜數字遊戲 每個節點就像「守門人」問：「比我大還是比我小？」 每走一步砍掉一半可能性！
💻進階：Python 實作 BSTADVANCED
Python class Node: def __init__(self, val): self.val = val self.left = self.right = None def insert(root, val): if root is None: return Node(val) if val < root.val: root.left = insert(root.left, val) else: root.right = insert(root.right, val) return root
搜尋（平衡）O(log n)每次砍一半，100萬筆只需 20 次
搜尋（不平衡）O(n)退化成鏈，跟線性搜尋一樣
🔥 挑戰：計算樹高

height = 1 + max(左子樹高度, 右子樹高度)

👁 查看答案
A4學習反思後設認知練習
BST 為什麼「從中間開始插」比「從小到大插」快很多？
REFERENCE ANSWER
從中間插 → 左右均衡，高度 log₂n，搜尋 O(log n)。從小到大插 → 退化成直線，高度 n，搜尋 O(n)。
你覺得理解到什麼程度？
B1以下走訪說明都以這棵樹為例
50 30 70 20 40 60 80 根 Root 葉 葉 葉 葉
B2速記法 — 用「走路蓋章」來記走訪順序
Q. 🎯 先預測 對上面這棵樹做「前序走訪」，第三個輸出的數字是？
✏️ 想像你沿著樹的輪廓從左邊走一圈
每個節點旁邊有 三個位置可以「蓋章記錄」：
🟣 第一次靠近（左側）→ 前序 Pre-order   🔵 從左子樹回來（下方）→ 中序 In-order   🔴 要離開（右側）→ 後序 Post-order
🟣

前序（Pre-order）

順序：自己→左→右 / 結果：50→30→20→40→70→60→80 / 應用：複製整棵樹

🔵

中序（In-order）

順序：左→自己→右 / 結果（=排序）：20→30→40→50→60→70→80 ✨ / 應用：輸出排序結果

🔴

後序（Post-order）

順序：左→右→自己 / 結果：20→40→30→60→80→70→50 / 應用：刪除整棵樹

B3動畫 — 走訪順序一步步亮起，標上順序編號
走訪結果序列
← 選一種走訪方式開始！
🔵 中序的神奇特性對 BST 做中序走訪，輸出一定是由小到大排好序的！
🔴 後序的生活例子刪資料夾：先刪裡面的檔案，再刪資料夾本身 → 後序！
B4學習反思後設認知練習
為什麼 BST 中序走訪輸出的一定是由小到大？
REFERENCE ANSWER
BST 定義：左 < 根 < 右。中序先走左（最小），再記自己，再走右（較大）。遞迴加上 BST 大小規則，輸出必然遞增！
你覺得理解到什麼程度？
C1點選術語卡片，圖中對應位置亮起！

點「高度 & 層」時，圖中會顯示各層 Level 編號。

👆 點選下方任一術語
Root

🌱 根節點

整棵樹最頂端，沒有父節點

Leaf

🍂 葉節點

沒有任何子節點，樹的最末端

Parent

👨‍👧 父節點

直接連結到子節點的節點

Child

👶 子節點

被父節點連結的節點

Height / Level

📏 高度 & 層

根到最深葉的邊數；根為 Level 0，往下 +1

Subtree

🌿 子樹

某節點和其所有後代組成的樹

Path

🛤️ 路徑

從一個節點到另一個節點的節點序列

Binary

🔢 二元樹

每個節點最多 2 個子節點

D1樹在生活中無所不在
📁

電腦資料夾

C:\ → 文件 → 作業 → 第一章.docx

👨‍👩‍👧‍👦

家族族譜

曾祖父母→祖父母→父母→你

🔍

搜尋引擎

Google 用樹狀索引快速搜尋幾百億網頁

🎮

遊戲決策

RPG 技能樹、對話選項分支

🌐

網頁 HTML

<html>→<body>→<div> 就是 DOM 樹

♟️

西洋棋 AI

每一步棋展開成樹，計算最佳路徑

🌳 為什麼要學樹？ BST 每次搜尋砍掉一半——大學資料庫、作業系統都用到樹。學好樹等於打通資訊的任督二脈！
D2學習反思P2 後設認知
在你的生活或未來想做的事中，樹狀結構可能出現在哪裡？
很棒的連結！
能把所學連結到自己有興趣的領域，這正是最深刻的學習方式！
你覺得理解到什麼程度？