В предыдущем посте мы использовали метод «содержит» в нашем классе двоичного дерева. Что, если мы хотим знать все узлы, содержащиеся в нашем дереве? Для этого нам нужно создать новый метод. Однако в каком порядке мы хотели бы, чтобы значения были в? У нас есть несколько различных вариантов обхода, которые повлияют на порядок возвращаемых узлов.
В ширину
Глядя на дерево выше, мы собираемся выполнить поиск в ширину. Это означает, что на каждом уровне мы собираемся посетить все узлы слева направо, прежде чем двигаться вниз по уровню. При поиске в ширину мы ожидаем, что наши узлы будут возвращены в следующем порядке: 44, 32, 68, 9, 40, 56, 99, 3, 41. Как мы собираемся это сделать? Раньше мне было трудно обдумать это, пока я не познакомился с очередями.
Решение состоит в том, чтобы использовать очередь (FIFO) для отслеживания значений, которые нам нужно посетить в следующий раз. Вот как это работает.
- Вставьте 44 в нашу очередь
- Если его левый указатель имеет значение, поместите его в очередь. Сделайте то же самое для правой.
- Извлеките первое значение из очереди и поместите его в массив, в котором хранятся наши значения.
- Перейдите на следующий слой. На данный момент у нас все еще есть узлы 32 и 68 в нашей очереди.
- Выполните те же проверки, что и шаг № 2, на узлах 32 и 68.
- Теперь мы можем поместить в очередь 9 и 40. Затем извлеките 32 из очереди/вставьте в массив хранения.
- Повторите шаг 6 на узле 68.
Это повторяется до тех пор, пока очередь не станет пустой, сигнализируя, что мы прошли все дерево.
