C++での二分木のシリアライズとデシリアライズを実装する方法

はじめに

シリアライズ（直列化）とは、データ構造やオブジェクトを一連のビット列へ変換する処理のことです。これにより、データをファイルやメモリバッファに保存でき、後から同じ環境でも別のコンピュータ環境でも元の構造として復元（デシリアライズ）できます。

本記事では、二分木を対象に、シリアライズとデシリアライズを行うアルゴリズムを解説します。なお、二分木とは各ノードが最大2つの子ノードしか持たない根付き木のことを指します。

例えば、次のような二分木が与えられたとします。

この場合の出力は以下のようになります。

• シリアライズ結果：1 2 3 4 5 N N N N N N
• デシリアライズ後の木（中順走査）：4 2 5 1 3

アルゴリズムの考え方

ここでは、幅優先探索（BFS）を利用したレベル順の走査によって木を文字列化します。存在しない子ノードは「N」で表現することで、木の構造を完全に復元できるようにします。

serialize() 関数の手順

• 引数としてルートノード root を受け取ります。
• 結果格納用の空文字列 ret を用意します。
• キュー q を定義し、root を挿入します。
• q が空になるまで以下を繰り返します。
  • q の先頭要素を curr として取り出します。
  • curr が NULL の場合は、ret に「N」と空白を連結し、次の反復へスキップします。
  • そうでなければ、ret に curr の値と空白を連結します。
  • curr の左の子と右の子をそれぞれ q の末尾に追加します。
• 最後に ret を返します。

deserialize() 関数の手順

• 引数として文字列 data を受け取ります。
• data の先頭が「N」であれば、空の木なので NULL を返します。
• data を空白区切りで分割し、配列 v に格納します。
• v[0] の値を持つノードを newRoot として生成します。
• キュー q を定義し、newRoot を挿入します。インデックス i を 1 に初期化します。
• q が空でなく、かつ i が v のサイズ未満である間、以下を繰り返します。
  • q の先頭要素を parent として取り出します。
  • v[i] が「N」でなければ、その値で左の子ノードを作成し、q に追加します。i を 1 増やします。
  • v[i] が「N」でなければ、その値で右の子ノードを作成し、q に追加します。i を 1 増やします。
• 最後に newRoot を返します。

C++による実装例

それでは、実際の実装を見ていきましょう。

#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

まとめ

このように、キューを活用したレベル順走査（BFS）を用いることで、二分木を「N」マーカー付きの文字列としてシリアライズし、その文字列から元の木構造を正確に復元することができます。シリアライズ・デシリアライズは計算量ともに O(N)（N はノード数）であり、効率的な手法です。