二叉樹鏈式存儲與遍歷算法全解析（遞歸與非遞歸實現）

1. 鏈式存儲結構

順序存儲空間利用率低，二叉樹通常採用二叉鏈表：每個節點包含數據域 data、左指針 lchild、右指針 rchild。若再加父指針則為三叉鏈表。

private static class Node {
    Integer data;
    Node lchild, rchild;
}

2. 從完全二叉樹序列構建樹

輸入先序序列，空節點用 0 表示（如 1,2,3,4,0,5,7,8）。利用完全二叉樹性質：索引 i 的左子節點為 2i，右子節點為 2i+1，遞歸構建。

public Node build(int index) {
    if (index > n) return null;
    Integer val = nodes[index - 1];
    if (val == 0) return null;
    Node node = new Node();
    node.data = val;
    node.lchild = build(2 * index);
    node.rchild = build(2 * index + 1);
    return node;
}

3. 遍歷算法

3.1 層次遍歷（廣度優先）

借助隊列，先入根節點，循環出隊訪問，將非空左右子節點入隊。

public void levelOrder(Node root) {
    Queue q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        Node cur = q.poll();
        System.out.print(cur.data + " ");
        if (cur.lchild != null) q.offer(cur.lchild);
        if (cur.rchild != null) q.offer(cur.rchild);
    }
}

3.2 先序遍歷（根-左-右）

遞歸版

public void preOrderRecur(Node node) {
    if (node == null) return;
    System.out.print(node.data + " ");
    preOrderRecur(node.lchild);
    preOrderRecur(node.rchild);
}

非遞歸版（棧模擬）

方法一：先壓右再壓左，保證左子樹先出棧。

public void preOrder(Node root) {
    Stack st = new Stack<>();
    st.push(root);
    while (!st.isEmpty()) {
        Node cur = st.pop();
        System.out.print(cur.data + " ");
        if (cur.rchild != null) st.push(cur.rchild);
        if (cur.lchild != null) st.push(cur.lchild);
    }
}

方法二：沿左鏈入棧，彈出後轉向右子樹。

public void preOrderOne(Node root) {
    Stack st = new Stack<>();
    Node cur = root;
    while (cur != null || !st.isEmpty()) {
        while (cur != null) {
            System.out.print(cur.data + " ");
            st.push(cur);
            cur = cur.lchild;
        }
        cur = st.pop().rchild;
    }
}

3.3 中序遍歷（左-根-右）

遞歸版

public void inOrderRecur(Node node) {
    if (node == null) return;
    inOrderRecur(node.lchild);
    System.out.print(node.data + " ");
    inOrderRecur(node.rchild);
}

非遞歸版

public void inOrder(Node root) {
    Stack st = new Stack<>();
    Node cur = root;
    while (cur != null || !st.isEmpty()) {
        while (cur != null) {
            st.push(cur);
            cur = cur.lchild;
        }
        cur = st.pop();
        System.out.print(cur.data + " ");
        cur = cur.rchild;
    }
}

3.4 後序遍歷（左-右-根）

遞歸版

public void postOrderRecur(Node node) {
    if (node == null) return;
    postOrderRecur(node.lchild);
    postOrderRecur(node.rchild);
    System.out.print(node.data + " ");
}

非遞歸版（單棧 + 前驅指針）

public void postOrder(Node root) {
    Stack st = new Stack<>();
    Node pre = null; // 記錄上一次訪問的節點
    Node cur = root;
    while (cur != null || !st.isEmpty()) {
        while (cur != null) {
            st.push(cur);
            cur = cur.lchild;
        }
        Node top = st.peek();
        // 若右子樹為空或已訪問過，則訪問當前節點
        if (top.rchild == null || pre == top.rchild) {
            System.out.print(top.data + " ");
            pre = st.pop();
        } else {
            cur = top.rchild;
        }
    }
}

4. 測試與輸出

輸入序列 1,2,3,4,0,5,7,8 對應樹結構：

        1
       / \
      2   3
     /   / \
    4   5   7
         \
          8

運行結果：

先序遍歷(遞歸)：1 2 4 3 5 8 7
中序遍歷(遞歸)：4 2 1 5 8 3 7
後序遍歷(遞歸)：4 2 8 5 7 3 1
層次遍歷：1 2 3 4 5 7 8
先序遍歷(非遞歸)：1 2 4 3 5 8 7
中序遍歷(非遞歸)：4 2 1 5 8 3 7
後序遍歷(非遞歸)：4 2 8 5 7 3 1

5. 總結

• 鏈式存儲靈活，適合動態樹結構。
• 遞歸代碼簡潔，但深度過大可能棧溢出；非遞歸用棧模擬，可控性強。
• 後序非遞歸最複雜，關鍵在於判斷右子樹是否已訪問（pre 指針法）。
• 層次遍歷必須用隊列，體現 BFS 思想。