June 2nd, 2021

Что такое обход дерева

Начало:
1. Учебник по JavaScript: структуры данных
2. Учебник по JavaScript, структура данных «дерево»

О том, что такое структура данных «дерево», было в предыдущих постах.

Что такое «обход дерева» (по-английски «tree traversal» или «tree search» или «walking the tree»)? Под этим подразумевается процесс посещения каждого узла (с целью некой обработки данных, хранящихся в узле) дерева. Предполагается, что каждый узел при этом будет посещён только один раз.

https://ru.wikipedia.org/wiki/Обход_дерева
https://en.wikipedia.org/wiki/Tree_traversal

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

Так как дерево является рекурсивной (рекурсивно определяемой) структурой данных (это такая структура данных, которая повторяет саму себя в своих частях), то обычно рассмотрение алгоритмов обхода дерева в пособиях начинают с обхода с использованием рекурсии. С одной стороны, рекурсивный способ обхода самый простой, но, с другой стороны, при слишком больших деревьях этот способ может вызвать переполнение стека вызовов (вики). Об этом подробнее можно почитать в подразделе 6.1 «Рекурсия и стек» учебника по JavaScript.

Но я хочу начать с алгоритма обхода дерева без рекурсии.

Из-за того, что каждый узел дерева может иметь несколько потомков (в отличие от линейных структур данных типа массивов или линейных односвязных списков), при обходе дерева в определенные моменты приходится выбирать какое-либо одно из нескольких направлений дальнейшего обхода, оставляя (запоминая) другие варианты на потом, как в лабиринте (в принципе, по идее, любой лабиринт можно представить в виде графа, как и дерево). Чтобы запоминать «другие варианты», нам потребуется реализовать «память», в которой мы их будем запоминать. Для этого я буду использовать в программе на языке JavaScript стек на основе массива и его методов push (положить в память, то есть «запомнить») и pop (взять из памяти, то есть «вспомнить»). Подробнее об этом можно почитать в подразделе 5.4 «Массивы» учебника по JavaScript.

Стоит упомянуть, что для реализации памяти при обходе дерева может быть использован не только стек (вики) (построенный по принципу «LIFO» — «последним вошёл, первым вышел»), но и очередь (вики) (построенная по принципу «FIFO» — «первым вошёл, первым вышел»).

Если внимательно рассмотреть рисунок любого дерева, то можно заметить, что его обход можно выполнять в глубину и в ширину. Что это значит? Рассмотрим следующую иллюстрацию:


На этой иллюстрации целые числа внутри узлов уже не являются данными, хранящимися в этих узлах, как было в предыдущем посте. Здесь они показывают порядок обхода узлов в дереве. На этой иллюстрации показаны два из множества возможных способов обхода узлов в дереве. Слева — способ обхода в глубину (по-английски «depth-first search», сокращенно «DFS»), справа — способ обхода в ширину (по-английски «breadth-first search», сокращенно «BFS»; или «level order»).

https://ru.wikipedia.org/wiki/Поиск_в_глубину
https://ru.wikipedia.org/wiki/Поиск_в_ширину

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

Очевидно, что в теории может быть несколько вариантов обхода в глубину в зависимости от того, какая ветвь (самая правая, самая левая, одна из центральных) выбирается в первую очередь на каждой развилке. На иллюстрации ветви (ссылки) выбираются на каждом узле (каждой развилке) при обходе дерева в глубину с приоритетом справа налево.

При обходе дерева в ширину узлы обрабатываются поуровнево. То есть сначала обрабатывается корень, потом узлы второго уровня, затем — третьего и так далее. На каждом уровне мы сначала помещаем узлы уровня в «память», затем последовательно их обрабатываем, пока память не опустеет.

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

В качестве «памяти» для запоминания узлов при обходе в глубину удобно использовать стек, а при обходе в ширину — очередь, это отмечено на иллюстрации.