跳轉到

5.1 二元樹的走訪#

概念說明#

走訪（traversal）是「把樹上每個節點拜訪一次」的套路，是一切樹演算法的地基。二元樹有四種經典順序：

  • 前序（preorder）：根 → 左子樹 → 右子樹。適合「複製樹、序列化」。
  • 中序（inorder）：左子樹 → 根 → 右子樹。對 BST 而言輸出由小到大的排序結果。
  • 後序（postorder）：左子樹 → 右子樹 → 根。適合「先算子樹再合併」，如目錄大小統計、釋放樹。
  • 層序（level-order）：一層一層由左至右，用佇列實作，屬於廣度優先。

前三者是深度優先（DFS），差別只在「根」被拜訪的相對位置；層序用佇列，前三者用遞迴或堆疊。

Python 實作#

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

def preorder(node, out):
    if node:
        out.append(node.val)
        preorder(node.left, out)
        preorder(node.right, out)

def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)

def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.val)

def level_order(root):
    from collections import deque
    out, q = [], deque([root] if root else [])
    while q:
        node = q.popleft()
        out.append(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out

# 建一棵樹：      1
#              /   \
#             2     3
#            / \     \
#           4   5     6
root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
root.left.left, root.left.right = TreeNode(4), TreeNode(5)
root.right.right = TreeNode(6)

for name, fn in [("前序", preorder), ("中序", inorder), ("後序", postorder)]:
    out = []
    fn(root, out)
    print(f"{name}: {out}")
print(f"層序: {level_order(root)}")
# 前序: [1, 2, 4, 5, 3, 6]
# 中序: [4, 2, 5, 1, 3, 6]
# 後序: [4, 5, 2, 6, 3, 1]
# 層序: [1, 2, 3, 4, 5, 6]

迭代版（用堆疊）與實用衍生#

遞迴本質上靠呼叫堆疊；改用顯式堆疊可寫成迭代版，也能順手寫出「樹高」等實用函式：

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 height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

print(preorder_iter(root))   # [1, 2, 4, 5, 3, 6]
print(height(root), count_nodes(root))   # 3 6

複雜度分析#

四種走訪都拜訪每個節點恰一次，時間 O(n)。空間：遞迴/堆疊版為 O(h)（h 為樹高，最壞鏈狀 O(n)、平衡 O(log n)）；層序的佇列最壞 O(n)（最寬一層）。

練習#

  1. 實作中序的迭代版（用堆疊一路壓左子孫、pop 拜訪、再轉向右子樹）。
  2. 兩棵樹的「中序 + 前序」可唯一重建樹，但「中序 + 後序」也可以，「前序 + 後序」不行。請用 n=2 的例子說明原因。
  3. 實作 zigzag_level_order：層序但奇數層反向輸出（第一層左→右、第二層右→左…）。