C语言二叉树的序列化和反序列化
时间: 2023-06-19 20:05:54 浏览: 58
二叉树的序列化指的是将二叉树转换为字符串格式的过程,反序列化则是将字符串格式的二叉树转换为二叉树的过程。在C语言中,可以通过递归的方式实现二叉树的序列化和反序列化。
下面是一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 将二叉树序列化为字符串
void serialize(TreeNode* root, char* str) {
if (root == NULL) {
strcat(str, "# ");
return;
}
char val[10];
sprintf(val, "%d ", root->val);
strcat(str, val);
serialize(root->left, str);
serialize(root->right, str);
}
// 将字符串反序列化为二叉树
TreeNode* deserialize(char* str) {
if (*str == '#') {
str += 2;
return NULL;
}
int val = 0;
while (*str != ' ') {
val = val * 10 + (*str - '0');
str++;
}
str++;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = deserialize(str);
root->right = deserialize(str);
return root;
}
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 str[100];
memset(str, 0, sizeof(str));
serialize(root, str);
printf("序列化后的结果:%s\n", str);
// 将字符串反序列化为二叉树
TreeNode* newRoot = deserialize(str);
printf("反序列化后的结果:%d %d %d %d %d\n", newRoot->val, newRoot->left->val, newRoot->right->val, newRoot->right->left->val, newRoot->right->right->val);
return 0;
}
```
该示例代码中,我们定义了一个结构体`TreeNode`,其中包括节点值`val`、左子节点`left`和右子节点`right`。`serialize`函数用于将二叉树序列化为字符串,参数`root`为根节点指针,`str`为存储字符串的指针。`deserialize`函数用于将字符串反序列化为二叉树,参数`str`为待反序列化的字符串。
在`serialize`函数中,我们首先判断根节点是否为空,若为空,则在字符串中加上`#`表示空节点。若不为空,则将节点值转换为字符串格式,并将其加入字符串中。然后递归调用左子树和右子树进行序列化。
在`deserialize`函数中,我们首先判断当前字符是否为`#`,若是,则表示当前节点为空,直接返回NULL。若不是,则读取节点值,并创建新的节点。然后递归调用左子树和右子树进行反序列化。
最后,在`main`函数中,我们构造一个二叉树,并将其序列化为字符串。然后将字符串反序列化为二叉树,并输出结果。