Duyệt cây nhị phân: preorder, inorder, postorder và level order

Tại sao thứ tự duyệt quan trọng

Cây không có một thứ tự tự nhiên duy nhất, nên thuật toán chọn thứ tự phù hợp với bài toán. Duyệt inorder một cây tìm kiếm nhị phân cho ra các khóa theo thứ tự tăng dần. Preorder thăm cha trước con, đúng thứ bạn cần để sao chép cây hoặc ghi cây ra để dựng lại được. Postorder thăm con trước cha, đúng thứ bạn cần để xóa cây, tính kích thước thư mục hoặc tính giá trị cây biểu thức. Level order tìm node nông nhất trước và in cây theo từng hàng.

Bốn thứ tự trên cùng một ví dụ

Ta dùng cây này: gốc 1 có hai con là 2 và 3; node 2 có hai con là 4 và 5; node 3 có con phải là 6.

        1
       / \
      2   3
     / \   \
    4   5   6

Cách nhớ ba thứ tự đầu đơn giản: tên cho biết node nằm ở đâu. Pre là trước cả hai cây con, in là giữa hai cây con, post là sau cả hai. Cây con trái luôn được thăm trước cây con phải.

Cài đặt đệ quy

Các phiên bản đệ quy phản ánh trực tiếp định nghĩa. Mỗi hàm thăm node ở một dòng khác nhau.

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]

Preorder và inorder dạng lặp với ngăn xếp

Đệ quy dùng ngăn xếp lời gọi. Để tránh giới hạn đệ quy trên cây sâu, hãy tự quản lý ngăn xếp. Với preorder, pop một node, thăm nó, rồi push con phải trước con trái để con trái được xử lý trước.

Với inorder, đi sang trái hết mức có thể, push các node trên đường đi. Khi không thể đi trái nữa, pop một node, thăm nó, rồi chuyển sang con phải của nó.

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]

Postorder và level order dạng lặp

Postorder dạng lặp là khó nhất. Một cách gọn dùng cờ: push mỗi node hai lần, lần thứ hai được đánh dấu là sẵn sàng thăm sau các con của nó. Level order dùng hàng đợi thay vì ngăn xếp; xử lý hàng đợi từng tầng một cũng cho biết độ sâu của mỗi node.

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

Một mẹo phổ biến khác cho postorder: chạy preorder đã chỉnh (node, phải, trái) rồi đảo ngược kết quả.

Độ phức tạp thời gian và không gian

Ở đây n là số node, h là chiều cao và w là độ rộng tối đa. Với cây cân bằng h khoảng log2(n) và w có thể khoảng n/2; với cây dạng chuỗi h là n và w là 1.

Lỗi thường gặp

• Push con trái trước con phải trong preorder dạng lặp. Ngăn xếp là LIFO, nên con bạn muốn thăm trước phải được push sau cùng.
• Quên cây rỗng: mọi hàm nên trả về kết quả rỗng khi root is None.
• Dùng list với pop(0) làm hàng đợi trong level order. Mỗi lần pop tốn O(n); hãy dùng collections.deque.
• Dựa vào đệ quy cho cây rất sâu. Python dừng ở giới hạn đệ quy (mặc định khoảng 1000) với RecursionError.
• Mong một cách duyệt đơn lẻ xác định được cây. Riêng preorder thì mơ hồ; preorder cộng inorder (với giá trị khác nhau) là đủ để dựng lại cây.

Khi nào dùng cách duyệt nào

Preorder, inorder và postorder đều là các dạng tìm kiếm theo chiều sâu; level order là tìm kiếm theo chiều rộng áp dụng cho cây. Cùng ý tưởng này mở rộng cho đồ thị tổng quát, nơi bạn còn cần một tập các node đã thăm.