सी++ में एन-आरी ट्री को क्रमानुसार और डिसेरिएलाइज करें

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

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

तो, अगर इनपुट पसंद है

तो आउटपुट सीरियलाइज होगा:1 #3 2 4 #5 6 ##### और डिसेरिएलाइज्ड ट्री:1[3[5, 6, ], 2, 4, ]

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

• फ़ंक्शन createVector() को परिभाषित करें, इसमें s लगेंगे,

• एक 2डी सरणी रेट परिभाषित करें

• एक सरणी tempv परिभाषित करें

• अस्थायी:=खाली स्ट्रिंग

• इनिशियलाइज़ i:=0 के लिए, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -

  • यदि s[i] रिक्त स्थान के बराबर नहीं है और s[i] '#' के बराबर नहीं है, तो -

    • अस्थायी:=अस्थायी + एस [i]

  • अन्यथा जब s[i] रिक्त स्ट्रिंग के समान है, तो -

    • tempv के अंत में temp s पूर्णांक डालें

    • अस्थायी:=खाली स्ट्रिंग

  • अन्यथा जब s[i] '#' के समान हो, तब -

    • रिट के अंत में tempv डालें

    • अस्थायी:=खाली स्ट्रिंग

    • स्पष्ट अस्थायी

• जबकि (न रिट खाली है और रिट का अंतिम तत्व 0 के समान है), करें -

  • रिट से अंतिम तत्व हटाएं

• वापसी रिट

• एक फ़ंक्शन को परिभाषित करें serialize(), यह जड़ लेगा,

• रिट:=खाली स्ट्रिंग

• यदि जड़ नहीं शून्य शून्य है, तो -

  • वापसी रिट

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

• q में रूट डालें

• rret :=ret concatenate val of root

• ret :=ret concatenate space

• ret :=ret concatenate "#"

• जबकि (नहीं q खाली है), करें -

  • curr =q का पहला तत्व

  • q से तत्व हटाएं

  • इनिशियलाइज़ i:=0 के लिए, जब मैं <बच्चों के सरणी का आकार, अद्यतन (i से 1 बढ़ाएँ), करें -

    • अगर बच्चे [i] करी के हैं, तो -

      • ret :=ret concatenate Kids[i] of curr

      • क्यू में बच्चे [i] कर्व डालें

    • रिट:=रिट + ब्लैंक स्ट्रिंग

  • ret :=ret concatenate "#"

• वापसी रिट

• एक फ़ंक्शन को परिभाषित करें deserialize(), यह डेटा लेगा,

• यदि डेटा का आकार 0 के समान है, तो -

  • वापसी शून्य

• एक 2डी सरणी को परिभाषित करें v:=createVector(data)

• ret :=मान v[0, 0]

  . के साथ नया नोड

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

• q में रिट डालें

• मैं :=1

• जबकि (क्यू खाली नहीं है और मैं - वी का आकार), करते हैं -

  • curr =q का पहला तत्व

  • q से तत्व हटाएं

  • इनिशियलाइज़ j :=0 के लिए, जब j - v का आकार [i], अपडेट करें (1 से j बढ़ाएँ), करें -

    • नोड :=v[i, j]

    • अस्थायी =मान नोड के साथ नया नोड

    • कर्व के बच्चों के अंत में अस्थायी डालें

    • q में अस्थायी डालें

  • (मैं 1 से बढ़ाइए)

• वापसी रिट

उदाहरण

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

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