ধরি আমাদের একটি N-ary ট্রি আছে। আমাদের এই ট্রিটিকে একটি বাইনারি ট্রিতে এনকোড করতে হবে। আমাদের বাইনারি ট্রি থেকে আবার N-ary ট্রি পাওয়ার জন্য ডিসিরিয়ালাইজারও তৈরি করতে হবে।
উদাহরণস্বরূপ, যদি ইনপুট হয় নিচের ট্রিটি, তবে আউটপুটও একই ট্রি হবে।
সমাধানের ধাপসমূহ
encode()ফাংশন সংজ্ঞায়িত করা: এটি root নিবে।- যদি root না থাকে, তবে NULL ফেরত।
- node = নতুন ট্রি নোড root-এর ভ্যালু দিয়ে।
- যদি root-এর চাইল্ডের সংখ্যা > 0 হয়:
- node->left := encode(root->children[0])
- curr = node->left
- i = 1 থেকে root->children.size()-1 পর্যন্ত লুপ:
- curr->right := encode(root->children[i])
- curr := curr->right
- node ফেরত।
decode()ফাংশন সংজ্ঞায়িত করা: এটি root নিবে।- যদি root না থাকে, তবে NULL ফেরত।
- node := নতুন নোড root->val দিয়ে।
- curr := root->left
- যখন curr নন-নাল:
- node->children-এ decode(curr) পুশ করা।
- curr := curr->right
- node ফেরত।
প্রোগ্রাম উদাহরণ
#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 inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
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:
TreeNode* encode(Node* root) {
if (!root) return NULL;
TreeNode* node = new TreeNode(root->val);
if (root->children.size()) {
node->left = encode(root->children[0]);
}
TreeNode* curr = node->left;
for (int i = 1; i < root->children.size(); i++) {
curr->right = encode(root->children[i]);
curr = curr->right;
}
return node;
}
Node* decode(TreeNode* root) {
if (!root) return NULL;
Node* node = new Node(root->val);
TreeNode* curr = root->left;
while (curr) {
node->children.push_back(decode(curr));
curr = curr->right;
}
return node;
}
};
int 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;
cout << "Serialized Binary Tree: ";
TreeNode *root = ob.encode(&n1);
inord(root);
cout << endl;
Node *deser = ob.decode(root);
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, ] Serialized Binary Tree: 5 6 3 2 4 1 Deserialized Tree: 1[3[5, 6, ], 2, 4, ]
