สมมติว่าเรามีต้นไม้ไบนารี และเราต้องจัดทำซีเรียล (serialize) และถอดซีเรียล (deserialize) ต้นไม้นั้น การซีเรียลคือการแปลงโครงสร้างข้อมูลหรือวัตถุเป็นลำดับบิต เพื่อเก็บในไฟล์หรือบัฟเฟอร์หน่วยความจำ และสามารถสร้างคืนได้ภายหลังในสภาพแวดล้อมเดียวกันหรือต่างกัน
ที่นี่เราต้องออกแบบอัลกอริทึมเพื่อซีเรียลและถอดซีเรียลต้นไม้ไบนารี ต้นไม้ไบนารีคือต้นไม้ที่มีราก ซึ่งแต่ละโหนดมีลูกไม่เกิน 2 โหนด
เช่น ถ้าอินพุตเป็นต้นไม้ตามรูปภาพ:
ผลลัพธ์จะเป็น Serialize: 1 2 3 4 5 N N N N N N Deserialized Tree: 4 2 5 1 3 (Inorder traversal)
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
- serialize(root): ใช้ BFS (Queue) เขียนค่าโหนด ถ้าโหนดเป็น null เขียน "N" คั่นด้วยช่องว่าว
- deserialize(data): แยกสตริงด้วยช่องว่าวได้เวกเตอร์ v; สร้างรากจาก v[0]; ใช้ Queue สร้างลูกซ้ายขวาจาก v[1], v[2]... ถ้าเป็น "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 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 v) {
TreeNode* root = new TreeNode(v[0]);
for(int i=1;ileft); cout<val<<" "; inord(root->right); }
}
class Codec {
public:
string serialize(TreeNode* root) {
string ret = "";
queue q; q.push(root);
while(!q.empty()){
TreeNode* curr = q.front(); q.pop();
if(!curr){ ret += "N "; continue; }
ret += to_string(curr->val) + " ";
q.push(curr->left); q.push(curr->right);
}
return ret;
}
TreeNode* deserialize(string data) {
if(data[0]=='N') return NULL;
string temp = ""; vector v;
for(int i=0;i q; q.push(newRoot);
int i=1;
while(!q.empty() && ileft = 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 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(deser);
}
อินพุต
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
