Обход бинарного дерева является основным элементом процесса технического собеседования во многих компаниях-разработчиках программного обеспечения, малых и крупных. Для любого, кто понимает рекурсию, семейство методов обхода довольно просто. Обычный поворот этих концепций, который больше проявляется в технических интервью, чем в наборах задач бакалавриата по информатике, - это довольно искусственное ограничение, которое требует реализации обходов с использованием итерации, а не рекурсии.
Я всегда находил эталонные реализации итеративного обхода дерева, особенно неупорядоченного обхода, лишенными интуитивного понимания. Классический способ итеративного обхода бинарного дерева заключается в использовании структуры данных стека, и первый фрагмент кода, который вы часто видите, выглядит примерно так:
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 г.