Зачем разные обходы

Обход дерева — это посещение каждого узла ровно один раз. Звучит просто. Но порядок посещения важен: для разных задач нужен разный порядок.

Четыре главных обхода:

1. Pre-order (NLR): корень -> left -> right.
2. In-order (LNR): left -> корень -> right.
3. Post-order (LRN): left -> right -> корень.
4. Level-order (BFS): по уровням, сверху вниз.

Первые три — варианты DFS (depth-first search, поиск в глубину). Четвёртый — BFS (breadth-first search, поиск в ширину). Разница принципиальная — и в реализации, и в применении.

Pre-order: корень первым

def pre_order(node):
    if node is None:
        return
    print(node.value)            # обработать корень
    pre_order(node.left)         # потом левое поддерево
    pre_order(node.right)        # потом правое

Применения:

• Клонирование дерева: создаём новый узел (на корне), потом рекурсивно создаём поддеревья. Pre-order естественно подходит.
• Сериализация дерева: записываем структуру сверху вниз.
• Печать иерархии с отступами: каталог, организационная структура.

def print_tree(node, indent=0):
    if node is None:
        return
    print("  " * indent + str(node.value))
    print_tree(node.left, indent + 1)
    print_tree(node.right, indent + 1)

In-order: между поддеревьями

def in_order(node):
    if node is None:
        return
    in_order(node.left)          # сначала левое
    print(node.value)            # потом корень
    in_order(node.right)         # потом правое

Главное применение — это обход BST в отсортированном порядке. По BST-инварианту left < node < right, и in-order рекурсивно даёт left_values, node, right_values, где left_values уже сортированы. По индукции — всё отсортировано.

# у нас BST с ключами
# in-order даёт: 1, 3, 5, 7, 9, 12, 15 — отсортированно

Это используется в SQL: SELECT ... ORDER BY column где column имеет B-tree индекс — БД делает in-order traversal индекса.

Post-order: дети раньше родителя

def post_order(node):
    if node is None:
        return
    post_order(node.left)        # сначала левое
    post_order(node.right)       # потом правое
    print(node.value)            # корень в конце

Применения:

• Удаление дерева: чтобы освободить узел, сначала нужно освободить его поддеревья (иначе ссылки потеряются). Post-order естественен.
• Вычисление выражений в expression tree: чтобы вычислить узел +, нужно сначала вычислить его left и right.
• Размер поддерева: подсчёт count(node) = 1 + count(left) + count(right) — естественно post-order.

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

def tree_height(node):
    if node is None:
        return -1
    return 1 + max(tree_height(node.left), tree_height(node.right))

Все «вычислить характеристику поддерева» функции — post-order: нужны результаты детей.

Level-order (BFS): по уровням

DFS-обходы естественно рекурсивные. BFS — итеративный, использует очередь (queue):

from collections import deque

def level_order(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Логика: положить root в очередь. Пока очередь не пуста — взять переднего, обработать, положить детей в конец. Это даёт обход по уровням: сначала все узлы depth 0, потом все depth 1, и так далее.

Применения:

• Кратчайший путь от root: BFS находит ближайший узел до целевого с минимальной depth.
• Печать дерева по уровням (визуализация).
• Поиск ближайшего к root узла с заданным свойством.

DFS итеративно — со стеком

Можно сделать DFS без рекурсии, используя стек:

def pre_order_iter(root):
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.value)
        # right кладём раньше — чтобы left достался первым
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

Зачем итеративная версия? Чтобы избежать stack overflow при глубоких деревьях. У Python default recursion limit = 1000. Skewed дерево из 10000 узлов вызовет RecursionError.

import sys
sys.setrecursionlimit(100_000)   # workaround, не идеальный

Лучше — итеративная версия с явным стеком. Стек живёт в heap’е, не в call-stack’е, и может расти до гигабайтов.

Сложность

Все обходы:

• Время: O(N) — каждый узел посещается ровно раз, операции внутри посещения O(1).
• Память: O(h) для рекурсивных DFS (стек вызовов), O(N) для BFS (очередь может содержать до N/2 узлов на самом широком уровне).

Для сбалансированного дерева:

• h ≈ log N — DFS space O(log N), отлично.
• W ≈ N/2 (последний уровень) — BFS space O(N), хуже.

Для skewed:

• h ≈ N — DFS space O(N), плохо (риск stack overflow).
• W = 1 — BFS space O(1).

То есть выбор обхода влияет и на корректность (stack overflow), и на память.

DFS vs BFS: когда какой

Эксперимент: измерим обходы

import time
from collections import deque
import sys
sys.setrecursionlimit(100_000)

