数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中二叉树的序列化与反序列化
假设我们有一棵二叉树，我们需要对其进行序列化和反序列化。众所周知，序列化是将数据结构或对象转换为一系列位流的过程，以便可以将其存储在文件或内存缓冲区中，并在以后在相同或不同的计算机环境中重建。
这里，我们需要设计一种算法来序列化和反序列化二叉树。二叉树是一种根树，其中每个节点最多有两个子节点。
因此，如果输入是这样的：
那么输出将是：序列化 - 1 2 3 4 5 N N N N N N 反序列化树：4 2 5 1 3。
为了解决这个问题，我们将遵循以下步骤：
定义一个序列化函数`serialize()`，它将接收根节点作为参数。
ret := 空字符串
定义一个队列q
将根节点插入到q中
当(q不为空)时，执行：
curr = q的第一个元素
从q中删除该元素
如果curr不可用，则：
ret := ret + "N"
ret := ret + 空格
忽略以下部分，跳到下一个迭代
ret := ret + curr的值
ret := ret + 空格
将curr的左子节点添加到q的末尾
将curr的右子节点添加到q的末尾
返回ret
定义一个反序列化函数`deserialize()`，它将接收数据作为参数。
如果data[0] == 'N'，则：
返回NULL
temp := 空字符串
定义一个数组v
for i := 0 to data.length -1:
如果data[i] == 空格，则：
将temp添加到v的末尾
temp := 空字符串
忽略以下部分，跳到下一个迭代
temp := temp + data[i]
newRoot = 新节点，值为v[0]
定义一个队列q
将newRoot插入到q中
i := 1
当(q不为空且i < v.length)时，执行：
parent = q的第一个元素
从q中删除该元素
如果v[i] != "N"，则：
parent的左子节点 := 新节点，值为v[i]
将parent的左子节点插入到q中
i++
如果v[i] != "N"，则：
parent的右子节点 := 新节点，值为v[i]
将parent的右子节点插入到q中
i++
返回newRoot
示例
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val) {
queue<TreeNode *> q;
q.push(*root);
while (q.size()) {
TreeNode *temp = q.front();
q.pop();
if (!temp->left) {
if (val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}
else {
q.push(temp->left);
}
if (!temp->right) {
if (val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}
else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v) {
TreeNode *root = new TreeNode(v[0]);
for (int i = 1; i < v.size(); i++) {
insert(&root, v[i]);
}
return root;
}
void inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Codec {
public:
string serialize(TreeNode *root) {
string ret = "";
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
TreeNode *curr = q.front();
q.pop();
if (!curr) {
ret += "N";
ret += " ";
continue;
}
ret += to_string(curr->val);
ret += " ";
q.push(curr->left);
q.push(curr->right);
}
return ret;
}
TreeNode *deserialize(string data) {
if (data[0] == 'N')
return NULL;
string temp = "";
vector<string> v;
for (int i = 0; i < data.size(); i++) {
if (data[i] == ' ') {
v.push_back(temp);
temp = "";
continue;
}
temp += data[i];
}
TreeNode *newRoot = new TreeNode(stoi(v[0]));
queue<TreeNode *> q;
q.push(newRoot);
int i = 1;
while (!q.empty() && i < v.size()) {
TreeNode *parent = q.front();
q.pop();
if (v[i] != "N") {
parent->left = new TreeNode(stoi(v[i]));
q.push(parent->left);
}
i++;
if (v[i] != "N") {
parent->right = new TreeNode(stoi(v[i]));
q.push(parent->right);
}
i++;
}
return newRoot;
}
};
main() {
Codec ob;
vector<int> v = {1,2,3,4,5};
TreeNode *root = make_tree(v);
cout << "Given Tree: ";
inord(root);
cout << endl;
string ser = ob.serialize(root);
cout << "Serialize: " << ser << endl;
TreeNode *deser = ob.deserialize(ser);
cout << "Deserialized Tree: ";
inord(root);
}输入
1,2,3,4,5
输出
Given Tree: 4 2 5 1 3 Serialize: 1 2 3 4 5 N N N N N N Deserialized Tree: 4 2 5 1 3
766 次浏览
