Java 實現表達式二叉樹：從中綴字串到樹結構的構建與遍歷

什麼是表達式二叉樹

將算術表達式 (如 a + b * (c - d)) 轉為二叉樹：葉子節點存運算元 (數字/變數)，內部節點存運算元。樹的結構天然體現運算優先級與結合性。

構建算法 (後綴表達式法)

1. 中綴轉後綴 (參考上一篇)。
2. 掃描後綴 Token：
   • 運算元：建立節點入堆疊。
   • 運算元：彈出右子樹、左子樹 (順序重要！)，建立新節點以運算元為根、左右子樹為孩子，再入堆疊。
3. 掃描結束，堆疊頂即為根節點。

Java 完整實現

public class ExpressionTree {

    static class Node {
        String value;
        Node left, right;
        Node(String v) { this.value = v; }
        Node(String v, Node l, Node r) { this.value = v; this.left = l; this.right = r; }
    }

    public static Node build(String infix) {
        String postfix = InfixToPostfix.convert(infix); // 需先實現中綴轉後綴
        Deque<Node> stack = new ArrayDeque<>();

        for (String token : postfix.split("")) { // 單字元 Token 簡化版
            if (token.matches("[a-zA-Z0-9]+")) {
                stack.push(new Node(token));
            } else {
                Node right = stack.pop();
                Node left = stack.pop();
                stack.push(new Node(token, left, right));
            }
        }
        return stack.pop();
    }

    // 三種遍歷
    public static void preOrder(Node root) {  // 根左右 -> 前綴表達式
        if (root == null) return;
        System.out.print(root.value + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void inOrder(Node root) {   // 左根右 -> 中綴表達式 (需加括號邏輯)
        if (root == null) return;
        if (root.left != null) System.out.print("(");
        inOrder(root.left);
        System.out.print(root.value + " ");
        inOrder(root.right);
        if (root.right != null) System.out.print(")");
    }

    public static void postOrder(Node root) { // 左右根 -> 後綴表達式
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value + " ");
    }

    // 計算表達式值 (假設葉子皆為整數)
    public static int evaluate(Node root) {
        if (root.left == null && root.right == null) 
            return Integer.parseInt(root.value);
        int l = evaluate(root.left);
        int r = evaluate(root.right);
        switch (root.value) {
            case "+": return l + r;
            case "-": return l - r;
            case "*": return l * r;
            case "/": return l / r;
            default: throw new IllegalArgumentException("未知運算元: " + root.value);
        }
    }

    public static void main(String[] args) {
        String expr = "45+23*56/2-5";
        Node root = build(expr);
        System.out.print("前序: "); preOrder(root); System.out.println();
        System.out.print("中序: "); inOrder(root); System.out.println();
        System.out.print("後序: "); postOrder(root); System.out.println();
        System.out.println("計算結果: " + evaluate(root));
    }
}

輸出範例

前序: - + 45 / * 23 56 2 5
中序: ( 45 + ( ( 23 * 56 ) / 2 ) - 5 )
後序: 45 23 56 * 2 / + 5 -
計算結果: 648

應用場景

• 編譯器前端：語法樹構建、常量折疊優化。
• 報表引擎：用戶自定義公式解析與計算。
• 規則引擎：動態條件表達式 (如 age > 18 && score >= 60) 的結構化存儲與求值。
• 教學演示：直觀展示運算優先級與結合性。

結語

表達式二叉樹是「中綴→後綴→樹」鏈路的關鍵環節。掌握其構建與遍歷，即掌握了表達式結構化處理的核心能力。實際專案中建議先將輸入 Token 化 (支援多位數、變數、函數)，再套用此框架。