Обход дерева в глубину (DFS)

Обход дерева в глубину (DFS)

DFS (Depth-First Search) — это алгоритм обхода графа или дерева, который углубляется максимально по одной ветке перед тем, как перейти на другую. Существует три основных варианта DFS для бинарного дерева:

1. Preorder (корень → левое → правое) — посетить корень, затем левое поддерево, затем правое
2. Inorder (левое → корень → правое) — посетить левое поддерево, затем корень, затем правое
3. Postorder (левое → правое → корень) — посетить левое поддерево, затем правое, затем корень

Определение класса узла

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

Preorder DFS (Рекурсивный)

def dfs_preorder(node):
    """
    Обход дерева в глубину (preorder).
    Порядок: корень → левое поддерево → правое поддерево
    """
    if node is None:
        return []
    
    result = [node.value]  # Сначала добавляем корень
    result.extend(dfs_preorder(node.left))   # Затем левое поддерево
    result.extend(dfs_preorder(node.right))  # Затем правое поддерево
    return result

# Пример использования
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(dfs_preorder(root))  # [1, 2, 4, 5, 3]

Inorder DFS (Рекурсивный)

def dfs_inorder(node):
    """
    Обход дерева в глубину (inorder).
    Порядок: левое поддерево → корень → правое поддерево
    """
    if node is None:
        return []
    
    result = []
    result.extend(dfs_inorder(node.left))    # Сначала левое поддерево
    result.append(node.value)                 # Затем корень
    result.extend(dfs_inorder(node.right))   # Затем правое поддерево
    return result

# Пример использования
print(dfs_inorder(root))  # [4, 2, 5, 1, 3]

Postorder DFS (Рекурсивный)

def dfs_postorder(node):
    """
    Обход дерева в глубину (postorder).
    Порядок: левое поддерево → правое поддерево → корень
    """
    if node is None:
        return []
    
    result = []
    result.extend(dfs_postorder(node.left))   # Сначала левое поддерево
    result.extend(dfs_postorder(node.right))  # Затем правое поддерево
    result.append(node.value)                  # Затем корень
    return result

# Пример использования
print(dfs_postorder(root))  # [4, 5, 2, 3, 1]

Iterative DFS с Stack (Preorder)

Рекурсивный подход может вызвать переполнение стека для больших деревьев. Вот итеративный вариант:

def dfs_preorder_iterative(root):
    """
    Итеративный обход в preorder с использованием стека.
    """
    if root is None:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()  # Берём с конца (LIFO)
        result.append(node.value)
        
        # Добавляем в стек СНАЧАЛА правое (оно будет обработано вторым)
        # Затем левое (оно будет обработано первым)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

print(dfs_preorder_iterative(root))  # [1, 2, 4, 5, 3]

Iterative DFS с Stack (Inorder)

def dfs_inorder_iterative(root):
    """
    Итеративный обход в inorder с использованием стека.
    """
    result = []
    stack = []
    node = root
    
    while node or stack:
        # Идём до самого левого узла
        while node:
            stack.append(node)
            node = node.left
        
        # Левого узла нет, берём из стека
        node = stack.pop()
        result.append(node.value)
        
        # Переходим к правому поддереву
        node = node.right
    
    return result

print(dfs_inorder_iterative(root))  # [4, 2, 5, 1, 3]

Iterative DFS с Stack (Postorder)

def dfs_postorder_iterative(root):
    """
    Итеративный обход в postorder с использованием двух стеков.
    """
    if root is None:
        return []
    
    result = []
    stack1 = [root]
    stack2 = []
    
    # Используем два стека для изменения порядка обхода
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    
    while stack2:
        node = stack2.pop()
        result.append(node.value)
    
    return result

print(dfs_postorder_iterative(root))  # [4, 5, 2, 3, 1]

Визуализация примера

    1
   / \
  2   3
 / \
4   5

Preorder (корень → левое → правое):  1, 2, 4, 5, 3
Inorder (левое → корень → правое):   4, 2, 5, 1, 3
Postorder (левое → правое → корень):  4, 5, 2, 3, 1

Сравнение подходов

Полный рабочий пример с тестами

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

def dfs_preorder(node):
    if node is None:
        return []
    result = [node.value]
    result.extend(dfs_preorder(node.left))
    result.extend(dfs_preorder(node.right))
    return result

def dfs_inorder(node):
    if node is None:
        return []
    result = []
    result.extend(dfs_inorder(node.left))
    result.append(node.value)
    result.extend(dfs_inorder(node.right))
    return result

def dfs_postorder(node):
    if node is None:
        return []
    result = []
    result.extend(dfs_postorder(node.left))
    result.extend(dfs_postorder(node.right))
    result.append(node.value)
    return result

# Создание примера дерева
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Тестирование
print("Preorder:", dfs_preorder(root))   # [1, 2, 4, 5, 3]
print("Inorder:", dfs_inorder(root))     # [4, 2, 5, 1, 3]
print("Postorder:", dfs_postorder(root)) # [4, 5, 2, 3, 1]

# Проверка
assert dfs_preorder(root) == [1, 2, 4, 5, 3]
assert dfs_inorder(root) == [4, 2, 5, 1, 3]
assert dfs_postorder(root) == [4, 5, 2, 3, 1]
print("\nВсе тесты пройдены!")

Когда использовать каждый вариант

• Preorder: создание копии дерева, сериализация
• Inorder: получение отсортированных значений из BST (бинарного дерева поиска)
• Postorder: удаление дерева, вычисление высоты поддеревьев