排序二叉樹持久化：基於陣列索引的序列化儲存與載入技術

排序二叉樹（BST）因優異的插入、刪除、查找特性（平均 O(log n)），廣泛應用於工程開發。但其指標密集的結構導致序列化儲存較為棘手：指標位址在記憶體間不具持久性，直接寫入磁碟無效。本文介紹一種基於完全二叉樹索引映射的儲存方案，巧妙利用父子節點索引關係，實現高效序列化與反序列化。

核心洞察：完全二叉樹索引規律

若將二叉樹視為完全二叉樹，節點按層序編號（根節點為 1），則任一節點 n 的：

• 左子節點索引 = 2n
• 右子節點索引 = 2n + 1
• 父節點索引 = n / 2（整數除法）

雖然 BST 實際結構稀疏，但此索引關係依然成立。我們只需在節點中記錄此「邏輯索引」，即可重建指標關係。

節點結構擴展

typedef struct _TREE_NODE {
    int data;
    int number;                    // 邏輯索引（層序編號）
    struct _TREE_NODE* left_child;
    struct _TREE_NODE* right_child;
} TREE_NODE;

插入時同步分配索引

STATUS _insert_node_into_tree(TREE_NODE* pTreeNode, int data) {
    TREE_NODE* pNode;
    while (1) {
        if (data < pTreeNode->data) {
            if (NULL == pTreeNode->left_child) {
                pNode = create_tree_node(data);
                assert(NULL != pNode);
                pNode->number = pTreeNode->number << 1;        // 父索引 * 2
                pTreeNode->left_child = pNode;
                break;
            } else {
                pTreeNode = pTreeNode->left_child;
            }
        } else {
            if (NULL == pTreeNode->right_child) {
                pNode = create_tree_node(data);
                assert(NULL != pNode);
                pNode->number = (pTreeNode->number << 1) + 1;  // 父索引 * 2 + 1
                pTreeNode->right_child = pNode;
                break;
            } else {
                pTreeNode = pTreeNode->right_child;
            }
        }
    }
    return TRUE;
}

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data) {
    if (NULL == ppTreeNode) return FALSE;
    if (NULL == *ppTreeNode) {
        *ppTreeNode = (TREE_NODE*)create_tree_node(data);
        assert(NULL != *ppTreeNode);
        (*ppTreeNode)->number = 1;  // 根節點索引固定為 1
        return TRUE;
    }
    return _insert_node_into_tree(*ppTreeNode, data);
}

磁碟儲存格式

遍歷樹時，僅需將每個節點的 (data, number) 對寫入磁碟：

typedef struct _DATA {
    int data;
    int number;
} DATA;

四步驟載入重建

1. 分配記憶體：依節點總數 n，分配 n * sizeof(TREE_NODE) 連續空間
2. 還原節點資料：依序讀取 DATA 陣列，填充 TREE_NODE 的 data 與 number，left/right 暫設為 NULL
3. 重建指標關係：對每個節點 n，尋找父節點 n >> 1，根據 n % 2 判斷左/右子節點，填充父節點對應指標
4. 定位根節點：索引為 1 的節點即為根節點，載入完成

優缺點分析

此法適用於配置樹、決策樹等結構相對固定的場景。動態高頻更新場景建議採用前序遍歷+空節點標記等通用序列化方案。