二元搜尋樹線索化實作：雙向鏈表優化遍歷與刪除效能

編輯：關於C語言

動機：為何需要線索化？

標準二元搜尋樹（BST）僅有左右子節點指標。若需刪除一段範圍資料或中序遍歷輸出，必須反覆從根節點搜尋或遞歸回溯，效率低下。解決方案：在節點中新增前驅（`prev`）與後繼（`next`）指標，將樹轉化為雙向鏈表，實現 O(1) 存取前後節點。

節點結構定義

typedef struct _TREE_NODE {
    int data;
    struct _TREE_NODE* prev;   // 中序前驅
    struct _TREE_NODE* next;   // 中序後繼
    struct _TREE_NODE* left;   // 左子樹
    struct _TREE_NODE* right;  // 右子樹
} TREE_NODE;

核心操作：插入時維護雙向鏈表

插入新節點 `pNode` 到父節點 `pParent` 後，需根據 `pNode` 是左還是右孩子，修補四條指標關係。

void set_link_for_insert(TREE_NODE* pParent, TREE_NODE* pNode) {
    if (NULL == pParent || NULL == pNode) return;

    // 情況 1：pNode 是左孩子 → 它的前驅是 pParent 的前驅，後繼是 pParent
    if (pNode == pParent->left) {
        pNode->prev = pParent->prev;
        if (pParent->prev) pParent->prev->next = pNode;
        pNode->next = pParent;
        pParent->prev = pNode;
    }
    // 情況 2：pNode 是右孩子 → 它的前驅是 pParent，後繼是 pParent 的後繼
    else {
        pNode->next = pParent->next;
        if (pParent->next) pParent->next->prev = pNode;
        pNode->prev = pParent;
        pParent->next = pNode;
    }
}

完整插入流程（迭代版）

STATUS add_node_into_tree(TREE_NODE** ppTreeNode, int data) {
    TREE_NODE *pHead = *ppTreeNode, *pNode = NULL;

    if (NULL == ppTreeNode) return FALSE;
    if (NULL == *ppTreeNode) {
        *ppTreeNode = create_new_node(data);
        return TRUE;
    }
    if (NULL != find_data_in_tree(*ppTreeNode, data)) return FALSE; // 重複值

    // 1. 尋找插入位置
    while (1) {
        if (data < pHead->data) {
            if (pHead->left) pHead = pHead->left;
            else { pNode = create_new_node(data); pHead->left = pNode; break; }
        } else {
            if (pHead->right) pHead = pHead->right;
            else { pNode = create_new_node(data); pHead->right = pNode; break; }
        }
    }

    // 2. 維護雙向鏈表
    set_link_for_insert(pHead, pNode);
    return TRUE;
}

核心操作：刪除時維護雙向鏈表

刪除節點 `pNode` 時，只需將其前驅與後繼直接鏈接，跳過 `pNode`。

void set_link_for_delete(TREE_NODE* pNode) {
    if (pNode->prev) {
        if (pNode->next) { // 一般節點：前後都有
            pNode->prev->next = pNode->next;
            pNode->next->prev = pNode->prev;
        } else { // 尾節點：無後繼
            pNode->prev->next = NULL;
        }
    } else if (pNode->next) { // 頭節點：無前驅
        pNode->next->prev = NULL;
    }
    // 若前驅後繼皆無，為唯一節點，無需操作
}

刪除節點完整邏輯（含樹結構調整）

刪除分四種情況：葉節點、單左子、單右子、雙子節點（找左子樹最大值替代）。刪除完成後呼叫 `set_link_for_delete` 修補鏈表。

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data) {
    TREE_NODE *pNode, *pLeftMax, *pLeftMaxParent;

    if (NULL == ppTreeNode || NULL == *ppTreeNode) return FALSE;
    if (NULL == (pNode = find_data_in_tree(*ppTreeNode, data))) return FALSE;

    // 1. 處理根節點刪除（特殊邏輯，需更新 *ppTreeNode）
    if (pNode == *ppTreeNode) {
        // ... 根節點刪除邏輯（參考原碼：處理左右子樹接管、左子樹最大值替代） ...
        goto final; // 統一跳轉至鏈表修補與釋放
    }

    // 2. 非根節點刪除（遞歸/迭代調整樹結構）
    pNode = _delete_node_from_tree(*ppTreeNode, pNode);

final:
    set_link_for_delete(pNode); // 關鍵：修補雙向鏈表
    free(pNode);
    return TRUE;
}

輔助函式 `get_max_node_of_one`（找左子樹最大值）與 `get_parent_of_one`（找父節點）為刪除邏輯核心工具。