Tree

樹狀結構（Tree）像大自然中的樹木一樣，呈現階層化（Hierarchical）的分支結構，可看作是 Graph 的其中一種形式。

在日常生活中，電腦的「資料夾路徑」或公司的「組織架構圖」，本質上都是一棵樹。

DSA - Tree

白話理解

想像一份公司組織圖：執行長在最上面（Root），底下帶著幾位主管（Child），主管底下又各自帶著更多員工，一路往下展開。沒有主管的最底層員工，就像是 Tree 裡的葉節點（Leaf）。這種「一層帶一層、只能往下展開」的階層關係，就是 Tree 的核心精神。

專有名詞

以下是 Tree 常見的專有名詞：

節點（Node）：基本單元，包含資料本身以及指向子節點的指標。
父節點（Parent）/ 子節點（Child）：上下層有連線關係的節點。上層是父，下層是子。
根節點（Root）：最頂端的節點，一棵樹只會有一個根，而這個根沒有父節點。
兄弟節點（Siblings）：擁有「同一個父節點」的同層節點。
葉節點（Leaf / External Node）：最底層、沒有任何子節點的末端節點。
子樹（Subtree）：由某個節點及其所有後代節點所組成的局部樹狀結構。
高度（Height）/ 深度（Depth）：
- 深度：從根節點走到該節點的步數（根節點深度為 0）。
- 高度：從該節點走到最深葉節點的最長步數。整棵樹的高度即為根節點的高度。

常見種類

這邊只介紹刷題最常見的 Tree，其他還有平衡樹和 B Tree 等等，有興趣可以自己搜尋。

二元樹（Binary Tree）：最基礎的樹，規定每個節點最多只能有兩個子節點（通常稱為左子節點與右子節點）。
二元搜尋樹（Binary Search Tree, BST）：
- 比起 Binary Tree 更多了一個嚴格規定：任何節點的左子樹資料都比自己小，右子樹資料都比自己大。
- 這種結構讓找資料的速度變得非常快。

BST 嚴格遵守左節點比較小，右節點比較大的規則

               [ 50 ]  <-- 根節點 (Root)
              /      \
            /          \
        [ 30 ]        [ 70 ]
       /      \      /      \
     /        \    /        \
  [ 20 ]    [ 40 ][ 60 ]    [ 80 ]

Binary Search Tree 的實作

一個 Binary Search Tree 由數個 Node 組成。

Python
JavaScript
Java

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Node {
  constructor(val) {
    this.val = val;
	this.left = null;
	this.right = null;
  }
}

class Node {
    int val;
    Node left;
    Node right;

    Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

Binary Search Tree 的每個 Node 都嚴格遵守左子節點比較小，右子節點比較大的規則。

Python
JavaScript
Java

class BinarySearchTree:
    def __init__(self):
        self.root = None  # 根節點，初始化為空值

    # 1. 插入新值：O(log n)
    def insert(self, val):
        new_node = Node(val)

        # 如果樹是空的，新節點直接成為根節點
        if not self.root:
            self.root = new_node
            return self

        current_node = self.root
        while current_node:
            # 依據 BST 定義，不允許重複的值存在
            if val == current_node.val:
                return None

            # 值大於目前節點，往右走
            if val > current_node.val:
                if not current_node.right:
                    current_node.right = new_node  # 找到空位，插入並結束
                    return self
                current_node = current_node.right  # 右邊有人，繼續往下一層走
            # 新值小於目前節點，往左走
            else:
                if not current_node.left:
                    current_node.left = new_node  # 找到空位，插入並結束
                    return self
                current_node = current_node.left  # 左邊有人，繼續往下一層走

    # 2. 尋找特定值：O(log n)
    def find(self, val):
        if not self.root:
            return False

        current_node = self.root
        while current_node:
            if val < current_node.val:
                current_node = current_node.left  # 目標較小，往左搜尋
            elif val > current_node.val:
                current_node = current_node.right  # 目標較大，往右搜尋
            else:
                return current_node  # 找到了，回傳該節點
        return False  # 找遍了都沒找到

    # 3. 刪除特定值：O(log n)
    def remove(self, val):
        if val is None:
            return None
        # 透過輔助方法更新根節點（因為根節點也有可能被刪除）
        self.root = self.remove_helper(val, self.root)

    # 刪除的遞迴輔助方法
    def remove_helper(self, val, current_node):
        # 走到盡頭都沒找到，回傳 None
        if not current_node:
            return None

        # 尋找階段：根據大小關係繼續往左或往右遞迴找尋
        if val < current_node.val:
            current_node.left = self.remove_helper(val, current_node.left)
            return current_node
        elif val > current_node.val:
            current_node.right = self.remove_helper(val, current_node.right)
            return current_node

        # 刪除階段：已找到目標節點 (val == current_node.val)

