二元樹走訪教學：前序、中序、後序與層序

為什麼走訪順序很重要

樹沒有唯一的自然順序，所以演算法會選擇適合任務的那一種。二元搜尋樹的中序走訪會依排序順序產生所有鍵。前序會先拜訪父節點再拜訪子節點，複製一棵樹或把它輸出成可重建的形式時就需要這個順序。後序會先拜訪子節點再拜訪父節點，刪除一棵樹、計算資料夾大小或求值運算式樹時就需要它。層序會最先找到最淺的節點，並能逐列印出一棵樹。

同一個範例的四種順序

我們使用這棵樹：根節點 1，子節點為 2 和 3；節點 2 的子節點是 4 和 5；節點 3 有一個右子節點 6。

        1
       / \
      2   3
     / \   \
    4   5   6

前三種有個簡單的記法：名稱說明了節點的位置。前（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]

用堆疊實作迭代式前序與中序

遞迴使用呼叫堆疊。為了避免在很深的樹上碰到遞迴上限，可以自己管理堆疊。前序的做法是：彈出一個節點、拜訪它，然後先 push 右子節點再 push 左子節點，這樣左子節點就會先被處理。

中序的做法是：盡可能往左走，沿途把節點 push 進去。當無法再往左時，彈出一個節點、拜訪它，然後移到它的右子節點。

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]

迭代式後序與層序

迭代式後序最難。有一個乾淨的做法是使用旗標：每個節點 push 兩次，第二次標記為「子節點處理完後即可拜訪」。層序則用佇列而不是堆疊；一次處理佇列中的一整層，也能順便得知每個節點的深度。

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]]

另一個常見的後序技巧：執行修改過的前序（節點、右、左），再把結果反轉。

時間與空間複雜度

這裡 n 是節點數，h 是高度，w 是最大寬度。對平衡樹而言，h 約為 log2(n)，w 可達約 n/2；對鏈狀的樹而言，h 是 n，w 是 1。

常見錯誤

• 在迭代式前序中先 push 左子節點再 push 右子節點。堆疊是 LIFO，想要先處理的子節點必須最後 push。
• 忘記處理空樹：每個函式在 root is None 時都應該回傳空的結果。
• 在層序中用 list 搭配 pop(0) 當佇列。每次 pop 是 O(n)；請改用 collections.deque。
• 在很深的樹上依賴遞迴。Python 會在遞迴上限（預設約 1000）時以 RecursionError 中止。
• 以為單一種走訪就能確定一棵樹。只有前序是有歧義的；前序加中序（且值互不相同）就足以重建出這棵樹。

何時使用哪一種走訪

前序、中序與後序都是深度優先搜尋的形式；層序則是套用在樹上的廣度優先搜尋。同樣的想法也可以延伸到一般的圖，只是這時還需要一個記錄已拜訪節點的集合。