Help us understand the problem. What is going on with this article?

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

概要

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

方針

二分木の構造を文字列に変換するにはいくつかの方法が考えられますが、ここでは深さ優先探索(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
Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away