Java 實作二元搜尋樹 (Binary Search Tree) 完整教學

什麼是二元搜尋樹？

二元搜尋樹 (Binary Search Tree, BST) 是一種資料結構，每個節點最多擁有兩個子節點 (左、右)，且滿足以下性質：

• 左子樹所有節點的值 小於 父節點
• 右子樹所有節點的值 大於或等於 父節點
• 左右子樹皆為二元搜尋樹

這種結構讓搜尋、插入、刪除操作的平均時間複雜度達到 O(log n)，是演算法面試與實務開發的基礎。

完整 Java 實作

package com.test;

/**
 * 二元搜尋樹實作示範
 * 包含節點插入、鍵值搜尋、前序遍歷列印
 */
public class BinaryTreeTest {
    private BinaryTree root = null;

    public BinaryTreeTest() {
        init();
    }

    /** 初始化測試資料並建立樹 */
    private void init() {
        int[] data = { 12, 11, 34, 45, 67, 38, 56, 43, 22, 8 };
        root = new BinaryTree(data[0]);
        System.out.println("二元搜尋樹建立過程：");
        System.out.println("------------------------------------");
        System.out.println(data[0] + "：root");
        for (int i = 1; i < data.length; i++) {
            System.out.print(data[i] + "：");
            root.insertTree(root, data[i]);
        }
        System.out.println("------------------------------------");
    }

    /** 對外提供的搜尋方法 */
    public void search(int key) {
        if (searchKey(root, key)) {
            System.out.println("找到了：" + key);
        } else {
            System.out.println("沒有找到：" + key);
        }
    }

    /** 遞迴搜尋鍵值 */
    private boolean searchKey(BinaryTree node, int key) {
        if (node == null) return false;
        if (node.data == key) return true;
        if (key >= node.data) return searchKey(node.right, key);
        return searchKey(node.left, key);
    }

    /** 內部節點類別 */
    static class BinaryTree {
        int data;
        BinaryTree left;
        BinaryTree right;

        BinaryTree(int data) {
            this.data = data;
            left = null;
            right = null;
        }

        /** 插入新節點並列印路徑 */
        void insertTree(BinaryTree root, int data) {
            if (data >= root.data) {
                if (root.right == null) {
                    System.out.println(" -> new right");
                    root.right = new BinaryTree(data);
                } else {
                    System.out.print(" -> right");
                    insertTree(root.right, data);
                }
            } else {
                if (root.left == null) {
                    System.out.println(" -> new left");
                    root.left = new BinaryTree(data);
                } else {
                    System.out.print(" -> left");
                    insertTree(root.left, data);
                }
            }
        }
    }

    public static void main(String[] args) {
        BinaryTreeTest tree = new BinaryTreeTest();
        tree.search(8);  // 搜尋鍵值 8
    }
}

執行輸出與解析

二元搜尋樹建立過程：
------------------------------------
12：root
11： -> new left
34： -> new right
45： -> right -> new right
67： -> right -> right -> new right
38： -> right -> right -> new left
56： -> right -> right -> right -> new left
43： -> right -> right -> left -> new right
22： -> right -> new left
8： -> left -> new left
------------------------------------
找到了：8

從輸出可清晰觀察每個數值的插入路徑：

• 12 為根節點
• 11 < 12 → 左子樹
• 34 > 12 → 右子樹
• 45 > 12 → 右 → 45 > 34 → 右
• ...以此類推

搜尋 8 時，路徑為：12 (左) → 11 (左) → 8 找到。

核心操作複雜度

進階主題

• 平衡樹：AVL Tree、Red-Black Tree 透過旋轉維持高度平衡，保證 O(log n)
• 刪除節點：需處理三種情況 (無子、單子、雙子)，雙子時通常用中序後繼節點取代
• 遍歷方式：前序、中序 (輸出排序結果)、後序、層序

常見面試題

1. 如何驗證一棵二元樹是否為合法的 BST？ (中序遍歷應為遞增序列)
2. 找出 BST 中第 k 小的元素？ (中序遍歷計數或朝左子樹大小決策)
3. 將有序陣列轉換為高度平衡的 BST？ (取中點為根，遞迴建立左右子樹)