Введение
Обход дерева — необходимая техника для работы с leetcode. И большинство разработчиков реализуют это с помощью рекурсии.
Рекурсия полезна. Но иногда это хлопотно.
Однажды я подумал: «Как реализовать обход дерева без рекурсии?».
В этой статье рассказывается, как это реализовать.
Что такое дерево?
Дерево — это фундаментальная структура данных. Пока не увижу, не поверю. Пожалуйста, смотрите следующую картинку.
- узел имеет много дочерних узлов.
- узел имеет только один родительский узел.
Это Дерево.
Некоторые из вас могут понять это. Он широко используется.
Например.
- файловая система (каталог)
- DNS
- индекс БД
В этой статье рассматриваются только первичные деревья. Так что, если вас интересуют подробности, пожалуйста, поищите их.
Что такое BFS (поиск в ширину)?
BFS — это обход дерева. Буквально, он пересекает узлы в ширину.
порядок узлов траверсы: 40 -> 30 -> 50 -> 25 -> 35 -> 45 -> 60 -> 15 -> 28 -> 55 -> 70
Прежде чем реализовать это, давайте организуем обработку во времени.
- Выберите корневой узел.
- Проверьте, есть ли у узла дети. если да, то добавьте их в список, надо проверить.
- выберите узел, добавленный в список последним.
- перейти к 1
Код…
Что такое DFS (поиск в глубину)?
Обход, который фокусируется на глубине. есть три типа.
Предварительный заказ
40 -> 30 -> 25 -> 15 -> 28 -> 35 -> 50 -> 45 -> 60 -> 55 -> 70
- проверьте корневой узел и значение
- переместите левый узел и проверьте значение
- если нет левого узла, сделайте шаг назад и проверьте правый узел
- если мы проверяем уже проверенный узел, пропускаем его.
- петля
Чтобы
15 -> 25 -> 28 -> 30 -> 35 -> 40 -> 45 -> 50 -> 55 -> 60 -> 70
- продолжайте двигаться, пока не достигнет узла, у которого нет левого узла.
- если узел без левого узла, проверьте значение
- Если узел еще не проверен, мы проверяем его значение.
- проверьте его правый узел.
- петля
Почтовый заказ
15 -> 28 -> 25 -> 35 -> 30 -> 45 -> 55 -> 70 -> 60 -> 50
- продолжайте двигаться, пока не достигнет узла, у которого нет левого узла.
- если нет левого узла, проверьте значение.
- сделайте шаг назад и переместите правый узел и проверьте значение.
- сделайте шаг назад и проверьте значение узла.
- петля
Окончательно
Я обычно реализую их с рекурсией. Итак, познавательно искать шаблоны реализации.
Я надеюсь, что эта статья поможет вам.