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

Дерево — это широко используемая структура данных в мире программирования. Эта структура, как и ее название, имеет ветви и подразделения, где каждый элемент в дереве называется узлом .

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

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

  • root : Первый узел дерева (обычно изображается как самый верхний узел).
  • parent : каждый узел, от которого идет ветвь, называется родительский элемент для последующих узлов.
  • children : узлы, которые отходят от родительского узла, называются дочерними элементами ; дочерний элемент left и right в зависимости от размещения узла.

Типы обходов

Глубинные обходы

  • Inorder : сначала вы проходите левый дочерний элемент и его поддерево, посетите корень, а затем правый дочерний элемент и его поддерево.
  • Предзаказ : сначала посетите корень, затем пройдитесь по левому поддереву, а затем по правому поддереву.

v>

  • Postorder : пройти левое поддерево, затем пройти правое поддерево и затем посетить корневой узел .

Обходы по ширине

  • Порядок уровней : пересекает узлы по уровням, а не по поддеревьям.. Сначала посетите корневой узел; затем посетите всех дочерних узлов корневого узла слева направо. Затем спускайтесь по уровням, пока не дойдете до узла, у которого нет дочерних узлов — конечных узлов.
Оцените статью
nanomode.ru
Добавить комментарий