N-ary ट्री को सीरियलाइज़ और डिसीरियलाइज़ करें

मान लीजिए हमारे पास एक N-ary ट्री है और हमें उन्हें सीरियलाइज़ और डिसीरियलाइज़ करना है। जैसा कि हम जानते हैं कि सीरियलाइज़ेशन एक डेटा संरचना या ऑब्जेक्ट को बिट्स के अनुक्रम में बदलने की प्रक्रिया है ताकि हम उन्हें फाइल या मेमोरी बफर में स्टोर कर सकें, और बाद में उसी या दूसरे कंप्यूटर वातावरण में पुनर्निर्मित कर सकें।

यहां हमें N-ary ट्री को सीरियलाइज़ और डिसीरियलाइज़ करने के लिए एक एल्गोरिदम तैयार करना है। N-ary ट्री एक रूटेड ट्री है जिसमें प्रत्येक नोड में N से अधिक बच्चे नहीं होते।

तो, यदि इनपुट इस तरह है

N-ary ट्री को सीरियलाइज़ और डिसीरियलाइज़ करें - C++

तो आउटपुट होगा Serialize: 1 #3 2 4 #5 6 ##### और Deserialized Tree: 1[3[5, 6, ], 2, 4, ]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

createVector() नामक एक फ़ंक्शन परिभाषित करें, जो s लेगा,
एक 2D ऐरे ret परिभाषित करें
एक ऐरे tempv परिभाषित करें
temp := खाली स्ट्रिंग
i := 0 से आरंभ करें, जब i, s के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −
- यदि s[i] खाली स्थान के बराबर नहीं है और s[i] '#' के बराबर नहीं है, तो −
  - temp := temp + s[i]
- अन्यथा जब s[i] खाली स्ट्रिंग के समान है, तो −
  - temp को पूर्णांक के रूप में tempv के अंत में डालें
  - temp := खाली स्ट्रिंग
- अन्यथा जब s[i] '#' के समान है, तो −
  - tempv को ret के अंत में डालें
  - temp := खाली स्ट्रिंग
  - tempv को क्लियर करें
जब तक (ret खाली नहीं है और ret का अंतिम तत्व 0 के समान है), करें −
- ret से अंतिम तत्व हटाएं
ret लौटाएं
serialize() नामक एक फ़ंक्शन परिभाषित करें, जो root लेगा,
ret := खाली स्ट्रिंग
यदि root शून्येतर नहीं है, तो −
- ret लौटाएं

एक कतार q परिभाषित करें

root को q में डालें
rret := ret को root के val के साथ जोड़ें
ret := ret को स्पेस के साथ जोड़ें
ret := ret को "#" के साथ जोड़ें
जब तक (q खाली नहीं है), करें −
- curr = q का पहला तत्व
- q से तत्व हटाएं
- i := 0 से आरंभ करें, जब i, curr के children ऐरे के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −
  - यदि curr के children[i], तो −
    - ret := ret को curr के children[i] के साथ जोड़ें
    - curr के children[i] को q में डालें
  - ret := ret + खाली स्ट्रिंग
- ret := ret को "#" के साथ जोड़ें
ret लौटाएं
deserialize() नामक एक फ़ंक्शन परिभाषित करें, जो data लेगा,
यदि data का आकार 0 के समान है, तो −
- null लौटाएं
एक 2D ऐरे v := createVector(data) परिभाषित करें
ret := v[0, 0] मान के साथ नया नोड
एक कतार q परिभाषित करें
ret को q में डालें
i := 1
जब तक (q खाली नहीं है और i − v का आकार), करें −
- curr = q का पहला तत्व
- q से तत्व हटाएं
- j := 0 से आरंभ करें, जब j − v[i] का आकार, अद्यतन करें (j को 1 से बढ़ाएं), करें −
  - node := v[i, j]
  - temp = node मान के साथ नया नोड
  - temp को curr के children के अंत में डालें
  - temp को q में डालें
- (i को 1 से बढ़ाएं)
ret लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

#include <bits/stdc++.h> using namespace std; 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:    vector<vector<int>>createVector(string s) {       vector<vector<int>> ret;       vector<int> 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<Node *> 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<vector<int>> v = createVector(data);          ret = new Node(v[0][0]);          queue<Node *> 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;          }  }; 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, ]