        # 情況 1：目標是「Leaf」（沒有任何子節點），直接刪除
        if not current_node.left and not current_node.right:
            return None
        # 情況 2：目標「只有右子節點」，直接用右子節點取代自己
        elif not current_node.left:
            return current_node.right
        # 情況 3：目標「只有左子節點」，直接用左子節點取代自己
        elif not current_node.right:
            return current_node.left
        # 情況 4：目標「同時有左右子節點」
        else:
            # 找出右子樹中的「最小值節點」來頂替自己的位置
            min_right_child_node = self.find_min_value(current_node.right)
            current_node.val = min_right_child_node.val  # 把數值換過去

            # 接著在右子樹中，把原本那個用來頂替的節點刪除
            current_node.right = self.remove_helper(min_right_child_node.val, current_node.right)
            return current_node

class BinarySearchTree {
  constructor() {
    this.root = null; // 根節點，初始化為空值
  }

  // 1. 插入新值：O(log n)
  insert(val) {
    const newNode = new Node(val);
    
    // 如果樹是空的，新節點直接成為根節點
    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let currentNode = this.root;
    while (currentNode) {
      // 依據 BST 定義，不允許重複的值存在
      if (val === currentNode.val) return undefined;

      // 值大於目前節點，往右走
      if (val > currentNode.val) {
        if (!currentNode.right) {
          currentNode.right = newNode; // 找到空位，插入並結束
          return this;
        }
        currentNode = currentNode.right; // 右邊有人，繼續往下一層走
      } 
      // 新值小於目前節點，往左走
      else {
        if (!currentNode.left) {
          currentNode.left = newNode;  // 找到空位，插入並結束
          return this;
        }
        currentNode = currentNode.left;  // 左邊有人，繼續往下一層走
      }
    }
  }

  // 2. 尋找特定值：O(log n)
  find(val) {
    if (!this.root) return false;
    
    let currentNode = this.root;
    while (currentNode) {
      if (val < currentNode.val) {
        currentNode = currentNode.left;  // 目標較小，往左搜尋
      } else if (val > currentNode.val) {
        currentNode = currentNode.right; // 目標較大，往右搜尋
      } else {
        return currentNode;              // 找到了，回傳該節點
      }
    }
    return false; // 找遍了都沒找到
  }

  // 3. 刪除特定值：O(log n)
  remove(val) {
    if (val === null || val === undefined) return undefined;
    // 透過輔助方法更新根節點（因為根節點也有可能被刪除）
    this.root = this.removeHelper(val, this.root);
  }

  // 刪除的遞迴輔助方法
  removeHelper(val, currentNode) {
    // 走到盡頭都沒找到，回傳 null
    if (!currentNode) return null;

    // 尋找階段：根據大小關係繼續往左或往右遞迴找尋
    if (val < currentNode.val) {
      currentNode.left = this.removeHelper(val, currentNode.left);
      return currentNode;
    } else if (val > currentNode.val) {
      currentNode.right = this.removeHelper(val, currentNode.right);
      return currentNode;
    }

    // 刪除階段：已找到目標節點 (val === currentNode.val)
    
    // 情況 1：目標是「Leaf」（沒有任何子節點），直接刪除
    if (!currentNode.left && !currentNode.right) {
      return null;
    } 
    // 情況 2：目標「只有右子節點」，直接用右子節點取代自己
    else if (!currentNode.left) {
      return currentNode.right;
    } 
    // 情況 3：目標「只有左子節點」，直接用左子節點取代自己
    else if (!currentNode.right) {
      return currentNode.left;
    } 
    // 情況 4：目標「同時有左右子節點」
    else {
      // 找出右子樹中的「最小值節點」來頂替自己的位置
      let minRightChildNode = this.findMinValue(currentNode.right);
      currentNode.val = minRightChildNode.val; // 把數值換過去
      
      // 接著在右子樹中，把原本那個用來頂替的節點刪除
      currentNode.right = this.removeHelper(minRightChildNode.val, currentNode.right);
      return currentNode;
    }
  }
}

class BinarySearchTree {
    Node root; // 根節點，初始化為空值

    BinarySearchTree() {
        this.root = null;
    }

    // 1. 插入新值：O(log n)
    BinarySearchTree insert(int val) {
        Node newNode = new Node(val);

        // 如果樹是空的，新節點直接成為根節點
        if (this.root == null) {
            this.root = newNode;
            return this;
        }

        Node currentNode = this.root;
        while (currentNode != null) {
            // 依據 BST 定義，不允許重複的值存在
            if (val == currentNode.val) return null;

            // 值大於目前節點，往右走
            if (val > currentNode.val) {
                if (currentNode.right == null) {
                    currentNode.right = newNode; // 找到空位，插入並結束
                    return this;
                }
                currentNode = currentNode.right; // 右邊有人，繼續往下一層走
            }
            // 新值小於目前節點，往左走
            else {
                if (currentNode.left == null) {
                    currentNode.left = newNode; // 找到空位，插入並結束
                    return this;
                }
                currentNode = currentNode.left; // 左邊有人，繼續往下一層走
            }
        }
        return null;
    }

