В предыдущих частях мы познакомились с рекурсивным подходом решения деревьев. В этой части мы воспользуемся стэком.
Рекурсия далека от идеала.
Рекурсия чаще всего используется только во время собеседований (а этот цикл статей именно направлен на подгтовку к собеседования). В промышленной разработке её чаще избегают изза потенциальных следующих потенциальных проблем:
- Криво написанная рекурсия может выполняться бесконечно (в "лучшем" случае это приведет к ошибке переполнения стэка). В худшем программа повиснет (особенно если программа однопоточная).
- Изначально чаще всего под стэк выделяется не более 1мб памяти а это значит что рекурсивная функция сможет вызвать саму себя где то от 10 до 20 тысяч раз. (размер можно легко увеличить с помощью параметра -Xss но стоит помнить что у JDK есть ограничения по верхней границе - обычно до 1 ГБ)
- Рекурсия сложна для понимания, особенно новичкам.
- Высокое потребление памяти - каждый раз спуская на уровень ниже мы позволяем сборщику мусора удалить ссылки используемые на верхних уровнях - и это не ошибка тк все объекты используемы выше текущего уровня будут использованы когда мы вернемся "снизу"
Очеред (или Стэк) - популярный подход в решении задач на деревья.
Во многом, задача на деревья определяется тем, как мы можем проитерироваться по всем узлам. В рекурсии мы вызываем рекурсивную функцию и передаем ей наследники. В случае же с очередью или стэком мы используем следующий трюк:
- Добавляем корневой элемент в очередь
- Проходим по всем элементам очереди и ранее добавленные узлы
- Если наследники узла не пусты добавляем в очередь опять
Обходим дерево в ширину.
Распечатаем все значения дерева сверху вниз, распечатывая значения на каждом уровне слева направо, как гирлянду.
Желаемый порядок распечатки - сверху вниз, слева направо.
Что такое очередь и как ей пользоваться?
Для начала познакомимся с интерфейсом очереди (Queue) в Java. Очередь представляет собой FIFO (first in, first out - первый зашёл, первый вышел) структуру. В нашем случае потребуется два метода:
- add - добавить в очередь
- poll - вытащить первого из очереди (элемент который бы добавлен раньше других)
Как именно мы будем выполнять обход дерева?
Обходить дерево мы будем следующим способом:
- Добавим в очередь корневой элемент
- "Вытащим" добавленный элемент и положим в очередь его наследников
- Повторим 1-2 шаги пока в очереди ничего не останется
Изобразим эти действя по шагам:
Движемся слева направо. Красными стрелками указаны "вытаскиваемые" из очереди элементы.
На графике выше вы могли бы заметить, что после момента добавления 4-х элементов больше элементы не добавляются, так как у каждого из 4-х узлов нет наследников.
Теперь напишем код описанной выше логике
И так как запомнить данный подход если он попадется на собеседовании? Я бы рекомендовал держать в памяти две вещи:
- условие while (!queue.isEmpty())
- queue.poll() - вытаскивание элемента
В следующих статьях мы будем использовать очередь для решения задач, связанных с деревьями. Кому интересна промышленная разработку приглашаю в котовскую телеграм группу