Java 實作二元樹鏈式儲存結構：節點定義、遍歷演算法與基本操作完整程式碼

二元樹儲存結構分類

特殊二元樹類型

• 完全二元樹：除最後一層外皆滿，最後一層靠左
• 平衡二元樹 (AVL)：左右子樹高度差 ≤ 1
• 線索二元樹：空指標指向前驅/後繼節點
• 三叉鏈表：含父節點指標
• 二元搜尋樹 (BST)：左<根<右，支援高效查找

節點類別定義

public class TreeNode {
    private int key;
    private String data;
    private boolean visited;
    private TreeNode leftChild;
    private TreeNode rightChild;
    
    public TreeNode() {}
    
    public TreeNode(int key, String data) {
        this.key = key;
        this.data = data;
    }
    // Getter/Setter 略...
}

二元樹核心操作實作

public class BinaryTree {
    private TreeNode root;
    
    public BinaryTree() {
        root = new TreeNode(1, "rootNode(A)");
    }
    
    /** 手動建立測試樹結構
     *        A(1)
     *       / \
     *     B(2) C(3)
     *    / \    \
     *  D(4) E(5) F(6)
     */
    public void createBinTree() {
        TreeNode nodeB = new TreeNode(2, "B");
        TreeNode nodeC = new TreeNode(3, "C");
        TreeNode nodeD = new TreeNode(4, "D");
        TreeNode nodeE = new TreeNode(5, "E");
        TreeNode nodeF = new TreeNode(6, "F");
        
        root.setLeftChild(nodeB);
        root.setRightChild(nodeC);
        nodeB.setLeftChild(nodeD);
        nodeB.setRightChild(nodeE);
        nodeC.setRightChild(nodeF);
    }
    
    // 基本屬性查詢
    public boolean isEmpty() { return root == null; }
    
    public int height() { return height(root); }
    private int height(TreeNode node) {
        if (node == null) return 0;
        return Math.max(height(node.getLeftChild()), height(node.getRightChild())) + 1;
    }
    
    public int size() { return size(root); }
    private int size(TreeNode node) {
        if (node == null) return 0;
        return 1 + size(node.getLeftChild()) + size(node.getRightChild());
    }
    
    // 關係查詢
    public TreeNode parent(TreeNode node) {
        return (root == null || root == node) ? null : parent(root, node);
    }
    private TreeNode parent(TreeNode subTree, TreeNode target) {
        if (subTree == null) return null;
        if (subTree.getLeftChild() == target || subTree.getRightChild() == target) 
            return subTree;
        TreeNode p = parent(subTree.getLeftChild(), target);
        return (p != null) ? p : parent(subTree.getRightChild(), target);
    }
    
    public TreeNode leftChild(TreeNode node) {
        return (node != null) ? node.getLeftChild() : null;
    }
    
    public TreeNode rightChild(TreeNode node) {
        return (node != null) ? node.getRightChild() : null;
    }
    
    // 樹銷毀（後序釋放）
    public void destroy(TreeNode subTree) {
        if (subTree != null) {
            destroy(subTree.getLeftChild());
            destroy(subTree.getRightChild());
            subTree = null; // 釋放引用
        }
    }
}

三種深度優先遍歷演算法

/** 前序遍歷 */
public void preOrder(TreeNode node) {
    if (node != null) {
        visit(node);
        preOrder(node.getLeftChild());
        preOrder(node.getRightChild());
    }
}

/** 中序遍歷 */
public void inOrder(TreeNode node) {
    if (node != null) {
        inOrder(node.getLeftChild());
        visit(node);
        inOrder(node.getRightChild());
    }
}

/** 後序遍歷 */
public void postOrder(TreeNode node) {
    if (node != null) {
        postOrder(node.getLeftChild());
        postOrder(node.getRightChild());
        visit(node);
    }
}

private void visit(TreeNode node) {
    node.setVisited(true);
    System.out.println("Key:" + node.getKey() + " Data:" + node.getData());
}

層序遍歷（廣度優先）

public void levelOrder(TreeNode root) {
    if (root == null) return;
    
    Queue queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        visit(current);
        
        if (current.getLeftChild() != null) queue.offer(current.getLeftChild());
        if (current.getRightChild() != null) queue.offer(current.getRightChild());
    }
}

非遞迴遍歷實作（堆疊模擬）

/** 非遞迴前序遍歷 */
public void preOrderIterative(TreeNode root) {
    if (root == null) return;
    Stack stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        visit(node);
        // 先壓右再壓左，確保左子樹先處理
        if (node.getRightChild() != null) stack.push(node.getRightChild());
        if (node.getLeftChild() != null) stack.push(node.getLeftChild());
    }
}

/** 非遞迴中序遍歷 */
public void inOrderIterative(TreeNode root) {
    Stack stack = new Stack<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.getLeftChild();
        }
        current = stack.pop();
        visit(current);
        current = current.getRightChild();
    }
}

測試驗證

public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.createBinTree();
    
    System.out.println("節點數：" + tree.size());        // 6
    System.out.println("樹高度：" + tree.height());      // 3
    
    System.out.println("=== 前序遍歷 ===");  // A B D E C F
    tree.preOrder(tree.getRoot());
    
    System.out.println("=== 中序遍歷 ===");  // D B E A C F
    tree.inOrder(tree.getRoot());
    
    System.out.println("=== 後序遍歷 ===");  // D E B F C A
    tree.postOrder(tree.getRoot());
    
    System.out.println("=== 層序遍歷 ===");  // A B C D E F
    tree.levelOrder(tree.getRoot());
}

輸出結果驗證

節點數：6
樹高度：3
=== 前序遍歷 ===
Key:1 Data:rootNode(A)
Key:2 Data:B
Key:4 Data:D
Key:5 Data:E
Key:3 Data:C
Key:6 Data:F
=== 中序遍歷 ===
Key:4 Data:D
Key:2 Data:B
Key:5 Data:E
Key:1 Data:rootNode(A)
Key:3 Data:C
Key:6 Data:F
=== 後序遍歷 ===
Key:4 Data:D
Key:5 Data:E
Key:2 Data:B
Key:6 Data:F
Key:3 Data:C
Key:1 Data:rootNode(A)
=== 層序遍歷 ===
Key:1 Data:rootNode(A)
Key:2 Data:B
Key:3 Data:C
Key:4 Data:D
Key:5 Data:E
Key:6 Data:F