    // 2. 尋找特定值：O(log n)
    Node find(int val) {
        if (this.root == null) return null;

        Node currentNode = this.root;
        while (currentNode != null) {
            if (val < currentNode.val) {
                currentNode = currentNode.left; // 目標較小，往左搜尋
            } else if (val > currentNode.val) {
                currentNode = currentNode.right; // 目標較大，往右搜尋
            } else {
                return currentNode; // 找到了，回傳該節點
            }
        }
        return null; // 找遍了都沒找到
    }

    // 3. 刪除特定值：O(log n)
    void remove(Integer val) {
        if (val == null) return;
        // 透過輔助方法更新根節點（因為根節點也有可能被刪除）
        this.root = removeHelper(val, this.root);
    }

    // 刪除的遞迴輔助方法
    Node removeHelper(int val, Node currentNode) {
        // 走到盡頭都沒找到，回傳 null
        if (currentNode == null) return null;

        // 尋找階段：根據大小關係繼續往左或往右遞迴找尋
        if (val < currentNode.val) {
            currentNode.left = removeHelper(val, currentNode.left);
            return currentNode;
        } else if (val > currentNode.val) {
            currentNode.right = removeHelper(val, currentNode.right);
            return currentNode;
        }

        // 刪除階段：已找到目標節點 (val == currentNode.val)

        // 情況 1：目標是「Leaf」（沒有任何子節點），直接刪除
        if (currentNode.left == null && currentNode.right == null) {
            return null;
        }
        // 情況 2：目標「只有右子節點」，直接用右子節點取代自己
        else if (currentNode.left == null) {
            return currentNode.right;
        }
        // 情況 3：目標「只有左子節點」，直接用左子節點取代自己
        else if (currentNode.right == null) {
            return currentNode.left;
        }
        // 情況 4：目標「同時有左右子節點」
        else {
            // 找出右子樹中的「最小值節點」來頂替自己的位置
            Node minRightChildNode = findMinValue(currentNode.right);
            currentNode.val = minRightChildNode.val; // 把數值換過去

            // 接著在右子樹中，把原本那個用來頂替的節點刪除
            currentNode.right = removeHelper(minRightChildNode.val, currentNode.right);
            return currentNode;
        }
    }
}

複雜度

操作種類	平均時間複雜度	最差時間複雜度	原因說明
搜尋資料 (Search)	O(log n)	O(n)	平均每次都能省掉一半的分支（對數時間）；但若樹嚴重傾斜（歪向一邊），就會退化成像 Linked List 一樣要一筆一筆找。
新增資料 (Insert)	O(log n)	O(n)	先搜尋找到對的位置（O(log n)），再放進去（O(1)）。
刪除資料 (Delete)	O(log n)	O(n)	找到目標後，還需要處理子節點的接頭問題。

遍歷 Tree 的演算法

寫在 Tree Traversal 裡，歡迎前去參考。

適用情況

HTML DOM Tree：
- 網頁結構在瀏覽器渲染時，就是被解析成一棵 DOM Tree。
- 例如 <html><head/><body><div><div/><body/><html/>，Root 是 html，它的子節點有 head 和 body，而 body 的子節點則有 div。
檔案系統（File System）：電腦的硬碟路徑（C:\ > Program Files > Nodejs）就是標準的樹狀階層。
字典樹（Trie / Prefix Tree）：
- 搜尋引擎或手機打字的「自動完成 / 關鍵字預測」功能。
- 把英文字母一個一個串成樹狀，輸入 "ap" 就會順著分支找到 "apple", "application"。
路由演算法（Routing Protocols）：網路封包在路由器之間傳遞時，會使用生成樹協定（STP）來尋找最短路徑並避免網路無窮迴圈。

常見誤區

誤以為 BST 一定是「平衡」的：如果照順序插入 1, 2, 3, 4, 5，BST 會退化成一條長長的鏈（每個節點都只有右子節點），這時複雜度不再是 O(log n)，而是退化成跟 Linked List 一樣的 O(n)。想避免這個問題，需要用平衡樹（如 AVL Tree、Red-Black Tree），這裡不深入探討。
搞混高度（Height）與深度（Depth）：深度是「從 Root 數到某節點」，高度是「從某節點數到最深的 Leaf」，兩者方向相反，計算整棵樹的高度時，要從 Root 往下算到最深的 Leaf，不是從某個節點往上數到 Root。
刪除節點時漏掉某種情況：BST 的刪除需要處理「Leaf」「只有一個子節點」「有兩個子節點」三種情況，尤其是最後一種（需要找右子樹最小值來頂替），是新手最容易漏寫或寫錯的部分，建議實作時對照文中的四種情況逐一檢查。

專有名詞​

常見種類​

Binary Search Tree 的實作​

複雜度​

遍歷 Tree 的演算法​

適用情況​

常見誤區​