二分木の巡回とは？前順・中順・後順・レベル順を解説

巡回の順序が重要な理由

木には唯一の自然な順序というものがないので、アルゴリズムは目的に合う順序を選びます。二分探索木を中順で巡回すると、キーがソート順で得られます。前順は親を子より先に訪問するので、木のコピーや、あとで再構築できる形での書き出しに必要な順序です。後順は子を親より先に訪問するので、木の削除、フォルダサイズの計算、式の木の評価に必要です。レベル順は最も浅いノードを最初に見つけ、木を行ごとに出力できます。

1つの例で見る4つの順序

次の木を使います。根は1で、子は2と3。ノード2は子4と5を持ち、ノード3は右の子6を持ちます。

        1
       / \
      2   3
     / \   \
    4   5   6

最初の3つの覚え方は簡単です。名前が、ノードを訪問する位置を表しています。pre（前）は両方の部分木より前、in（中）は部分木の間、post（後）は両方の部分木のあとです。左部分木は常に右より先に訪問します。

再帰による実装

再帰版は、定義をそのままコードにしたものです。関数ごとに、ノードを訪問する行が異なります。

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
def preorder(node, out):
    if node:
        out.append(node.val)
        preorder(node.left, out)
        preorder(node.right, out)
    return out
def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)
    return out
def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.val)
    return out
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
print(preorder(root, []))   # [1, 2, 4, 5, 3, 6]
print(inorder(root, []))    # [4, 2, 5, 1, 3, 6]
print(postorder(root, []))  # [4, 5, 2, 6, 3, 1]

スタックを使った前順・中順の反復実装

再帰はコールスタックを使います。深い木での再帰の上限を避けるには、スタックを自分で管理します。前順では、ノードをpopして訪問し、左の子が先に処理されるように、右の子を左の子より先にpushします。

中順では、左へ行けるところまで進みながらノードをpushしていきます。それ以上左へ行けなくなったらノードをpopして訪問し、その右の子へ移ります。

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out
def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:              # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out
print(preorder_iter(root))  # [1, 2, 4, 5, 3, 6]
print(inorder_iter(root))   # [4, 2, 5, 1, 3, 6]

後順とレベル順の反復実装

反復による後順が最も厄介です。すっきりした方法の1つはフラグを使うことです。各ノードを2回pushし、2回目には「子のあとに訪問する準備ができた」という印を付けます。レベル順はスタックの代わりにキューを使います。キューを1レベルずつ処理すれば、各ノードの深さも分かります。

from collections import deque
def postorder_iter(root):
    out, stack = [], [(root, False)] if root else []
    while stack:
        node, children_done = stack.pop()
        if children_done:
            out.append(node.val)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return out
def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):   # nodes of the current level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels
print(postorder_iter(root))  # [4, 5, 2, 6, 3, 1]
print(level_order(root))     # [[1], [2, 3], [4, 5, 6]]

後順のもう1つのよくある手法は、変形した前順（ノード、右、左）を実行して、結果を反転することです。

時間計算量と空間計算量

ここで、nはノード数、hは高さ、wは最大の幅です。平衡木ではhは約log2(n)、wは約n/2になりえます。鎖状の木ではhはn、wは1です。

よくある間違い

• 反復の前順で、左の子を右の子より先にpushしてしまう。スタックはLIFOなので、先に処理したい子を最後にpushします。
• 空の木を忘れる：すべての関数は、root is Noneのときに空の結果を返すべきです。
• レベル順で、listとpop(0)をキューとして使う。popのたびにO(n)かかります。collections.dequeを使いましょう。
• 非常に深い木で再帰に頼る。Pythonは再帰の上限（デフォルトで約1000）でRecursionErrorを出して止まります。
• 1つの巡回だけで木が特定できると期待する。前順だけでは曖昧です。前順と中順（値が重複しない場合）があれば、木を再構築できます。

どの巡回をいつ使うか

前順・中順・後順はいずれも深さ優先探索の形で、レベル順は木に適用した幅優先探索です。同じ考え方は一般のグラフにも広げられますが、その場合は訪問済みのノードの集合も必要です。