排序二叉樹線索化：雙向鏈表加速區間刪除與順序訪問

排序二叉樹（BST）雖擁有優異的單點查找性能，但面對區間操作（如批量刪除某範圍節點）時極其低效：需逐一查找、驗證、刪除，重複遍歷造成極大浪費。解決之道是將 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;

插入時維護線索鏈表

新節點插入後，需根據其作為左/右孩子的身分，正確串接 prev/next：

void set_link_for_insert(TREE_NODE* pParent, TREE_NODE* pNode) {
    if (NULL == pParent || NULL == pNode) return;
    
    if (pNode == pParent->left) {  // 作為左孩子插入
        pNode->prev = pParent->prev;
        if (pParent->prev) pParent->prev->next = pNode;
        pNode->next = pParent;
        pParent->prev = pNode;
    } 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;
    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;  // 去重
    
    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; }
        }
    }
    set_link_for_insert(pHead, pNode);  // 關鍵：維護線索
    return TRUE;
}

刪除時修復線索鏈表

刪除節點前，先將其從雙向鏈表中摘除：

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;
    }
}

刪除邏輯處理四種情況（無子、單左、單右、雙子），雙子情況下採用左子樹最大節點替換法：

TREE_NODE* _delete_node_from_tree(TREE_NODE* root, TREE_NODE* pNode) {
    TREE_NODE *pLeftMax, *pLeftMaxParent, *pParent = get_parent_of_one(root, pNode);
    
    if (!pNode->left && !pNode->right) {                    // 葉節點
        (pNode == pParent->left) ? pParent->left = NULL : pParent->right = NULL;
    } else if (pNode->left && !pNode->right) {              // 僅有左子
        (pNode == pParent->left) ? pParent->left = pNode->left : pParent->right = pNode->left;
    } else if (!pNode->left && pNode->right) {              // 僅有右子
        (pNode == pParent->left) ? pParent->left = pNode->right : pParent->right = pNode->right;
    } else {                                                // 雙子：左子樹最大節點頂替
        pLeftMax = get_max_node_of_one(pNode->left);
        if (pLeftMax == pNode->left) {
            pNode->left->right = pNode->right;
            (pNode == pParent->left) ? pParent->left = pNode->left : pParent->right = pNode->left;
        } else {
            pLeftMaxParent = get_parent_of_one(root, pLeftMax);
            pNode->data = pLeftMax->data;  // 資料覆蓋
            pLeftMaxParent->right = NULL;
            pNode = pLeftMax;              // 實際刪除 pLeftMax
        }
    }
    return pNode;  // 返回實際被刪除節點，供線索修復使用
}

完整刪除入口：

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;
    
    if (pNode == *ppTreeNode) {  // 刪除根節點特殊處理
        // ...（處理根節點四種情況，略）...
        goto final;
    }
    
    pNode = _delete_node_from_tree(*ppTreeNode, pNode);
    
final:
    set_link_for_delete(pNode);  // 關鍵：修復線索
    free(pNode);
    return TRUE;
}

輔助函數：尋找最大節點與父節點

TREE_NODE* get_max_node_of_one(TREE_NODE* pNode) {
    if (!pNode) return NULL;
    while (pNode->right) pNode = pNode->right;
    return pNode;
}

TREE_NODE* get_parent_of_one(TREE_NODE* root, TREE_NODE* pNode) {
    if (!root || !pNode) return NULL;
    while (root) {
        if (pNode == root->left || pNode == root->right) return root;
        root = (pNode->data < root->data) ? root->left : root->right;
    }
    return NULL;
}

總結與心得

1. 空間換時間：兩個指標換取 O(1) 區間遍歷與批量操作能力
2. 維護複雜度：插入/刪除需同步維護樹結構與雙向鏈表，邏輯較繁瑣
3. 實戰價值：適用於頻繁區間查詢、範圍刪除、順序迭代的場景（如資料庫索引、時間序列資料）
4. 測試關鍵：邊界條件（首/尾節點）、雙子刪除替換邏輯、線索斷裂修復

線索二叉樹是「資料結構增強」的經典案例，掌握其維護邏輯有助於理解更複雜的 B+ 樹、跳表等結構設計。