Java SE 資料結構：二元樹三種遍歷與查找實作

Java SE 資料結構：二元樹三種遍歷與查找實作

遍歷定義 (以根節點為基準)

• 前序 (Pre-order)： 根 → 左 → 右
• 中序 (In-order)： 左 → 根 → 右 (BST 中序輸出為有序序列)
• 後序 (Post-order)： 左 → 右 → 根

查找邏輯 (BST 特有)

從根節點開始比較目標鍵值：

• 目標 < code>node.key → 移至左子樹
• 目標 > node.key → 移至右子樹
• 相等 → 找到，返回節點
• 走到 null → 不存在，返回 null

完整實作代碼 (接續 BSTree 類別)

// 前序遍歷
public void preOrder() { preOrder(mRoot); }
private void preOrder(BSTNode<T> node) {
    if (node != null) {
        System.out.print(node.key + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

// 中序遍歷
public void inOrder() { inOrder(mRoot); }
private void inOrder(BSTNode<T> node) {
    if (node != null) {
        inOrder(node.left);
        System.out.print(node.key + " ");
        inOrder(node.right);
    }
}

// 後序遍歷
public void postOrder() { postOrder(mRoot); }
private void postOrder(BSTNode<T> node) {
    if (node != null) {
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.key + " ");
    }
}

// BST 查找
public BSTNode<T> search(T key) {
    BSTNode<T> current = mRoot;
    while (current != null) {
        int cmp = key.compareTo(current.key);
        if (cmp < 0) current = current.left;
        else if (cmp > 0) current = current.right;
        else return current;
    }
    return null;
}

測試驗證 (使用上篇建立的樹：插入 3,1,2,5,4,6)

BSTree<Integer> tree = new BSTree<>();
tree.insert(3); tree.insert(1); tree.insert(2);
tree.insert(5); tree.insert(4); tree.insert(6);

tree.preOrder();  // 輸出: 3 1 2 5 4 6
tree.inOrder();   // 輸出: 1 2 3 4 5 6 (有序!)
tree.postOrder(); // 輸出: 2 1 4 6 5 3

BSTree.BSTNode<Integer> node = tree.search(5);
System.out.println(node != null ? node.left.key : "not found"); // 輸出: 4

關鍵觀察

1. 中序遍歷 BST 產生有序序列，這是 BST 最重要的性質之一。
2. 查找時間複雜度平均 O(log n)，最壞 O(n) (樹退化為鏈表)。
3. 遞迴實作簡潔但深度過大時可能堆疊溢位，生產環境可改用迭代 + 显式堆疊。

圖示樹結構

        3
       / \
      1   5
       \ / \
       2 4  6