Java 數據結構：二叉樹完整實現（接口、節點、遍歷、堆疊非遞歸）

從接口定義、節點類、樹構建到中序遍歷（遞歸與堆疊非遞歸雙實現），完整展示 Java 泛型二叉樹核心代碼，適合數據結構教學與面試刷題參考。

1. 二叉樹接口定義

public interface BinaryTreeInterface<T> {
    T getRootData();
    int getHeight();
    int getNumberOfNodes();
    void clear();
    void setTree(T rootData);
    void setTree(T rootData, BinaryTreeInterface<T> left, BinaryTreeInterface<T> right);
}

2. 節點類

public class BinaryNode<T> {
    private T data;
    private BinaryNode<T> left, right;

    public BinaryNode() { this(null); }
    public BinaryNode(T data) { this(data, null, null); }
    public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
        this.data = data; this.left = left; this.right = right;
    }

    // getter/setter 省略
    public boolean hasLeft() { return left != null; }
    public boolean hasRight() { return right != null; }
    public boolean isLeaf() { return left == null && right == null; }

    // 遞歸計算高度
    public int getHeight() { return getHeight(this); }
    private int getHeight(BinaryNode<T> node) {
        if (node == null) return 0;
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }

    // 遞歸計算節點數
    public int getNumberOfNodes() {
        int leftNum = left != null ? left.getNumberOfNodes() : 0;
        int rightNum = right != null ? right.getNumberOfNodes() : 0;
        return leftNum + rightNum + 1;
    }
}

3. 二叉樹實現類

public class BinaryTree<T> implements BinaryTreeInterface<T> {
    private BinaryNode<T> root;

    public BinaryTree() { root = null; }
    public BinaryTree(T rootData) { root = new BinaryNode<>(rootData); }
    public BinaryTree(T rootData, BinaryTree<T> left, BinaryTree<T> right) {
        root = new BinaryNode<>(rootData);
        if (left != null) root.setLeft(left.root);
        if (right != null) root.setRight(right.root);
    }

    // 接口方法實現
    public void setTree(T rootData) { root = new BinaryNode<>(rootData); }
    public void setTree(T rootData, BinaryTreeInterface<T> left, BinaryTreeInterface<T> right) {
        root = new BinaryNode<>(rootData);
        if (left instanceof BinaryTree) root.setLeft(((BinaryTree<T>)left).root);
        if (right instanceof BinaryTree) root.setRight(((BinaryTree<T>)right).root);
    }
    public void clear() { root = null; }
    public T getRootData() { return root != null ? root.getData() : null; }
    public int getHeight() { return root != null ? root.getHeight() : 0; }
    public int getNumberOfNodes() { return root != null ? root.getNumberOfNodes() : 0; }

    // 遞歸中序遍歷
    public void inOrderTraverse() { inOrderTraverse(root); }
    private void inOrderTraverse(BinaryNode<T> node) {
        if (node != null) {
            inOrderTraverse(node.getLeft());
            System.out.println(node.getData());
            inOrderTraverse(node.getRight());
        }
    }

    // 堆疊非遞歸中序遍歷（顯式堆疊模擬調用棧）
    public void inOrderStackTraverse() {
        Stack<BinaryNode<T>> stack = new Stack<>();
        BinaryNode<T> cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.getLeft();
            }
            if (!stack.isEmpty()) {
                BinaryNode<T> tmp = stack.pop();
                System.out.println(tmp.getData());
                cur = tmp.getRight();
            }
        }
    }

    // 測試主方法
    public static void main(String[] args) {
        BinaryTree<String> t = new BinaryTree<>();
        BinaryTree<String> t7 = new BinaryTree<>("7");
        BinaryTree<String> t8 = new BinaryTree<>("8");
        t.setTree("6", t7, t8);      //      6
                                     //     / \
                                     //    7   8
        t.inOrderStackTraverse();    // 輸出: 7, 6, 8
        System.out.println("Height: " + t.getHeight()); // 2
    }
}

核心要點總結

• 泛型設計：支援任意數據類型元素
• 組合而非繼承：樹持有根節點引用，節點持有左右子節點引用
• 雙遍歷實現：遞歸簡潔但受棧深度限制；堆疊非遞歸適合深度樹、可中斷恢復
• 高度與節點數：均採用後序遞歸思想，自底向上聚合

擴展練習建議

1. 實現前序、後序、層序遍歷（遞歸 + 非遞歸）
2. 新增「查找節點」「刪除節點」「鏡像翻轉」「判斷平衡樹」方法
3. 實現二叉搜索樹（BST）插入/刪除/查找邏輯
4. 嘗試莫里斯遍歷（O(1) 空間中序遍歷）

扎實掌握二叉樹操作，是攻克樹類算法題的基石。