Обход бинарного дерева относится к началу с корневого узла и посещению всех узлов бинарного дерева в определенном порядке, так что каждый узел посещается один и только один раз.
В обходе бинарного дерева есть три распространенных метода обхода: обход в прямом порядке, обход в порядке и обход в обратном порядке. Далее я попытаюсь использовать три набора анимаций, чтобы подробно представить читателям логические идеи этих трех методов обхода, надеясь, что читатели смогут быстро обрисовать анимацию в уме, когда увидят любое бинарное дерево.
помещение
Прежде чем представить эти три набора анимаций, давайте воспользуемся диаграммой, чтобы представить создание бинарных деревьев и некоторые соглашения в анимации.
Как показано на рисунке, это узел в двоичном дереве. Этот узел имеет левое поддерево и правое поддерево. Двумя зелеными соединительными линиями этот узел разделен на три области. Мы используем переднюю, среднюю и заднюю три области соответственно. , вспомогательная точка.
Эти три точки указывают, когда нужно получить значение этого узла при обходе бинарного дерева.
Любой узел, который нужно пройти, проходится в следующем порядке: передняя левая зеленая линия-средняя-правая зеленая линия-задняя.
обход предварительного заказа
Конкретный процесс реализации обхода предварительного порядка с использованием рекурсии выглядит следующим образом:
- Сначала посетите корневой узел
- Переупорядочить обход левого поддерева
- Обход правого поддерева в последнем порядке
Давайте дадим полное объяснение анимации выше, чтобы понять рекурсивную реализацию обхода предварительного порядка.
- посетил первый
28В этом узле мы видим前辅助点, так как это предварительный обход, то мы вынимаем значение узла в этот момент28 - Затем доступ через левую зеленую линию
28левое поддерево - существует
16В этом узле мы видим前辅助点, так как это предварительный обход, выньте значение узла16 - Доступ по левой зеленой линии
16левое поддерево - существует
13В этом узле мы видим前辅助点, так как это предварительный обход, выньте значение узла13 -
13Левое поддерево этого узла пустое, значит у нас нет левой зеленой линии, а дальше видим中辅助点, так как это предварительный обход, он не обрабатывается -
13Правое поддерево этого узла пустое, значит, у нас нет правой зеленой линии, а дальше видим后辅助点, так как это предварительный обход, он не обрабатывается - затем обратно в
16В этом узле см.中辅助点, так как это предварительный обход, он не обрабатывается - тогда см.
16правое поддерево этого узла22этот узел см.前辅助点, так как это предварительный обход, выньте значение узла22 - . . .
Код:
Неупорядоченный обход
Конкретный процесс реализации обхода по порядку с использованием рекурсии выглядит следующим образом:
- Сначала пройти левое поддерево по порядку
- Вернитесь к корневому узлу
- Последний неупорядоченный обход правого поддерева
Давайте дадим полное объяснение анимации выше, чтобы понять рекурсивную реализацию обхода по порядку.
- посетил первый
28В этом узле мы видим前辅助点, так как это обход по порядку, он не обрабатывается - Затем доступ через левую зеленую линию
28левое поддерево - существует
16В этом узле мы видим前辅助点, так как это обход по порядку, он не обрабатывается - Доступ по левой зеленой линии
16левое поддерево - существует
13В этом узле мы видим前辅助点, так как это обход по порядку, он не обрабатывается -
13Левое поддерево этого узла пустое, значит у нас нет левой зеленой линии, а дальше видим中辅助点, так как это обход по порядку, выньте значение узла13 -
13Правое поддерево этого узла пустое, значит, у нас нет правой зеленой линии, а дальше видим后辅助点, так как это обход по порядку, он не обрабатывается - затем обратно в
16В этом узле см.中辅助点, так как это обход по порядку, выньте значение узла16 - тогда см.
16правое поддерево этого узла22этот узел см.前辅助点, так как это обход по порядку, он не обрабатывается - Смотреть
中辅助点, так как это обход по порядку, выньте значение узла22 - . . .
Код:
пост-порядковый обход
Конкретный процесс реализации обратного обхода с использованием рекурсии выглядит следующим образом:
- Обходим левое поддерево по порядку
- Затем пройдите по правому поддереву в обратном порядке.
- Последнее посещение корневого узла
Давайте дадим полное объяснение анимации выше, чтобы понять рекурсивную реализацию обхода по порядку.
- посетил первый
28В этом узле мы видим前辅助点, поскольку это обход в обратном порядке, он не обрабатывается - Затем доступ через левую зеленую линию
28левое поддерево - существует
16В этом узле мы видим前辅助点, поскольку это обход в обратном порядке, он не обрабатывается - Доступ по левой зеленой линии
16левое поддерево - существует
13В этом узле мы видим前辅助点, поскольку это обход в обратном порядке, он не обрабатывается -
13Левое поддерево этого узла пустое, значит у нас нет левой зеленой линии, а дальше видим中辅助点, поскольку это обход в обратном порядке, он не обрабатывается -
13Правое поддерево этого узла пустое, значит, у нас нет правой зеленой линии, а дальше видим后辅助点, так как это обход в обратном порядке, выньте значение узла13 - затем обратно в
16В этом узле см.中辅助点, поскольку это обход в обратном порядке, он не обрабатывается - тогда см.
16правое поддерево этого узла22этот узел см.前辅助点, так как это обход по порядку, он не обрабатывается - Смотреть
中辅助点, поскольку это обход в обратном порядке, он не обрабатывается - Смотреть
后辅助点, так как это обход в обратном порядке, выньте значение узла16 - . . .