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

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

stack = []
curr = root
while curr is not null || stack is not empty
    while curr is not null
        stack.push(curr)
        curr = curr.left
        ...

Когда я вижу этот код, у меня сразу возникает больше вопросов, чем понимания.

  • Почему код следует левым указателям, помещая все узлы в стек?
  • Почему условие цикла проверяется как на текущий узел, так и на размер стека?
  • Почему существует вложенный цикл while?

Для меня интуитивный способ рассуждать об итеративной реализации рекурсивной функции — это смоделировать стек вызовов, а это обычно начинается с ручки и бумаги. Например, предположим, что у нас есть бинарное дерево, которое выглядит так:

    A
   / \
  B   C
 / \
D   E

Неупорядоченный обход такого дерева должен давать узлы в следующем порядке: D, B, E, A, C. Лучший способ смоделировать стек вызовов, который приводит к такому обходу, — извлечь содержимое стека по мере прохождения обхода по дереву. Мне нравится моделировать свои стопки по образцу реального мира, с физической основой, указывающей на нижнюю часть стопки, и элементами, которые вставляются и выталкиваются. Вот визуализация пустого стека и его преобразование после двух операций push (push(A), push(B)) и одной операции pop (pop()):

                  B      ~B~
          A       A       A
_____   _____   _____   _____
stack   stack   stack   stack

В конце операций стек содержит единственный элемент B. Обозначения здесь помечают любые элементы, выскочившие из стека, зачеркнутыми маркерами (~), но оставляют их в стеке в исходном месте, чтобы лучше проиллюстрировать порядок. Теперь мы можем использовать эту нотацию для визуальной имитации первых нескольких шагов того, как может выглядеть неупорядоченный обход дерева примеров с использованием стандартного подхода поиск в глубину. Первоначально стек пуст, и корневой узел помещается в стек.

  A
_____
stack

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

                  B
                  A
                  C
  A      ~A~     ~A~
_____   _____   _____
stack   stack   stack

В этот момент B извлекается из стека и применяется та же логика. Обход продолжается вниз к левому дочернему элементу B, за которым следует посещение B и последующий обход правого дочернего элемента B. То есть push(E), push(B), push(D). Вот как выглядит стек после достижения первого конечного узла D:

                  D
                  B
                  E
  B      ~B~     ~B~
  A       A       A
  C       C       C
 ~A~     ~A~     ~A~
_____   _____   _____
stack   stack   stack

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

if the node has already been discovered
    "visit" or do something with the node
else
    mark the node as discovered
    push the right child of the node onto the stack
    push the node onto the stack
    push the left child of the node onto the stack

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

Чтобы проиллюстрировать процесс более наглядно, мы можем поместить узлы в стек с явным статусом: статус start указывает, что узел еще не обработан, и статус end указывает, что он был обработан. Например, A.start и A.end будут представлять начальное и конечное состояние для узла A соответственно. Вот та же визуализация для тех же первых нескольких операций, что и выше, с явными атрибутами состояния для каждого узла:

                       B.start
                       A.end
                       C.start
A.start   ~A.start~   ~A.start~
 _____      _____       _____
 stack      stack       stack

С этой расширенной нотацией логика, необходимая для обработки любого заданного узла на вершине стека, ясна. Если узел на вершине стека имеет статус start, поместите его правый потомок в стек со статусом start, поместите себя обратно в стек со статусом end и поместите его левый потомок в стек со статусом start.

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

def iterative_inorder_traversal(root):
    stack = []
    stack.append(root)
    discovered = {}
    while len(stack) > 0:
        node = stack.pop()
        if node in discovered:
            pass # "Visit" or do something with the node
        else:
            discovered[node] = True
            if node.right:
                stack.append(node.right)
            stack.append(node)
            if node.left:
                stack.append(node.left)

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

Первоначально опубликовано на https://www.kelvinjiang.com 23 октября 2019 г.