Обход по предварительному заказу — это фундаментальная операция в древовидных структурах данных, которая предполагает посещение корневого узла раньше его дочерних узлов. Хотя наиболее распространенный подход к реализации обхода по предварительному порядку включает рекурсию, существуют альтернативные методы, предлагающие нерекурсивные решения, часто с использованием итерационных алгоритмов. В этой статье блога мы рассмотрим несколько нерекурсивных методов обхода предварительного заказа, попутно предоставляя примеры кода и пояснения.

Метод 1: итерационный подход на основе стека
Одним из популярных методов реализации нерекурсивного обхода предварительного заказа является использование стека. Идея состоит в том, чтобы поместить корневой узел в стек, а затем выполнять итерацию, пока стек не станет пустым. Во время каждой итерации мы извлекаем узел из стека, посещаем его, а затем помещаем в стек его правого дочернего узла (если есть), а затем левого дочернего узла (если есть). Это гарантирует, что левый дочерний элемент будет обработан перед правым в соответствии с порядком обхода предварительного заказа.

Вот пример реализации на Python:

def preorder_iterative(root):
    if not root:
        return

    stack = [root]

    while stack:
        node = stack.pop()
        visit(node)

        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

Метод 2: обход Морриса
Обход Морриса — это еще один нерекурсивный подход, который позволяет нам выполнять обход по предварительному заказу без явного использования стека. Это достигается путем временного изменения древовидной структуры. Основная идея состоит в том, чтобы установить временную связь между узлом и его предшественником, что позволит нам перемещаться по дереву без использования дополнительного пространства.

Вот пример реализации на Python:

def preorder_morris(root):
    current = root

    while current:
        if not current.left:
            visit(current)
            current = current.right
        else:
            predecessor = current.left

            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if not predecessor.right:
                visit(current)
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                current = current.right

Метод 3: использование структуры узлов с тегами
В этом подходе мы изменяем структуру узлов дерева, добавляя поле «тег». Этот тег используется для отслеживания статуса прохождения каждого узла. Используя этот тег, мы можем эффективно выполнить нерекурсивный обход предварительного заказа.

Вот пример реализации на Python:

class TaggedNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.tag = 'unvisited'
def preorder_tagged(root):
    stack = [root]

    while stack:
        node = stack.pop()

        if node:
            if node.tag == 'unvisited':
                visit(node)
                node.tag = 'visited'
                stack.append(node.right)
                stack.append(node.left)
            else:
                stack.append(None)

В этой статье мы исследовали несколько нерекурсивных методов выполнения предварительного обхода в древовидных структурах данных. Мы обсудили итеративный подход на основе стека, обход Морриса и метод, использующий структуру узлов с тегами. Каждый метод предоставляет свой способ достижения желаемого результата, не полагаясь на рекурсивные вызовы функций. Понимая и реализуя эти нерекурсивные методы, разработчики могут получить большую гибкость и контроль над алгоритмами обхода дерева.