Java SE 資料結構實作：二元搜尋樹 (BST) 節點插入完整代碼

Java SE 資料結構實作：二元搜尋樹 (BST) 節點插入

二元搜尋樹 (Binary Search Tree) 定義

• 左子樹所有節點鍵值 小於 根節點鍵值。
• 右子樹所有節點鍵值 大於 根節點鍵值。
• 左右子樹亦為二元搜尋樹。

完整實作代碼 (含泛型、插入、列印)

public class BSTree<T extends Comparable<T>> {

    private BSTNode<T> mRoot;

    // 內部節點類別
    public static class BSTNode<T extends Comparable<T>> {
        public T key;
        public BSTNode<T> parent, left, right;

        public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }

    // 對外插入入口
    public void insert(T key) {
        BSTNode<T> node = new BSTNode<>(key, null, null, null);
        if (node != null) insert(this, node);
    }

    // 核心插入邏輯：尋找父節點位置 + 掛載
    private void insert(BSTree<T> tree, BSTNode<T> node) {
        BSTNode<T> parent = null;
        BSTNode<T> current = tree.mRoot;

        // 1. 尋找插入位置 (父節點)
        while (current != null) {
            parent = current;
            int cmp = node.key.compareTo(current.key);
            if (cmp < 0) current = current.left;
            else current = current.right;
        }

        // 2. 掛載新節點
        node.parent = parent;
        if (parent == null) {
            tree.mRoot = node; // 空樹，新節點為根
        } else {
            int cmp = node.key.compareTo(parent.key);
            if (cmp < 0) parent.left = node;
            else parent.right = node;
        }
    }

    // 列印樹結構 (輔助驗證)
    private void print(BSTNode<T> node, T parentKey, int direction) {
        if (node != null) {
            if (direction == 0) System.out.printf("%s is root%n", node.key);
            else System.out.printf("%s is %s's %s child%n", node.key, parentKey, direction == 1 ? "right" : "left");
            print(node.left, node.key, -1);
            print(node.right, node.key, 1);
        }
    }

    public void print() {
        if (mRoot != null) print(mRoot, mRoot.key, 0);
    }

    // 測試主程式
    public static void main(String[] args) {
        BSTree<Integer> tree = new BSTree<>();
        tree.insert(3);
        tree.insert(1);
        tree.insert(2);
        tree.insert(5);
        tree.insert(4);
        tree.insert(6);
        tree.print();
    }
}

執行輸出

3 is root
1 is 3's left child
2 is 1's right child
5 is 3's right child
4 is 5's left child
6 is 5's right child

核心邏輯解析

1. 泛型限制 <T extends Comparable<T>>：確保鍵值可比較。
2. 插入分兩階段：
   • 向下遍歷找到 parent (即將成為新節點父節點的位置)。
   • 比較新節點鍵值與 parent.key，決定掛載為左或右子節點。
3. 空樹處理：parent == null 時直接設為根節點。
4. 不允許重複鍵值：cmp >= 0 皆走右子樹，若需去重可在比較處加邏輯。

擴充建議

• 實作刪除節點 (三種情況：葉節點、單子節點、雙子節點需找前驅/後繼)。
• 實作查找、中序遍歷 (輸出有序序列)、層序遍歷。
• 引入平衡機制 (AVL、紅黑樹) 避免退化為鏈表。