สมมติว่าเรามีต้นไม้ N-ary และเราต้องจัดทำซีเรียล (serialize) และถอดซีเรียล (deserialize) ต้นไม้นั้น ตามที่รู้จักว่าการซีเรียลคือการแปลงโครงสร้างข้อมูลหรือวัตถุเป็นลำดับบิต เพื่อเก็บในไฟล์หรือบัฟเฟอร์หน่วยความจำ และสามารถสร้างคืนได้ภายหลังในสภาพแวดล้อมเดียวกันหรือต่างกัน
ที่นี่เราต้องออกแบบอัลกอริทึมเพื่อซีเรียลและถอดซีเรียลต้นไม้ N-ary ต้นไม้ N-ary คือต้นไม้ที่มีราก ซึ่งแต่ละโหนดมีลูกไม่เกิน N โหนด
เช่น ถ้าอินพุตเป็นรูปภาพดังนี้:
ผลลัพธ์จะเป็น Serialize: 1 #3 2 4 #5 6 ##### และ Deserialized Tree: 1[3[5, 6, ], 2, 4, ]
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
- กำหนดฟังก์ชัน createVector() รับ s: แยกสตริงเป็นเวกเตอร์ 2 มิติของจำนวนเต็ม โดยใช้ '#' และช่องว่าวเป็นตัวคั่น
- กำหนดฟังก์ชัน serialize() รับ root: ใช้ BFS (Queue) เขียนค่าราก แล้วตามด้วยลูกของแต่ละโหนด คั่นระดับด้วย '#'
- กำหนดฟังก์ชัน deserialize() รับ data: ใช้ createVector() ได้โครงสร้างระดับ แล้วสร้างต้นไม้ทีละระดับด้วย Queue
ตัวอย่าง
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
vector children;
Node() {}
Node(int _val) { val = _val; }
Node(int _val, vector _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> createVector(string s) {
vector> ret;
vector 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 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> v = createVector(data);
ret = new Node(v[0][0]);
queue 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, ]
