C++でのバイナリツリーのシリアル化と逆シリアル化

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

ここでは、バイナリツリーをシリアル化および逆シリアル化するためのアルゴリズムを考案する必要があります。二分木は、各ノードに2つ以下の子を持つルートツリーです。

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

その場合、出力はSerialize − 1 2 3 4 5 N N N N N N Deserialized Tree：4 2 5 1 3.

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

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

• ret：=空白の文字列

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

• ルートをqに挿入

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

  • curr=qの最初の要素

  • qから要素を削除

  • currが利用できない場合は、-

    • ret：=ret連結"N"

    • ret：=ret連結空白スペース

    • 次の部分を無視し、次の反復にスキップします

  • ret：=ret+currの値

  • ret：=ret+空白スペース

  • qの終わりのcurrの左側

  • qの終わりのcurrの権利

• retを返す

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

• data[0]が'N'と同じ場合、-

  • NULLを返す

• temp：=空の文字列

• 配列を定義するv

• 初期化i：=0の場合、i −データのサイズの場合、更新（iを1増やします）、実行-

  • data [i]が空白と同じ場合、-

    • vの最後に温度を挿入

    • temp：=空白の文字列

    • 次の部分を無視し、次の反復にスキップします

  • temp：=temp + data [i]

• newRoot =v [0]

  の新しいノード

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

• newRootをqに挿入します

• i：=1

• （qが空で、i

  • 親=qの最初の要素

  • qから要素を削除

  • v [i]が「N」と等しくない場合、-

    • 親の左側：=v [i]

      のある新しいノード

    • 親の左側をqに挿入

  • （iを1増やします）

  • v [i]が「N」と等しくない場合、-

    • 親の権利：=v [i]

      の新しいノード

    • 親の権利をqに挿入

  • （iを1増やします）

• newRootを返す

例

理解を深めるために、次の実装を見てみましょう-

#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 insert(TreeNode **root, int val) {
   queue<TreeNode *> q;
   q.push(*root);
   while (q.size()) {
      TreeNode *temp = q.front();
      q.pop();
      if (!temp->left) {
         if (val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }
      else {
         q.push(temp->left);
      }
      if (!temp->right) {
         if (val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }
      else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v) {
   TreeNode *root = new TreeNode(v[0]);
   for (int i = 1; i < v.size(); i++) {
      insert(&root, v[i]);
   }
   return root;
}
void inord(TreeNode *root) {
   if (root != NULL) {
      inord(root->left);
      cout << root->val << " ";
      inord(root->right);
   }
}
class Codec {
public:
   string serialize(TreeNode *root) {
      string ret = "";
      queue<TreeNode *> q;
      q.push(root);
      while (!q.empty()) {
         TreeNode *curr = q.front();
         q.pop();
         if (!curr) {
            ret += "N";
            ret += " ";
            continue;
         }
         ret += to_string(curr->val);
         ret += " ";
         q.push(curr->left);
         q.push(curr->right);
      }
      return ret;
   }
   TreeNode *deserialize(string data) {
      if (data[0] == 'N')
         return NULL;
      string temp = "";
      vector<string> v;
      for (int i = 0; i < data.size(); i++) {
         if (data[i] == ' ') {
            v.push_back(temp);
            temp = "";
            continue;
         }
         temp += data[i];
      }
      TreeNode *newRoot = new TreeNode(stoi(v[0]));
      queue<TreeNode *> q;
      q.push(newRoot);
      int i = 1;
      while (!q.empty() && i < v.size()) {
         TreeNode *parent = q.front();
         q.pop();
         if (v[i] != "N") {
            parent->left = new TreeNode(stoi(v[i]));
            q.push(parent->left);
         }
         i++;
         if (v[i] != "N") {
            parent->right = new TreeNode(stoi(v[i]));
            q.push(parent->right);
         }
         i++;
      }
      return newRoot;
   }
};
main() {
   Codec ob;
   vector<int> v = {1,2,3,4,5};
   TreeNode *root = make_tree(v);
   cout << "Given Tree: ";
   inord(root);
   cout << endl;
   string ser = ob.serialize(root);
   cout << "Serialize: " << ser << endl;
   TreeNode *deser = ob.deserialize(ser);
   cout << "Deserialized Tree: ";
   inord(root);
}

入力

1,2,3,4,5

出力

Given Tree: 4 2 5 1 3
Serialize: 1 2 3 4 5 N N N N N N
Deserialized Tree: 4 2 5 1 3