Giả sử chúng ta có một cây nhị phân 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 cây nhị phân. Cây nhị phân là cây gốc trong đó mỗi nút có không quá 2 nút con.
Vì vậy, nếu đầu vào giống như
Sau đó, đầu ra sẽ được tuần tự hóa - 1 2 3 4 5 N N N N N N N N N N Cây Deserialized:4 2 5 1 3.
Để 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 serialize (), hàm này sẽ bắt nguồn từ gốc,
-
ret:=chuỗi trống
-
Xác định một hàng đợi q
-
chèn root vào q
-
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
-
nếu curr không có sẵn, thì -
-
ret:=ret nối "N"
-
ret:=ret nối khoảng trống
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
ret:=ret + giá trị của curr
-
ret:=ret + khoảng trắng
-
bên trái lề đường ở cuối q
-
bên phải của lề đường ở cuối q
-
-
trả lại ret
-
Xác định một hàm deserialize (), hàm này sẽ lấy dữ liệu,
-
nếu dữ liệu [0] giống với 'N', thì -
-
trả về NULL
-
-
temp:=chuỗi trống
-
Xác định một mảng v
-
để khởi tạo i:=0, khi i - kích thước dữ liệu, hãy cập nhật (tăng i lên 1), thực hiện -
-
nếu dữ liệu [i] giống với khoảng trống, thì -
-
chèn tạm thời vào cuối v
-
temp:=chuỗi trống
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
temp:=temp + data [i]
-
-
newRoot =nút mới với v [0]
-
Xác định một hàng đợi q
-
chèn newRoot vào q
-
i:=1
-
while (không phải q trống và i
-
cha =phần tử đầu tiên của q
-
xóa phần tử khỏi q
-
nếu v [i] không bằng "N" thì -
-
left of cha:=new node with v [i]
-
chèn bên trái của cha mẹ vào q
-
-
(tăng tôi lên 1)
-
nếu v [i] không bằng "N" thì -
-
quyền của phụ huynh:=nút mới với v [i]
-
chèn quyền của cha mẹ vào q
-
-
(tăng tôi lên 1)
-
-
trả lại newRoot
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 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);
} Đầu vào
1,2,3,4,5
Đầu ra
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