ধরুন আমাদের একটি N-ary গাছ আছে। আমাদের সেই গাছটিকে একটি বাইনারিতে এনকোড করতে হবে। বাইনারি ট্রিকে এন-আরি ট্রিতে ডিসিরিয়ালাইজ করার জন্যও আমাদের ডিসিরিয়ালাইজার তৈরি করতে হবে।
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন এনকোড সংজ্ঞায়িত করুন(), এটি রুট করবে,
-
রুট যদি বৈধ হয়, তাহলে −
-
রিটার্ন নাল
-
-
নোড =মূলের মান সহ নতুন ট্রি নোড
-
যদি মূলের বাচ্চাদের আকার 0 না হয়, তাহলে −
-
নোডের বাম :=এনকোড(শিশুদের[0] রুট)
-
-
curr =নোডের বাম
-
আরম্ভ করার জন্য i :=1, যখন i <রুটের বাচ্চাদের আকার, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −
-
নোডের অধিকার :=এনকোড(শিশুদের[i] রুট)
-
curr :=curr এর ডান
-
-
রিটার্ন নোড
-
একটি ফাংশন ডিকোড() সংজ্ঞায়িত করুন, এটি রুট করবে,
-
যদি root না থাকে, তাহলে −
-
NULL
ফেরত দিন
-
-
নোড :=রুটের ভ্যাল সহ নতুন নোড
-
curr :=মূলের বাম
-
যখন curr অ-শূন্য হয়, −
করুন-
নোডের শিশুদের শেষে decode(curr) সন্নিবেশ করান
-
curr :=curr এর ডান
-
-
রিটার্ন নোড
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _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;
}
};
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, ]
