Все, что вам нужно знать об обходе дерева за 7 минут (с анимацией)
Если вы профессиональный программист или много лет работаете в индустрии программного обеспечения, эта тема может показаться вам очень тривиальной. Но варианты использования таких алгоритмов и их различные варианты могут ввести в заблуждение новичков. Поэтому я попытался изложить все, что вам нужно знать об обходе дерева, в этой единственной статье (с анимацией).
«Анимация может объяснить все, что может вообразить человеческий разум. Это средство делает его наиболее универсальным и понятным средством коммуникации, разработанным для быстрого массового признания », - Уолт Дисней
Эта статья не только о теориях вокруг таких алгоритмов, но и о том, как реализовать эти алгоритмы с помощью кода.
Лента новостей
- Древовидная структура данных
- Обход дерева - Введение
- Давайте углубимся - Практическое руководство
- Inorder Traversal
- Предварительный заказ
- Пост порядковый обход
- Обход порядка уровней
- Заключительные примечания
1. Древовидная структура данных
Прежде чем переходить к алгоритмам обхода дерева, давайте сначала определим Tree как структуру данных. Это поможет вам осмысленно понять концепции.
Дерево - это иерархическая структура данных, в которой информация хранится естественным образом в виде иерархии, в отличие от линейных структур данных, таких как Связанный список, Стек и т. д. Дерево содержит узлы (данные) и соединения (ребра), которые должны не образуют цикла.
Ниже приведены несколько часто используемых терминов для древовидной структуры данных.
Узел - узел - это структура, которая может содержать значение или условие или представлять отдельную структуру данных.
Корень - верхний узел в дереве, первичный предок.
Дочерний: узел, непосредственно связанный с другим узлом при удалении от корня, непосредственный потомок.
Родитель - обратное понятие ребенка, непосредственного предка.
Лист - узел без дочерних элементов.
Внутренний узел - узел как минимум с одним дочерним элементом.
Edge - соединение между одним узлом и другим.
Глубина - расстояние между узлом и корнем.
Уровень - количество ребер между узлом и корнем + 1
Высота - количество ребер на самом длинном пути между узлом и дочерним листом.
Ширина - количество листьев.
Поддерево - дерево T - это дерево, состоящее из узла в T и всех его потомков в T .
Двоичное дерево - представляет собой древовидную структуру данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левым и правым дочерними элементами.
Дерево двоичного поиска - это особый тип двоичного дерева, обладающий следующими свойствами.
- Левое поддерево узла содержит только узлы с ключами меньше ключа узла.
- Правое поддерево узла содержит только узлы с ключами больше ключа узла.
- Левое и правое поддерево также должны быть двоичным деревом поиска.
Примечание. Для простоты мы будем использовать двоичное дерево в качестве примера для понимания алгоритмов обхода дерева. Но эти алгоритмы можно обобщить и на другие типы деревьев.
2. Обход дерева - Введение
«В информатике обход дерева (также известный как поиск дерева) представляет собой форму обхода графа и относится к процессу посещения (проверки и / или обновления) каждого узла. в древовидной структуре данных ровно один раз. Такие обходы классифицируются по порядку посещения узлов ». - Википедия
Определение Википедии говорит само за себя, чтобы понять, что означает обход дерева. Но я хочу подробнее остановиться на последней строке определения, которая поможет нам понять типы обхода дерева и их различия.
Алгоритмы обхода дерева можно разделить на следующие две категории по порядку посещения узлов:
- Алгоритм поиска в глубину (DFS): он начинается с корневого узла и сначала посещает все узлы одной ветви как можно глубже от выбранного узла, а перед обратным отслеживанием он посещает все другие ветви в аналогичном мода. Под этим есть три подтипа, которые мы рассмотрим в этой статье.
- Алгоритм поиска в ширину (BFS): он также начинается с корневого узла и посещает все узлы текущей глубины перед переходом на следующую глубину в дереве. Мы рассмотрим один алгоритм типа BFS в следующем разделе.
3. Давайте углубимся - Практическое руководство
Пришло время понять концепцию на практике. Я буду использовать язык программирования Java, чтобы объяснить код. Но эти алгоритмы можно закодировать на предпочитаемом вами языке программирования так же, как мы это сделаем на Java.
Ниже приведен план нашего класса Node, который будет действовать как атомарный член древовидной структуры данных. Мы назовем его TreeNode, который содержит данные в виде целого числа, левый и правый дочерние элементы одного типа (TreeNode). Вы можете использовать любую другую структуру данных для хранения в качестве данных в TreeNode.
4. Неупорядоченный обход
Inorder Traversal - один из наиболее часто используемых вариантов DFS (Depth First Search) обхода дерева.
Как предлагает DFS, мы сначала сосредоточимся на глубине выбранного узла, а затем перейдем к глубине на этом уровне. Таким образом, мы начнем с корневого узла дерева и будем все глубже и глубже проникать в левое поддерево рекурсивным образом.
Когда мы дойдем до самого левого узла с помощью вышеуказанных шагов, тогда мы посетим этот текущий узел и перейдем к самому левому узлу его правого поддерева (если существует).
Для завершения обхода по порядку необходимо выполнить те же шаги рекурсивно. Порядок этих шагов будет таким (в рекурсивной функции)…
- Перейти к левому поддереву
- Посетить узел
- Перейти к правому поддереву
Важный факт: Обход двоичного дерева поиска в порядке очередности всегда дает вам отсортированные узлы.
5. Обход предзаказа
Preorder Traversal - еще один вариант DFS. Если атомарные операции в рекурсивной функции такие же, как обход Inorder, но с другим порядком.
Здесь мы сначала посещаем текущий узел, а затем переходим к левому поддереву. Покрыв каждый узел левого поддерева, мы перейдем к правому поддереву и посетим его аналогичным образом.
Порядок шагов будет таким…
- Посетить узел
- Перейти к левому поддереву
- Перейти к правому поддереву
6. Постоперационный обход
То же самое и с Postorder Traversal. Где мы посещаем левое поддерево и правое поддерево перед посещением текущего узла в рекурсии.
Итак, последовательность шагов будет…
- Перейти к левому поддереву
- Перейти к правому поддереву
- Посетить узел
7. Обход порядка уровней
Это обходной путь, отличный от того, что мы рассмотрели выше. Обход порядка уровней следует за BFS (поиск в ширину) для посещения / изменения каждого узла дерева.
Как предлагает BFS, сначала приоритет имеет ширина дерева, а затем его глубина. Проще говоря, мы посетим все узлы, присутствующие на одном уровне, один за другим слева направо, а затем перейдем на следующий уровень, чтобы посетить все узлы этого уровня.
Реализация здесь немного сложнее, чем три вышеупомянутых обхода. Мы будем использовать структуру данных Queue (FIFO) для реализации обхода порядка уровней, где после посещения узла мы просто последовательно помещаем его левый и правый дочерние элементы в очередь.
Здесь важен порядок добавления дочерних элементов в очередь, поскольку мы должны перемещаться слева направо на одном уровне. Ознакомьтесь с приведенной ниже сутью для большего понимания.
8. Заключительные примечания
Алгоритмы обхода дерева можно разделить на две категории:
- Алгоритмы поиска в глубину (DFS)
- Алгоритмы поиска в ширину (BFS)
Есть три варианта алгоритмов поиска в глубину (DFS):
- Preorder Traversal (current-left-right) - Посетите текущий узел перед посещением любых узлов внутри левого или правого поддеревья.
- Inorder Traversal (left-current-right) - Посетите текущий узел после посещения всех узлов внутри левого поддерева, но перед посещением любого узла в правом поддереве.
- Postorder Traversal (left-right-current) - Посетите текущий узел после посещения всех узлов левого и правого поддеревьев.
У алгоритма поиска в ширину (BFS) есть один вариант:
- Обход порядка уровней - Посещайте узлы поэтапно и слева направо на одном уровне.
Ознакомьтесь с моим Репозиторием Github для получения подробного кода.
Важный факт. Существуют и другие алгоритмы обхода дерева, которые не классифицируются ни как поиск в глубину, ни как поиск в ширину. Одним из таких алгоритмов является поиск по дереву Монте-Карло, который концентрируется на анализе наиболее многообещающих ходов, расширяя дерево поиска на основе случайной выборки пространства поиска.
Возможность для вас…
Получите доступ к моей личной Шпаргалке Java Collection в качестве БЕСПЛАТНОГО приветственного подарка после присоединения к моему племени. Получите сейчас!
об авторе
Ананд К. Пармар - инженер-программист, который любит разрабатывать и создавать мобильные приложения. Он писатель, публикующий статьи по информатике, программированию и личным финансам. Свяжитесь с ним в LinkedIn или Twitter. Ознакомьтесь с его последними статьями внизу.
