Java 實現二叉樹與三種遍歷遞歸詳解

核心思想：引用鏈接節點

Java 中無指針，但在類內部定義**自身類型的引用**即可構建鏈式結構：

class Tree {
    int data;
    Tree left;
    Tree right;
}

new Tree() 時，left/right 即為連接左右子樹的「邊」。

完整代碼：構建二叉搜索樹並遍歷

package code;
public class TwoTree {
    public static void main(String[] args) {
        Tree root = new Tree(50);
        int[] array = {25, 89, 48, 90, 101, 13, 45, 60};
        for (int n : array) root.insert(root, n);
        Bianli bl = new Bianli(root);
        bl.second(root); // 中序遍歷輸出
    }
}

class Tree {
    int data;
    Tree left, right;
    public Tree(int data) { this.data = data; left = right = null; }

    public void insert(Tree root, int data) {
        if (data > root.data) {
            if (root.right == null) root.right = new Tree(data);
            else insert(root.right, data);
        } else {
            if (root.left == null) root.left = new Tree(data);
            else insert(root.left, data);
        }
    }
}

class Bianli {
    Tree root;
    public Bianli(Tree root) { this.root = root; }

    // 前序：根-左-右
    public void first(Tree root) {
        if (root != null) {
            System.out.println(root.data);
            first(root.left);
            first(root.right);
        }
    }
    // 中序：左-根-右（輸出有序序列）
    public void second(Tree root) {
        if (root != null) {
            second(root.left);
            System.out.println(root.data);
            second(root.right);
        }
    }
    // 後序：左-右-根
    public void third(Tree root) {
        if (root != null) {
            third(root.left);
            third(root.right);
            System.out.println(root.data);
        }
    }
}

遞歸機制深度解析

插入遞歸

insert 將大樹分解為無數 /\ 小樹：若目標節點為空則掛載，否則以該節點為新根繼續遞歸，本質是**問題規模縮小** + **邊界條件終止**。

遍歷遞歸

三種遍歷代碼幾乎相同，僅 **輸出語句位置** 不同：

• 前序：遞歸調用**前**輸出
• 中序：左遞歸**後**、右遞歸**前**輸出
• 後序：左右遞歸**後**輸出

類比階乘遞歸 DG(n) = n * DG(n-1)：遞歸向深處推進至終止條件，再**回溯**時依次完成各層剩餘操作。輸出位置決定了回溯時的執行順序，從而產生不同遍歷序列。

關鍵感悟

遞歸本質：向深處分解問題 → 觸及邊界 → 回溯合併結果。遍歷順序 = 回溯時操作的順序。