C++-এ N-ary ট্রি সিরিয়ালাইজ এবং ডিসিরিয়ালাইজ করা

ধরি আমাদের একটি N-ary ট্রি আছে এবং আমাদের সেটিকে সিরিয়ালাইজ এবং ডিসিরিয়ালাইজ করতে হবে। সিরিয়ালাইজেশন হল ডেটা স্ট্রাকচার বা অবজেক্টকে বিটের সিকোয়েন্সে রূপান্তর করার প্রক্রিয়া যাতে সেটিকে ফাইল বা মেমোরি বাফারে স্টোর করা যায় এবং পরবর্তীতে একই বা অন্য কম্পিউটার এনভায়রনমেন্টে পুনরুদ্ধার করা যায়।

এখানে আমাদের N-ary ট্রি সিরিয়ালাইজ এবং ডিসিরিয়ালাইজ করার একটি অ্যালগরিদম ডিজাইন করতে হবে। N-ary ট্রি হল একটি রুটেড ট্রি যেখানে প্রতিটি নোডের সর্বোচ্চ N টি চাইল্ড হতে পারে।

উদাহরণস্বরূপ, ইনপুট ট্রি হলে আউটপুট হবে: Serialize: "1 #3 2 4 #5 6 #####" এবং Deserialized Tree: "1[3[5, 6, ], 2, 4, ]"

সমাধানের ধাপসমূহ

• createVector() ফাংশন সংজ্ঞায়িত করা: এটি s নিবে।
  • একটি 2D অ্যারে ret সংজ্ঞায়িত।
  • একটি অ্যারে tempv সংজ্ঞায়িত।
  • temp := খালি স্ট্রিং।
  • i = 0 থেকে s.size()-1 পর্যন্ত লুপ:
    • যদি s[i] না হয় স্পেস এবং '#' নয়: temp += s[i]
    • অন্যথায় যদি s[i] == ' ': temp-কে ইন্টেজার হিসেবে tempv-তে পুশ, temp খালি।
    • অন্যথায় যদি s[i] == '#': tempv-কে ret-তে পুশ, temp খালি, tempv ক্লিয়ার।
  • যখন ret খালি না এবং ret-এর শেষ উপাদান খালি: শেষ উপাদান ডিলিট।
  • ret ফেরত।
• serialize() ফাংশন সংজ্ঞায়িত করা: এটি root নিবে।
  • ret := খালি স্ট্রিং।
  • যদি root না থাকে: ret ফেরত।
  • একটি কিউ q সংজ্ঞায়িত, root পুশ।
  • ret += root->val + " #"
  • যখন q খালি না:
    • curr = q.front(); q.pop()
    • curr->children-র প্রতিটি চাইল্ডের জন্য:
      • যদি চাইল্ড থাকে: ret += চাইল্ড->val + " "; q-তে চাইল্ড পুশ।
    • ret += "#"
  • ret ফেরত।
• deserialize() ফাংশন সংজ্ঞায়িত করা: এটি data নিবে।
  • যদি data.size() == 0: NULL ফেরত।
  • v := createVector(data)
  • ret := নতুন নোড v[0][0] দিয়ে।
  • একটি কিউ q, ret পুশ।
  • i := 1
  • যখন q খালি না এবং i < v.size():
    • curr = q.front(); q.pop()
    • j = 0 থেকে v[i].size()-1 পর্যন্ত:
      • node = v[i][j]
      • temp = নতুন নোড node দিয়ে।
      • curr->children-এ temp পুশ, q-তে temp পুশ।
    • i++
  • ret ফেরত।

প্রোগ্রাম উদাহরণ

#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;
    }
};

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;
    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, ]