二分木の直列化（シリアライズ）と復元

概要

直列化（シリアライズ）とは、オブジェクトをバイト列に変換し、メモリやファイル上に保存しやすい状態にすることです。本記事では二分木のデータ構造を文字列にシリアライズし、さらにその文字列から二分木を復元する手法を紹介します。

方針

二分木の構造を文字列に変換するにはいくつかの方法が考えられますが、ここでは深さ優先探索(DFS)の先行順巡回(pre-order)の順に各ノードの値を羅列した文字列を生成することにします。

例

下記のような二分木をDFSのpre-orderで走査し、1 2 null null 3 4 null null 5 null nullのような文字列を生成します。のちの復元（デシリアライズ）を容易に行うため、子ノードがnullの場合も明示的に文字列に含めている点に注意してください。

    1
   / \
  2   3
     / \
    4   5

実装例

    def preorder(self, node, arr):
        if node is None:
            # ノードが空の場合もnullとして記録しておく
            arr.append('null')
        elif node is not None:
            arr.append(node.val)
            arr = self.preorder(node.left, arr)
            arr = self.preorder(node.right, arr)
        return arr

    def serialize(self, root):
        # 先行順巡回でリストを生成
        arr = self.preorder(root, [])
        # スペース区切りでリストを文字列化する
        return ' '.join(str(i) for i in arr)

    def deserialize(self, text):
        # 文字列からリストを生成
        arr = text.split()
        return self.rdeserialize(arr)

    # pre-orderの配列から二分木を生成するメソッド
    def rdeserialize(self, arr):
        if len(arr) == 0:
            return None
        if arr[0] == 'null':
            del arr[0]
            return None

        # pre-orderの先頭をrootとして取り出し、部分木を再帰的に生成する
        root = TreeNode(int(arr[0]))
        del arr[0]
        root.left = self.rdeserialize(arr)
        root.right = self.rdeserialize(arr)

        return root