二元搜尋樹序列化儲存與載入：陣列索引映射法實作指南

問題：指標難以直接序列化

二元樹節點含多指標（左、右、父），直接寫入硬碟無意義（記憶體位址下次載入失效）。需將樹結構轉為無指標的純資料結構儲存。

解決方案：堆積式陣列索引映射

借鑒二元堆積（Binary Heap）的陣列表示法：

• 根節點編號 = 1
• 左子節點編號 = 父編號 × 2
• 右子節點編號 = 父編號 × 2 + 1

即使樹非完全二元樹（稀疏），編號規則依然成立。儲存時只存「有效節點的 (資料, 編號)」，載入時依編號重建指標關係。

節點結構擴充

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

磁碟資料結構

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

遍歷樹（任意順序），將每個節點的 `data` 與 `number` 依序寫入檔案。另需記錄總節點數 `count`。

四步驟載入還原

1. 分配記憶體：根據 `count` 分配 `TREE_NODE` 陣列 `nodes[count]`。
2. 填充資料：讀取檔案每筆 `DATA`，複製至 `nodes[i]`，`left_child`/`right_child` 暫設 `NULL`。
3. 重建指標：遍歷陣列 `i = 1 ~ count-1`（對應編號 `n = i+1`）：
   • 父節點索引 = `parent_idx = (n >> 1) - 1`（即 `n/2 - 1`）。
   • 若 `n % 2 == 0` → `nodes[parent_idx].left_child = &nodes[i]`；否則 → `right_child`。
4. 取得根節點：`root = &nodes[0]`（編號 1），載入完成。

程式碼骨架

TREE_NODE* load_tree_from_disk(FILE* fp, int count) {
    // 1. 分配
    TREE_NODE* nodes = (TREE_NODE*)malloc(count * sizeof(TREE_NODE));
    DATA* disk_data = (DATA*)malloc(count * sizeof(DATA));
    fread(disk_data, sizeof(DATA), count, fp);

    // 2. 填充
    for (int i = 0; i < count; ++i) {
        nodes[i].data = disk_data[i].data;
        nodes[i].number = disk_data[i].number;
        nodes[i].left_child = nodes[i].right_child = NULL;
    }

    // 3. 重建連結
    for (int i = 1; i < count; ++i) { // 從編號 2 開始
        int n = nodes[i].number;
        int parent_idx = (n >> 1) - 1;
        if (n % 2 == 0)
            nodes[parent_idx].left_child = &nodes[i];
        else
            nodes[parent_idx].right_child = &nodes[i];
    }

    free(disk_data);
    return &nodes[0]; // 根節點
}

優缺點分析

改進方向

• 使用 64 位元 `long long` 儲存編號。
• 採用前序遍歷 + 空節點標記（如 `#`）序列化，空間效率更高，通用性更強。