数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中N元树的序列化和反序列化
假设我们有一棵N元树，我们需要对其进行序列化和反序列化。众所周知，序列化是将数据结构或对象转换为一系列比特的过程，以便我们可以将其存储在文件或内存缓冲区中，并在以后在相同或不同的计算机环境中重建它。
这里我们需要设计一个算法来序列化和反序列化N元树。N元树是一棵根树，其中每个节点最多有N个子节点。
因此，如果输入如下所示：
则输出将是序列化：1 #3 2 4 #5 6 ##### 反序列化树：1[3[5, 6, ], 2, 4, ]
为了解决这个问题，我们将遵循以下步骤：
定义一个函数`createVector()`，它将接收s作为参数。
定义一个二维数组`ret`
定义一个数组`tempv`
`temp :=`空字符串
从`i := 0`开始循环，当`i < s`的长度时，更新（将i加1），执行：
如果`s[i]`不等于空格并且`s[i]`不等于'#'，则：
`temp := temp + s[i]`
否则，如果`s[i]`等于空格，则：
将`temp`转换为整数，并将其添加到`tempv`的末尾。
`temp :=`空字符串
否则，如果`s[i]`等于'#'，则：
将`tempv`添加到`ret`的末尾。
`temp :=`空字符串
清空`tempv`。
当`ret`不为空且`ret`的最后一个元素等于0时，执行：
从`ret`中删除最后一个元素。
返回`ret`。
定义一个函数`serialize()`，它将接收根节点作为参数。
`ret :=`空字符串
如果根节点不为空，则：
返回`ret`。
定义一个队列`q`。
将根节点插入到`q`中。
`rret := ret`连接根节点的值。
`ret := ret`连接空格。
`ret := ret`连接"#"
当`q`不为空时，执行：
`curr = q`的第一个元素。
从`q`中删除元素。
从`i := 0`开始循环，当`i < curr`的子节点数组的大小时，更新（将i加1），执行：
如果`curr`的`children[i]`存在，则：
`ret := ret`连接`curr`的`children[i]`。
将`curr`的`children[i]`插入到`q`中。
`ret := ret +`空格
`ret := ret`连接"#"
返回`ret`。
定义一个函数`deserialize()`，它将接收数据作为参数。
如果数据的长度等于0，则：
返回`null`。
定义一个二维数组`v := createVector(data)`。
`ret :=`一个值为`v[0, 0]`的新节点。
定义一个队列`q`。
将`ret`插入到`q`中。
`i := 1`
当`q`不为空且`i − v`的长度时，执行：
`curr = q`的第一个元素。
从`q`中删除元素。
从`j := 0`开始循环，当`j − v[i]`的长度时，更新（将j加1），执行：
`node := v[i, j]`
`temp =`一个值为`node`的新节点。
将`temp`添加到`curr`的子节点的末尾。
将`temp`插入到`q`中。
将`i`加1。
返回`ret`。
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
string n_ary_to_str(Node *root){
string ret = "";
if(root){
ret = ret + to_string(root->val);
if(root->children.size() > 0){
ret += "[";
for(Node* child : root->children){
ret += n_ary_to_str(child) + ", ";
}
ret += "]";
}
}
return ret;
}
class Codec {
public:
vector<vector<int>>createVector(string s) {
vector<vector<int>> ret;
vector<int> tempv;
string temp = "";
for (int i = 0; i < s.size(); i++) {
if (s[i] != ' ' && s[i] != '#') {
temp += s[i];
}
else if (s[i] == ' ') {
tempv.push_back(stoi(temp));
temp = "";
}
else if (s[i] == '#') {
ret.push_back(tempv);
temp = "";
tempv.clear();
}
}
while (!ret.empty() && ret.back().size() == 0)
ret.pop_back();
return ret;
}
string serialize(Node *root) {
string ret = "";
if (!root)
return ret;
queue<Node *> q;
q.push(root);
ret += to_string(root->val);
ret += " ";
ret += "#";
while (!q.empty()) {
Node *curr = q.front();
q.pop();
for (int i = 0; i < curr->children.size(); i++) {
if (curr->children[i]) {
ret += to_string(curr->children[i]->val);
q.push(curr->children[i]);
}
ret += " ";
}
ret += "#";
}
return ret;
}
Node *deserialize(string data) {
Node *ret;
if (data.size() == 0)
return NULL;
vector<vector<int>> v = createVector(data);
ret = new Node(v[0][0]);
queue<Node *> q;
q.push(ret);
int i = 1;
while (!q.empty() && i < v.size()) {
Node *curr = q.front();
q.pop();
for (int j = 0; j < v[i].size(); j++) {
int node = v[i][j];
Node *temp = new Node(node);
curr->children.push_back(temp);
q.push(temp);
}
i++;
}
return ret;
}
};
main() {
Codec ob;
Node n5(5), n6(6);
Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
Node n2(2), n4(4);
Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
n1.children.push_back(&n4);
cout << "Given Tree: " << n_ary_to_str(&n1) << endl;
string ser = ob.serialize(&n1);
cout << "Serialize: " << ser << endl;
Node *deser = ob.deserialize(ser);
cout << "Deserialized Tree: " << n_ary_to_str(deser);
}输入
Node n5(5), n6(6); Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6); Node n2(2), n4(4); Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2); n1.children.push_back(&n4);
输出
Given Tree: 1[3[5, 6, ], 2, 4, ] Serialize: 1 #3 2 4 #5 6 ##### Deserialized Tree: 1[3[5, 6, ], 2, 4, ]
341 次浏览
