C++でのN-aryツリーのシリアル化と逆シリアル化

N-aryツリーが1つあり、それらをシリアル化および逆シリアル化する必要があるとします。シリアル化とは、データ構造またはオブジェクトをビットシーケンスに変換して、ファイルまたはメモリバッファに格納し、後で同じまたは別のコンピュータ環境で再構築できるようにするプロセスであることを知っています。

ここでは、N-aryツリーをシリアル化および逆シリアル化するためのアルゴリズムを考案する必要があります。 N-aryツリーは、各ノードにN個以下の子を持つルートツリーです。

したがって、入力が次のような場合

その場合、出力はシリアル化：1＃3 2 4＃5 6 #####および逆シリアル化ツリー：1 [3 [5、6、]、2、4、]

これを解決するには、次の手順に従います-

• 関数createVector（）を定義します。これにはsがかかります

• 1つの2D配列retを定義する

• 配列tempvを定義する

• temp：=空の文字列

• 初期化i：=0の場合、i

  • s [i]が空白スペースに等しくなく、s [i]が「＃」に等しくない場合、-

    • temp：=temp + s [i]

  • それ以外の場合、s [i]が空白の文字列と同じである場合、-

    • tempvの最後にtemps整数を挿入します

    • temp：=空の文字列

  • それ以外の場合、s [i]が'＃'と同じである場合、-

    • retの最後にtempvを挿入します

    • temp：=空の文字列

    • 明確な温度

• （retは空ではなく、retの最後の要素は0と同じです）、do-

  • retから最後の要素を削除する

• retを返す

• 関数serialize（）を定義します。これはルートになります

• ret：=空の文字列

• ルートがゼロ以外の場合、-

  • retを返す

• 1つのキューを定義するq

• ルートをqに挿入

• rret：=ルートのvalを連結するret

• ret：=ret連結スペース

• ret：=ret concatenate "＃"

• （qが空ではない）間、-

  • curr=qの最初の要素

  • qから要素を削除

  • 初期化i：=0の場合、i

    • currのchildren[i]の場合、-

      • ret：=currの子[i]を連結するret

      • currのchildren[i]をqに挿入します

    • ret：=ret+空白の文字列

  • ret：=ret concatenate "＃"

• retを返す

• 関数deserialize（）を定義します。これにより、データが取得されます。

• データのサイズが0と同じ場合、-

  • nullを返す

• 1つの2D配列を定義しますv：=createVector（data）

• ret：=値v [0、0]

  の新しいノード

• 1つのキューを定義するq

• retをqに挿入

• i：=1

• （qが空で、i-vのサイズではない）間、-

  • curr=qの最初の要素

  • qから要素を削除

  • 初期化j：=0の場合、j −サイズがv [i]の場合、更新（jを1増やします）、do −

    • ノード：=v [i、j]

    • temp=値ノードを持つ新しいノード

    • currの子の最後にtempを挿入します

    • qにtempを挿入

  • （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, ]