class Node:
    __slots__ = ('v', 'l', 'r')
    def __init__(self, v):
        self.v = v
        self.l = None
        self.r = None

def build_balanced(n):
    """Создаёт balanced BST из 1..n"""
    def helper(lo, hi):
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        node = Node(mid)
        node.l = helper(lo, mid - 1)
        node.r = helper(mid + 1, hi)
        return node
    return helper(1, n)

root = build_balanced(1_000_000)

def in_order_rec(node, acc):
    if node is None:
        return
    in_order_rec(node.l, acc)
    acc.append(node.v)
    in_order_rec(node.r, acc)

def in_order_iter(node):
    stack = []
    acc = []
    while node or stack:
        while node:
            stack.append(node)
            node = node.l
        node = stack.pop()
        acc.append(node.v)
        node = node.r
    return acc

def level_order(root):
    if not root:
        return []
    q = deque([root])
    acc = []
    while q:
        n = q.popleft()
        acc.append(n.v)
        if n.l: q.append(n.l)
        if n.r: q.append(n.r)
    return acc

start = time.perf_counter()
acc = []
in_order_rec(root, acc)
print(f"in_order_rec:  {(time.perf_counter()-start)*1000:.0f} ms, {len(acc)} items")

start = time.perf_counter()
acc = in_order_iter(root)
print(f"in_order_iter: {(time.perf_counter()-start)*1000:.0f} ms, {len(acc)} items")

start = time.perf_counter()
acc = level_order(root)
print(f"level_order:   {(time.perf_counter()-start)*1000:.0f} ms, {len(acc)} items")

Ожидаемые результаты на M-class CPU:

• in_order_rec: ~300 ms (рекурсия в Python медленнее из-за overhead функции)
• in_order_iter: ~200 ms (без overhead вызовов)
• level_order: ~400 ms (deque чуть медленнее, потому что N/2 узлов в очереди одновременно — больше allocs)

Применения в DE

Сериализация в JSON — pre-order

Любой JSON-encoder делает pre-order по дереву объектов:

import json

data = {"a": {"b": 1, "c": [2, 3]}}
json.dumps(data)
# обход: root, потом a, потом b, потом c, потом [2, 3]

SQL ORDER BY — in-order

Когда вы пишете SELECT * FROM t ORDER BY id, и на id есть B-tree индекс, БД делает in-order обход индекса. Это даёт отсортированный результат без отдельной сортировки.

Merge tree в LSM — level-order

В RocksDB / Cassandra данные хранятся в multiple SSTable’ах, организованных по уровням (L0, L1, L2, …). Compaction обходит уровни сверху вниз — это level-order.

Попробуй сам

class Node:
    def __init__(self, v):
        self.v = v
        self.l = None
        self.r = None

# дерево:
#       1
#      / \
#     2   3
#    /\   /\
#   4 5  6 7

root = Node(1)
root.l = Node(2)
root.r = Node(3)
root.l.l = Node(4)
root.l.r = Node(5)
root.r.l = Node(6)
root.r.r = Node(7)

# 1. Реализуйте все 4 обхода и проверьте порядок
def pre(n):
    if not n: return
    print(n.v, end=' ')
    pre(n.l)
    pre(n.r)

def ino(n):
    if not n: return
    ino(n.l)
    print(n.v, end=' ')
    ino(n.r)

def post(n):
    if not n: return
    post(n.l)
    post(n.r)
    print(n.v, end=' ')

from collections import deque
def level(root):
    if not root: return
    q = deque([root])
    while q:
        n = q.popleft()
        print(n.v, end=' ')
        if n.l: q.append(n.l)
        if n.r: q.append(n.r)

print("pre:    ", end=''); pre(root); print()    # 1 2 4 5 3 6 7
print("in:     ", end=''); ino(root); print()    # 4 2 5 1 6 3 7
print("post:   ", end=''); post(root); print()   # 4 5 2 6 7 3 1
print("level:  ", end=''); level(root); print()  # 1 2 3 4 5 6 7

# 2. Сделайте все три DFS итеративно (через стек)
# Pre-order — уже показан выше. In-order и post-order — упражнение.

# 3. Найдите глубину дерева через BFS (level-order считает уровни)
def depth_bfs(root):
    if not root: return 0
    q = deque([(root, 0)])
    max_d = 0
    while q:
        n, d = q.popleft()
        max_d = max(max_d, d)
        if n.l: q.append((n.l, d + 1))
        if n.r: q.append((n.r, d + 1))
    return max_d

print(f"depth = {depth_bfs(root)}")   # 2

В следующем уроке разберём BST (binary search tree) — самое популярное применение бинарного дерева. Узнаем инвариант, операции search/insert, и почему BST может выродиться в связный список.