C语言二叉树反序列化（从字符串重建二叉树的完整教程）

什么是二叉树的序列化与反序列化？

- 序列化：将内存中的二叉树转换成字符串（如 "1,2,#,3,#,#,#"），便于存储或传输。
- 反序列化：将该字符串重新构建成原来的二叉树结构。

我们通常使用前序遍历（根-左-右）的方式进行序列化，并用特殊符号（如 #）表示空节点。

第一步：定义二叉树节点结构

在 C 语言中，首先需要定义一个二叉树节点：

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;} TreeNode;// 辅助函数：创建新节点TreeNode* createNode(int val) {    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));    node->val = val;    node->left = NULL;    node->right = NULL;    return node;}

第二步：实现反序列化函数

我们将使用递归方式解析字符串。假设输入字符串格式为："1,2,#,3,#,#,#"，其中 # 表示空节点。

思路：
1. 将字符串按逗号分割成数组；
2. 使用一个全局索引记录当前处理到哪个元素；
3. 递归构建左右子树。

// 全局索引，用于跟踪当前解析位置int index = 0;// 分割字符串为 tokenschar** splitString(const char* s, int* size) {    char* str = strdup(s);    char** tokens = malloc(strlen(str) * sizeof(char*));    char* token = strtok(str, ",");    *size = 0;    while (token != NULL) {        tokens[(*size)++] = strdup(token);        token = strtok(NULL, ",");    }    free(str);    return tokens;}// 反序列化核心函数TreeNode* deserializeHelper(char** tokens, int size) {    if (index >= size || strcmp(tokens[index], "#") == 0) {        index++;        return NULL;    }    TreeNode* root = createNode(atoi(tokens[index]));    index++;    root->left = deserializeHelper(tokens, size);    root->right = deserializeHelper(tokens, size);    return root;}// 对外接口TreeNode* deserialize(const char* data) {    if (data == NULL || strlen(data) == 0) return NULL;        int size;    char** tokens = splitString(data, &size);    index = 0; // 重置索引    TreeNode* root = deserializeHelper(tokens, size);        // 清理内存    for (int i = 0; i < size; i++) {        free(tokens[i]);    }    free(tokens);        return root;}

第三步：测试你的反序列化函数

下面是一个完整的测试示例：

// 前序遍历打印（用于验证）void preorderPrint(TreeNode* root) {    if (root == NULL) {        printf("# ");        return;    }    printf("%d ", root->val);    preorderPrint(root->left);    preorderPrint(root->right);}int main() {    const char* serialized = "1,2,#,3,#,#,#";    printf("原始序列化字符串: %s\n", serialized);        TreeNode* root = deserialize(serialized);    printf("反序列化后前序遍历: ");    preorderPrint(root);    printf("\n");        return 0;}

常见问题与注意事项

• 确保输入字符串格式正确，逗号分隔，空节点用 # 表示。
• 注意内存管理：动态分配的内存要记得释放，避免内存泄漏。
• 全局变量 index 在多线程环境中不安全，实际项目中建议封装为结构体成员。

总结

通过本教程，你已经掌握了 C语言实现反序列化 的基本方法，并理解了 二叉树重建算法 的核心逻辑。这项技能不仅对面试有帮助，也能提升你对数据结构和递归的理解。

动手试试吧！修改序列化字符串，看看能否正确重建不同的二叉树结构。

关键词：C语言二叉树反序列化、二叉树序列化与反序列化、C语言实现反序列化、二叉树重建算法