Giả sử chúng ta có một cây N-ary và chúng ta phải tuần tự hóa và giải mã hóa chúng. Như chúng ta biết rằng tuần tự hóa là quá trình chuyển đổi cấu trúc dữ liệu hoặc đối tượng thành một chuỗi các bit để chúng ta có thể lưu trữ chúng trong tệp hoặc bộ đệm bộ nhớ và có thể được tạo lại sau này trong cùng một môi trường máy tính hoặc môi trường máy tính khác.
Ở đây chúng ta phải nghĩ ra một thuật toán để tuần tự hóa và giải mã hóa một cây N-ary. Cây N-ary là cây gốc trong đó mỗi nút có không quá N nút con.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là Serialize:1 # 3 2 4 # 5 6 ##### và Deserialized Tree:1 [3 [5, 6,], 2, 4,]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm createVector (), điều này sẽ mất s,
-
Xác định một mảng 2D ret
-
Xác định tạm thời mảng
-
temp:=chuỗi trống
-
để khởi tạo i:=0, khi i
-
nếu s [i] không bằng khoảng trống và s [i] không bằng '#' thì -
-
temp:=temp + s [i]
-
-
ngược lại khi s [i] giống với chuỗi trống thì -
-
chèn số nguyên tạm thời vào cuối tempv
-
temp:=chuỗi trống
-
-
ngược lại khi [i] giống với '#' thì -
-
chèn tempv vào cuối ret
-
temp:=chuỗi trống
-
nhiệt độ rõ ràng
-
-
-
while (not ret trống và phần tử cuối cùng của ret giống 0), do -
-
xóa phần tử cuối cùng khỏi ret
-
-
trả lại ret
-
Xác định một hàm serialize (), hàm này sẽ bắt nguồn từ gốc,
-
ret:=chuỗi trống
-
nếu không gốc là khác 0, thì -
-
trả lại ret
-
-
Xác định một hàng đợi q
-
chèn root vào q
-
rret:=ret nối val của gốc
-
ret:=ret nối khoảng cách
-
ret:=ret nối "#"
-
while (không phải q trống), do -
-
curr =phần tử đầu tiên của q
-
xóa phần tử khỏi q
-
để khởi tạo i:=0, khi i
-
if children [i] of curr, then -
-
ret:=ret nối con [i] của curr
-
chèn con [i] của curr vào q
-
-
ret:=ret + chuỗi trống
-
-
ret:=ret nối "#"
-
-
trả lại ret
-
Xác định một hàm deserialize (), hàm này sẽ lấy dữ liệu,
-
nếu kích thước dữ liệu bằng 0, thì -
-
trả về null
-
-
Xác định một mảng 2D v:=createVector (dữ liệu)
-
ret:=nút mới với giá trị v [0, 0]
-
Xác định một hàng đợi q
-
chèn ret vào q
-
i:=1
-
while (không phải q trống và i - kích thước của v), do -
-
curr =phần tử đầu tiên của q
-
xóa phần tử khỏi q
-
để khởi tạo j:=0, khi j - kích thước của v [i], cập nhật (tăng j lên 1), thực hiện -
-
nút:=v [i, j]
-
temp =nút mới với nút giá trị
-
chèn nhiệt độ vào cuối con của curr
-
chèn tạm thời vào q
-
-
(tăng tôi lên 1)
-
-
trả lại ret
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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);
} Đầu vào
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);
Đầu ra
Given Tree: 1[3[5, 6, ], 2, 4, ] Serialize: 1 #3 2 4 #5 6 ##### Deserialized Tree: 1[3[5, 6, ], 2, 4, ]