二叉树的序列化和反序列化用c语言

二叉树的序列化和反序列化可以使用前序遍历来实现。

序列化：

前序遍历二叉树，对于每个节点，如果该节点不为空，输出节点的值，并将其左右子树分别递归进行序列化；如果该节点为空，输出特定值（如“#”）表示空节点。

反序列化：

读取序列化字符串，对于每个字符，如果为“#”表示当前节点为空，返回空节点；否则将当前字符解析为节点值，创建新节点，并递归读取左右子树进行反序列化。

以下是示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 1024

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

char* serialize(TreeNode* root) {
    if (root == NULL) {
        return strdup("#");
    }
    char* left = serialize(root->left);
    char* right = serialize(root->right);
    char* res = (char*)malloc(strlen(left) + strlen(right) + 16);
    sprintf(res, "%d%s%s", root->val, left, right);
    free(left);
    free(right);
    return res;
}

TreeNode* deserialize(char* data, int* index) {
    if (data[*index] == '#' || data[*index] == '\0') {
        (*index)++;
        return NULL;
    }
    int val = 0;
    while (data[*index] >= '0' && data[*index] <= '9') {
        val = val * 10 + data[*index] - '0';
        (*index)++;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = deserialize(data, index);
    root->right = deserialize(data, index);
    return root;
}

void print_tree(TreeNode* root) {
    if (root == NULL) {
        printf("# ");
        return;
    }
    printf("%d ", root->val);
    print_tree(root->left);
    print_tree(root->right);
}

int main() {
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    char* data = serialize(root);
    printf("%s\n", data);
    int index = 0;
    TreeNode* new_root = deserialize(data, &index);
    print_tree(new_root);
    printf("\n");

    free(data);
    free(root->left);
    free(root->right->left);
    free(root->right->right);
    free(root->right);
    free(root);
    free(new_root->left);
    free(new_root->right);
    free(new_root);

    return 0;
}