Введение

Обход дерева — необходимая техника для работы с leetcode. И большинство разработчиков реализуют это с помощью рекурсии.

Рекурсия полезна. Но иногда это хлопотно.

Однажды я подумал: «Как реализовать обход дерева без рекурсии?».

В этой статье рассказывается, как это реализовать.

Что такое дерево?

Дерево — это фундаментальная структура данных. Пока не увижу, не поверю. Пожалуйста, смотрите следующую картинку.

  • узел имеет много дочерних узлов.
  • узел имеет только один родительский узел.

Это Дерево.

Некоторые из вас могут понять это. Он широко используется.

Например.

  • файловая система (каталог)
  • DNS
  • индекс БД

В этой статье рассматриваются только первичные деревья. Так что, если вас интересуют подробности, пожалуйста, поищите их.

Что такое BFS (поиск в ширину)?

BFS — это обход дерева. Буквально, он пересекает узлы в ширину.

порядок узлов траверсы: 40 -> 30 -> 50 -> 25 -> 35 -> 45 -> 60 -> 15 -> 28 -> 55 -> 70

Прежде чем реализовать это, давайте организуем обработку во времени.

  1. Выберите корневой узел.
  2. Проверьте, есть ли у узла дети. если да, то добавьте их в список, надо проверить.
  3. выберите узел, добавленный в список последним.
  4. перейти к 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

  • продолжайте двигаться, пока не достигнет узла, у которого нет левого узла.
  • если нет левого узла, проверьте значение.
  • сделайте шаг назад и переместите правый узел и проверьте значение.
  • сделайте шаг назад и проверьте значение узла.
  • петля

Окончательно

Я обычно реализую их с рекурсией. Итак, познавательно искать шаблоны реализации.

Я надеюсь, что эта статья поможет вам.