ধরুন আমাদের একটি বাইনারি গাছ আছে এবং আমাদের সেগুলিকে সিরিয়ালাইজ এবং ডিসিরিয়ালাইজ করতে হবে। আমরা জানি যে সিরিয়ালাইজেশন হল একটি ডেটা স্ট্রাকচার বা বস্তুকে বিটগুলির একটি ক্রমানুসারে রূপান্তর করার প্রক্রিয়া যাতে আমরা সেগুলিকে একটি ফাইল বা মেমরি বাফারে সংরক্ষণ করতে পারি এবং এটি একই বা অন্য কম্পিউটার পরিবেশে পরে পুনর্গঠন করা যেতে পারে।
এখানে বাইনারি ট্রিকে সিরিয়ালাইজ এবং ডিসিরিয়ালাইজ করার জন্য আমাদের একটি অ্যালগরিদম তৈরি করতে হবে। বাইনারি ট্রি হল একটি শিকড়যুক্ত গাছ যার প্রতিটি নোডে 2টির বেশি বাচ্চা নেই৷
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে সিরিয়ালাইজ − 1 2 3 4 5 N N N N N N Deserialized Tree:4 2 5 1 3।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন serialize(), এটি রুট নেবে,
সংজ্ঞায়িত করুন -
ret :=ফাঁকা স্ট্রিং
-
একটি সারি q
সংজ্ঞায়িত করুন -
q
-এ রুট সন্নিবেশ করান -
যখন (q খালি নয়), −
করুন-
curr =q
এর প্রথম উপাদান -
q
থেকে উপাদান মুছুন -
যদি curr উপলব্ধ না হয়, তাহলে -
-
ret :=ret concatenate "N"
-
ret :=ret concatenate ফাঁকা স্থান
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
ret :=ret + curr এর মান
-
ret :=ret + ফাঁকা স্থান
-
q
এর শেষে curr এর বাম -
q
এর শেষে curr এর ডান
-
-
রিটার্ন রিটার্ন
-
একটি ফাংশন deserialize(), এটি ডেটা নেবে,
সংজ্ঞায়িত করুন -
যদি ডেটা[0] 'N' এর মত হয়, তাহলে −
-
NULL
ফেরত দিন
-
-
temp :=খালি স্ট্রিং
-
একটি অ্যারে v
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=0, যখন i − ডেটার আকার, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −
-
যদি ডেটা[i] ফাঁকা স্থানের মতো হয়, তাহলে −
-
v
এর শেষে তাপমাত্রা সন্নিবেশ করুন -
temp :=ফাঁকা স্ট্রিং
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
temp :=temp + ডেটা[i]
-
-
newRoot =v[0]
সহ নতুন নোড -
একটি সারি q
সংজ্ঞায়িত করুন -
q
-এ newRoot সন্নিবেশ করান -
i :=1
-
যখন (q খালি নয় এবং i
করুন -
প্যারেন্ট =q
এর প্রথম উপাদান -
q
থেকে উপাদান মুছুন -
যদি v[i] "N" এর সমান না হয়, তাহলে −
-
প্যারেন্টের বাম :=v[i]
সহ নতুন নোড -
q
-এ প্যারেন্টের বাঁদিকে সন্নিবেশ করান
-
-
(i 1 দ্বারা বাড়ান)
-
যদি v[i] "N" এর সমান না হয়, তাহলে −
-
পিতামাতার অধিকার :=v[i]
সহ নতুন নোড -
q
-এ পিতামাতার অধিকার সন্নিবেশ করান
-
-
(i 1 দ্বারা বাড়ান)
-
-
নতুন রুট ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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);
} ইনপুট
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
