Java 二叉樹遞歸與非遞歸遍歷完整實作

前言

二叉樹遍歷是數據結構核心考點。本文以固定樹形結構為例，完整實現前序、中序、後序的遞歸與非遞歸（棧模擬）兩種版本，並驗證輸出一致性。

樹結構定義

        H
       / \
      D   G
     / \   \
    B   C   F
     \     /
      A   E

前序: H D B A C G F E
中序: B A D C H G E F
後序: A B C D E F G H

節點類

public class BTNode {
    private char key;
    private BTNode left, right;
    // 建構子、getter/setter 略
}

建樹方法

public static BTNode init() {
    BTNode a=new BTNode('A');
    BTNode b=new BTNode('B', null, a);
    BTNode c=new BTNode('C');
    BTNode d=new BTNode('D', b, c);
    BTNode e=new BTNode('E');
    BTNode f=new BTNode('F', e, null);
    BTNode g=new BTNode('G', null, f);
    BTNode h=new BTNode('H', d, g);
    return h; // root
}

遞歸遍歷（簡潔直觀）

// 前序：根 -> 左 -> 右
void preorder(BTNode p) {
    if (p!=null) { visit(p); preorder(p.getLeft()); preorder(p.getRight()); }
}

// 中序：左 -> 根 -> 右
void inorder(BTNode p) {
    if (p!=null) { inorder(p.getLeft()); visit(p); inorder(p.getRight()); }
}

// 後序：左 -> 右 -> 根
void postorder(BTNode p) {
    if (p!=null) { postorder(p.getLeft()); postorder(p.getRight()); visit(p); }
}

非遞歸遍歷（棧模擬調用棧）

前序：根左右 → 棧先推右再推左

void iterativePreorder(BTNode p) {
    Stack<BTNode> st = new Stack<>();
    if (p!=null) st.push(p);
    while (!st.empty()) {
        p = st.pop();
        visit(p);
        if (p.getRight()!=null) st.push(p.getRight());
        if (p.getLeft()!=null) st.push(p.getLeft());
    }
}

中序：左根右 → 一路向左入棧，彈出訪問，轉右

void iterativeInorder(BTNode p) {
    Stack<BTNode> st = new Stack<>();
    while (p!=null) {
        while (p!=null) {
            if (p.getRight()!=null) st.push(p.getRight()); // 右子先入棧
            st.push(p);                                     // 自己入棧
            p = p.getLeft();                                // 走左
        }
        p = st.pop();
        while (!st.empty() && p.getRight()==null) { // 無右子，連續彈出訪問
            visit(p);
            p = st.pop();
        }
        visit(p);
        if (!st.empty()) p = st.pop(); // 取出右子繼續
        else p = null;
    }
}

後序：左右根 → 最複雜，需記錄上一訪問節點判斷右子是否已處理

void iterativePostorder(BTNode p) {
    BTNode q = p; // 上一訪問節點
    Stack<BTNode> st = new Stack<>();
    while (p!=null) {
        // 1. 左子樹一路入棧
        for (; p.getLeft()!=null; p=p.getLeft()) st.push(p);
        // 2. 處理無右子 或 右子已訪問 的節點
        while (p!=null && (p.getRight()==null || p.getRight()==q)) {
            visit(p);
            q = p;
            if (st.empty()) return;
            p = st.pop();
        }
        // 3. 處理右子
        st.push(p);
        p = p.getRight();
    }
}

驗證輸出

Pre-Order: H D B A C G F E
In-Order:  B A D C H G E F
Post-Order:A B C D E F G H

Pre-Order: H D B A C G F E
In-Order:  B A D C H G E F
Post-Order:A B C D E F G H

遞歸與非遞歸結果完全一致。

複雜度與棧深度

總結

• 前序最易非遞歸：根、右、左入棧。
• 中序核心是「左邊緣入棧、彈出訪問、轉右」。
• 後序靈魂在於 q 變量記錄「上一訪問」，判斷右子樹是否已處理完畢。
• 面試常考：手寫三種非遞歸、分析空間複雜度、說明 q 作用。