Обход двоичного дерева¶
С точки зрения физической структуры дерево представляет собой разновидность структуры данных на основе связей, поэтому его обход выполняется через последовательный доступ к узлам по указателям. Однако дерево является нелинейной структурой данных, а значит, его обход сложнее, чем обход связного списка, и для него требуется использовать поисковые алгоритмы.
К распространенным способам обхода двоичного дерева относятся обход по уровням, прямой обход, симметричный обход и обратный обход.
Обход по уровням¶
Как показано на рисунке ниже, обход по уровням (level-order traversal) проходит двоичное дерево сверху вниз по уровням и на каждом уровне посещает узлы слева направо.
По своей сути обход по уровням относится к обходу в ширину (breadth-first traversal), также называемому поиском в ширину (breadth-first search, BFS). Он отражает идею «расширяться от центра к периферии слой за слоем».
Код реализации¶
Обход в ширину обычно реализуется с помощью «очереди». Очередь подчиняется правилу «первым пришел - первым вышел», а обход в ширину подчиняется правилу «продвигаться по уровням», поэтому стоящая за ними идея согласована. Код реализации приведен ниже:
Анализ сложности¶
- Временная сложность равна \(O(n)\) : все узлы посещаются по одному разу, поэтому требуется \(O(n)\) времени, где \(n\) - число узлов.
- Пространственная сложность равна \(O(n)\) : в худшем случае, то есть для полной двоичной деревообразной структуры, до достижения самого нижнего уровня в очереди одновременно может находиться до \((n + 1) / 2\) узлов, что требует \(O(n)\) памяти.
Прямой, симметричный и обратный обходы¶
Соответственно, прямой, симметричный и обратный обходы относятся к обходу в глубину (depth-first traversal), также называемому поиском в глубину (depth-first search, DFS). Он отражает идею «сначала идти до конца, затем возвращаться и продолжать».
На рисунке ниже показан принцип работы обхода двоичного дерева в глубину. Обход в глубину можно представить как обход всей двоичной структуры по внешнему контуру , и у каждого узла встречаются три позиции, соответствующие прямому, симметричному и обратному обходам.
Код реализации¶
Поиск в глубину обычно реализуется через рекурсию:
Tip
Поиск в глубину можно реализовать и итеративно. Заинтересованные читатели могут изучить это самостоятельно.
На рисунке ниже показан рекурсивный процесс прямого обхода двоичного дерева. Его можно разделить на две противоположные части: «вход в рекурсию» и «возврат».
- «Вход в рекурсию» означает запуск нового вызова функции. В этом процессе программа переходит к следующему узлу.
- «Возврат» означает завершение вызова функции и возврат назад, то есть текущий узел уже полностью обработан.
Анализ сложности¶
- Временная сложность равна \(O(n)\) : все узлы посещаются по одному разу, поэтому требуется \(O(n)\) времени.
- Пространственная сложность равна \(O(n)\) : в худшем случае, когда дерево вырождается в связный список, глубина рекурсии достигает \(n\) , и система тратит \(O(n)\) памяти на стек вызовов.