C 語言二叉樹轉鏈表：遞歸後序遍歷的精妙實現

釐清誤區：list_from_tree 是「樹轉列表」，非「建樹」

代碼中的 list_from_tree 函數**不是構建二叉樹**，而是將已建好的二叉樹，按 **右-根-左** 的逆中序遍歷順序，轉換為單向鏈表。主函數中樹的建立是靠 new_tnode 手動串聯完成的。

遞歸邏輯深度解析

Lnode *list_from_tree(Tnode *root, Lnode *list) {
    if (root == NULL) return list;           // 終止條件：空節點直接返回當前列表尾部

    // 1. 先處理右子樹，返回右子樹轉換後的列表頭（即當前子樹中最大值節點）
    Lnode *right = list_from_tree(root->right, list);

    // 2. 建立當前根節點對應的鏈表節點，接在右子樹列表之後
    Lnode *new = new_node(root->data);
    new->next = right;

    // 3. 處理左子樹，將新節點作為左子樹轉換的「尾部」傳入
    //    左子樹所有節點值均小於根節點，應排在根節點之前
    Lnode *left = list_from_tree(root->left, new);

    return left; // 返回整個子樹轉換後的列表頭（最小值節點）
}

執行流程圖解（以示例樹為例）

       6
     /   \
    5     8
         / \
        7   9

1. 遞歸到最右節點 9：右子樹為空，返回 list (NULL) → 建節點 9 → 左子樹空 → 返回 9。
2. 回到 8：右子樹返回 9 → 建節點 8 → 8->next=9 → 遞歸左子樹 7 → 返回 7->8->9。
3. 回到 6：右子樹返回 7-8-9 → 建節點 6 → 6->next=7 → 遞歸左子樹 5 → 返回 5-6-7-8-9。

最終鏈表順序：5 → 6 → 7 → 8 → 9（升序），完美對應二叉搜尋樹的中序遍歷。

關鍵設計點

• 參數 list 代表「已構建部分的列表尾部」：遞歸時層層傳遞，實現「就地拼接」，無需額外合併步驟。
• 順序：右 → 根 → 左：因為鏈表是單向且從小到大，必須先生成大值節點（右），再插入根，最後生成小值節點（左）接在頭部。
• 尾遞歸優化潛力：編譯器若支援尾呼叫優化，可避免棧溢出（C 標準不保證）。

常見變體

• 若需降序列表：改為 左 → 根 → 右 遍歷。
• 若樹非 BST：輸出順序取決於遍歷順序，不再保證有序。
• 雙向鏈表：節點增加 prev 指針，遞歸時同步維護。

這段代碼展示了指針操作與遞歸思維的完美結合，是掌握樹形結構轉換的經典教材。