【Python】二分木を深さ/幅優先探索でシリアライズ/デシリアライズする-ぐぐりらにっき

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

今回は、二分木が与えられた時に、その構造を文字列に変換するシリアライズと、その文字列を逆に二分木に戻すデシリアライズするコードをPythonを用いて実装しました。

二分木をシリアライズする方法としては、単純に深さ優先探索と幅優先探索の二つの方法が思いつくと思うので、今回はその二種類の方法でシリアライズし、それぞれのシリアライズ手法について逆変換であるデシリアライズも実装しました。

## 実装と結果

深さ優先探索を用いた実装->幅優先探索を用いた実装の順番で紹介します。

深さ優先探索には三つのバリエーションがあるので、全部で4通りのシリアライズ/デシリアライズを実装しました。

4つの探索法については詳しくはこちらの記事で解説されているので、ぜひ参考にしてみてください。

[うさぎでもわかる2分探索木　後編　2分探索木における4つの走査方法 | 工業大学生ももやまのうさぎ塾](https://www.momoyama-usagi.com/entry/info-algo-tree-traverse#__inorder)

### 深さ優先探索

深さ優先探索は以下の三つのバリエーションがあります。

* preorder (行きがけ順)
* inorder (通りがけ順)
* postorder (帰りがけ順)

行きがけ順ではnodeに到達した順番でnodeを探索済みにしていきます。
帰りがけ順はその逆で、そのnodeを最後に訪れたときに探索済みにします。
通りがけ順はその中間といった方法で、そのnodeより左側にあるnodeをすべて探索済みにした場合にそのnodeも探索済みにします。

```
  1
 / \
2   3
```

だと、
* 行きがけ順は 1,2,3
* 通りがけ順は 2,1,3
* 帰りがけ順は 2,3,1

となります。

以下の実装では`DfsCodec`のパラメータにorderを持たせて、この値によって

* preorder (行きがけ順)
* inorder (通りがけ順)
* postorder (帰りがけ順)

のうちどの深さ優先探索をするかを決めることにしました。

```python
class DfsCodec:
    """深さ優先探索的にシリアライズ/デシリアライズする."""

def __init__(self, order):
        if order not in ["pre", "in", "post"]:
            raise Exception(f"Invalid order {order}.")
        self.order = order

def serialize(self, root):
        """

深さ優先でシリアライズする.
        Noneはxに置換し、親子関係は()で囲む
          1
         / \
        2   3
        の場合、inorder (order=in)であれば
        (,(,x,2,x,),1,(,x,3,x,),)
        とシリアライズされる.デシリアライズはその逆.
        """
        def _serialize(x):
            left_list = _serialize(x.left) if x.left else [None]
            right_list = _serialize(x.right) if x.right else [None]
            if self.order == "in":
                result = ["("]+left_list + [x] + right_list + [")"]
            elif self.order == "pre":
                result = ["("]+[x] + left_list + right_list + [")"]
            elif self.order == "post":
                result = ["("] + left_list + right_list + [x] + [")"]
            else:
                raise Exception(f"Invalid order {self.order}")
            return result
        serialized_list = _serialize(root)
        return convert_serialized_list(serialized_list)

def deserialize(self, data):
        """デシリアライズしてrootを返す.

先頭から文字列を見ていき、)以外ならstackに追加していく.
        )がきたらstackから三つ取り出してtree_nodeを結合してrootをstackに追加
        これを文字列の末尾まで繰り返し、最後にstackに残ったtree_nodeがroot
        """
        converted_list = convert_serialization2list(data)

stack = deque([])
        for item in converted_list:
            if item == ")":
                tmp = []
                while len(stack):
                    pop = stack.pop()
                    if pop == "(":
                        break
                    else:
                        tmp.append(pop)
                assert len(tmp) == 3, tmp
                tmp.reverse()
                if self.order == "in":
                    center = tmp[1]
                    center.right = tmp[2]
                    center.left = tmp[0]
                elif self.order == "pre":
                    center = tmp[0]
                    center.left = tmp[1]
                    center.right = tmp[2]
                elif self.order == "post":
                    center = tmp[2]
                    center.left = tmp[0]
                    center.right = tmp[1]
                else:
                    raise Exception(f"Invalid order {self.order}")
                stack.append(center)
            else:
                stack.append(item)

if len(stack) == 1:
            return stack.pop()
        else:
            raise Exception(stack)
```

シリアライズは深さ優先探索なので再帰を用いて実装しました。

親子関係がわかるようにシリアライズする時に`()`で囲むようにしているのですが、
これがないとデシリアライズが難しかったので入れました。

調べてみると、preorderの深さ優先探索をしてシリアライズ/デシリアライズをしている以下の記事では`()`を使わずにデシリアライズできていました。

[二分木の直列化（シリアライズ）と復元 - Qiita](https://qiita.com/maebaru/items/8c548bdb980be3717906)

自分は最初inorderの深さ優先探索で実装しており、`()`がないと復元できないのでは...?と思ってこのような実装をしました。もしかしたらpreorder,inorder,postorderの全てで`()`がなくても復元できるのかもしれないですが、今回はこれでよしとしました。

実際に以下の二分木をシリアライズ/デシリアライズをした結果がこちらです。

```
   1
  / \
 2   3
    / \
   4   5
```

結果:

```
order : pre
serialized : (,1,(,2,x,x,),(,3,(,4,x,x,),(,5,x,x,),),)
original == deserialized ? -> True
serialization of deserialized : (,1,(,2,x,x,),(,3,(,4,x,x,),(,5,x,x,),),)

order : in
serialized : (,(,x,2,x,),1,(,(,x,4,x,),3,(,x,5,x,),),)
original == deserialized ? -> True
serialization of deserialized : (,(,x,2,x,),1,(,(,x,4,x,),3,(,x,5,x,),),)

order : post
serialized : (,(,x,x,2,),(,(,x,x,4,),(,x,x,5,),3,),1,)
original == deserialized ? -> True
serialization of deserialized : (,(,x,x,2,),(,(,x,x,4,),(,x,x,5,),3,),1,)
```

各orderの二行目ではオリジナルの木とシリアライズ->デシリアライズをして得られた木が等しいかを判定しました。
木の同一性の判定はTreeNodeクラスの方に実装しました。Appendixに載せたので興味を持たれた方はそちらも参考にしていただければと思います。
一応三行目でもう一度シリアライズして1回目のシリアライズ結果と同じかどうかも確認しています。

### 幅優先探索

幅優先探索については一種類なのでパラメータはなく、単純にキューをつかって幅優先探索を実装しました。

Pythonではスタック、キューを使いたい場合はcollectionsのdequeを使うようです。

[Pythonのスタックとキューには何を使えばいいのか（各データ構造の速度比較） - Qiita](https://qiita.com/saba/items/107c4237206e31acdbef)

実はちらっと深さ優先探索の方のデシリアライズでスタックを使っており、そこでもdequeを用いているのですが、こちらの幅優先探索ではシリアライズの処理でキューを用いる実装になっています。

```python
class BfsCodec:
    """幅優先探索的にシリアライズ/デシリアライズする."""

def serialize(self, root):
        """
        幅優先でシリアライズする.
        Noneはxに置換する.
          1
         / \
        2   3
        の場合
        1,2,3,x,x,x,x
        とシリアライズされる.デシリアライズはその逆.
        """
        queue = deque([root])
        serialized_list = []
        while queue:
            target = queue.popleft()
            serialized_list.append(target)
            if target is not None:
                queue.append(target.left)
                queue.append(target.right)

return convert_serialized_list(serialized_list)

def deserialize(self, data):
        """デシリアライズしてrootを返す.

キューに先頭のrootを入れてスタート
        二番目の要素から二個ずつみていき、キューから取り出してleftとrightにつける
        leftとrightのうちNoneでないものはキューに追加する
        全ての操作を終えると最初のrootにすべてのnodeがついているのでそれを返す.
        """
        data_list = convert_serialization2list(data)
        queue = deque([])
        if len(data_list) == 0:
            return None

queue.append(data_list[0])
        for i in range((len(data_list))):
            if 2*(i+1) >= len(data_list):
                break
            target = queue.popleft()
            target.left = data_list[2*(i+1)-1]
            target.right = data_list[2*(i+1)]
            if i == 0:
                root = target
            if target.left is not None:
                queue.append(target.left)

if target.right is not None:
                queue.append(target.right)
        return root
```

デシリアライズでもキューを使っていましたね。
コード中のdocstringにも書いてありますが、二個ずつ先頭からみていき、キューから取り出したものに子としてつけていきます。

深さ優先探索のときと同じ木構造に対して適用しました。

```
   1
  / \
 2   3
    / \
   4   5
```

結果はこちらです。

```
serialized : 1,2,3,x,x,4,5,x,x,x,x
original == deserialized ? -> True
serialization of deserialized : 1,2,3,x,x,4,5,x,x,x,x
```

問題なさそうです。

## おわりに

今回は二分木を文字列に変換し、復元する手法を四種類の方法で実装してみました。
シリアライズについては深さ優先探索や幅優先探索といった従来の手法で実装できるのですが、復元するのが難しかったため記事にしてみました。

個人的にもう少し考えられそうなのは、記事中でも言及していたpreorder以外でも`()`なしのシリアライズで作られた文字列を復元できるのか、という点です。

パッと思いつかなかったので今回はこの形で実装しましたが、もっとよい書き方があるかもしれないのであくまで一例として参考にしていただければと思います。

最後までお読みいただきありがとうございました。

## Appendix

本編のコードだけでは完結しないため、こちらで足りないコードを補完しておきます。

```python
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.right = None
        self.left = None

def __eq__(self, other):
        """自分以下のtreeが一致しているかどうかを判定する."""
        def equals(x, y):
            if (bool(x.left) ^ bool(y.left)) or (bool(x.left) ^ bool(y.left)):
                return False

if (x.left is None and y.left is None) and (x.right is None and y.right is None):
                return True

return (x.val == y.val) and (equals(x.left, y.left)) and (equals(x.right, y.right))

if not isinstance(other, TreeNode):
            return False
        return equals(self, other)

def convert_serialized_list(serialized_list):
    """シリアライズしたあとのlistを最終的な文字列に変換する."""

converted_list = []
    for e in serialized_list:
        target = e
        if target is None:
            target = "x"
        elif isinstance(target, TreeNode):
            target = str(e.val)

converted_list.append(target)
    return ",".join(converted_list)

def convert_serialization2list(data):
    """シリアライズした文字列をリストに変換する.convert_serialized_listの逆変換."""
    data_list = data.split(",")
    converted_list = []
    for item in data_list:
        if item == "x":
            item = None
        elif item.isdecimal():
            item = TreeNode(int(item))

converted_list.append(item)
    return converted_list

```

【Python】二分木を深さ/幅優先探索でシリアライズ/デシリアライズする

0 件のコメント:

コメントを投稿

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT