Поиск в ширину на Python
Двоичные деревья вечны. По крайней мере, так думают технические менеджеры, занимающиеся наймом разработчиков. И когда на техническом собеседовании вас просят решить задачу, касающуюся двоичных деревьев, первое, что интервьюер захочет знать, — в ширину или в глубину?
В чем разница?
Когда говорят о поиске в ширину (Breadth First Search, BFS) и глубину (Depth First Search, DFS), имеется в виду порядок обхода узлов двоичного дерева. При обходе в глубину вы сначала опускаетесь к низу дерева, а потом идете в сторону, а при обходе в ширину — наоборот, начинаете с корня и спускаетесь сначала к его узлам-потомкам, обходите их, потом спускаетесь к потомкам потомков, обходите их, и так далее.
Если взять в качестве примера двоичное дерево на этом рисунке, при BFS-подходе порядок обхода узлов будет следующим: 1, 2, 3, 4, 5.
В случае с DFS возможны разные варианты последовательности посещения узлов. Все зависит от того, будет это прямой, обратный или центрированный обход. Например, прямой обход выдаст 1, 2, 4, 5, 3. Мы разбирали эти три типа обхода в статье «Обход двоичного дерева на Python».
Реализация поиска в ширину на Python
Давайте посмотрим, как сделать BFS на Python. Начнем с определения нашего класса TreeNode. В нем должны быть только значение и левый и правый указатели.
class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None
1. Стратегия
Вот как мы будем обходить узлы:
- Найдем высоту дерева от корня до самого дальнего листа.
- В цикле переберем все уровни (заканчивая верхушкой).
- Обойдем каждый уровень, выводя все узлы.
2. Поиск высоты дерева
Чтобы обойти каждый уровень, нам нужно сначала узнать, сколько всего уровней в дереве. Для этого мы напишем специальный метод.
Да, вы угадали: метод будет рекурсивным, как и большинство методов для обхода двоичных деревьев. Давайте подумаем, каким будет базовый случай. Самый простой вариант — когда у нас нулевой корень. В этом случае высота — 0. Вам может показаться, что простейший случай — узел без потомков, но тогда нам придется проверять, есть ли потомки, а это уже увеличивает сложность.
def height(node): if not node: return 0
Что дальше? Нам нужно обойти левую и правую половину дерева. Мы будем вызывать метод height() для этих половин и сохранять в две переменные: l_height и r_height .
def height(node): if not node: return 0 l_height = height(node.left) r_height = height(node.right)
Какую высоту мы вернем: левую или правую? Конечно, большую! Поэтому мы берем max() обоих значений и возвращаем его. Не забудьте добавить 1 для текущего узла.
def height(node): if not node: return 0 l_height = height(node.left) r_height = height(node.right) return max(l_height, r_height) + 1
3. Перебор уровней в цикле
Теперь, когда у нас есть высота, мы можем приступить к написанию метода для обхода дерева в ширину. Единственный аргумент, который этот метод будет принимать, — корневой узел.
Затем нам нужно получить нашу высоту.
def breadth_first(root): h = height(root)
Наконец, мы перебираем в цикле высоту дерева. На каждой итерации мы будем вызывать вспомогательную функцию — print_level() , которая принимает узел root и уровень.
def breadth_first(root): h = height(root) for i in range(h): print_level(root, i)
4. Обход дерева
Мы будем обходить каждый уровень отдельно, выводя все узлы на нем. Тут нам пригодится наша вспомогательная функция. Она принимает два аргумента: корень и текущий уровень.
def print_level(root, level):
В этом методе номер уровня определяется индексом i цикла for . Чтобы обойти все дерево, мы будем рекурсивно двигаться по уровням, уменьшая i , пока не достигнем уровня 0. Когда достигнем, это будет означать, что теперь можно выводить узлы на экран.
Наш базовый случай — когда корень — null . Этот метод только выводит дерево на экран и ничего не возвращает, поэтому в базовом случае будет просто return .
def print_level(root, level): if not root: return
Далее, если наш уровень — 0 (то есть интересующий нас уровень), нам нужно вывести значение этого узла.
def print_level(root, level): if not root: return if level == 0: print(root.value)
Наконец, если номер уровня больше нуля, это означает, что нам нужно продолжить обход дерева. Мы вызываем наш рекурсивный метод для левой и правой половин дерева. Не забудьте отнять единицу от level в обоих вызовах функции.
def print_level(root, level): if not root: return if level == 0: print(root.value) elif level > 0: print_level(root.left, level - 1) print_level(root.right, level - 1)
Вот и все! Нам пришлось создать три разных метода, но в конечном итоге мы можем обойти дерево в ширину.
5. Тестирование
Для начала давайте создадим дерево, используя наш класс TreeNode .
Теперь нужно заполнить оставшуюся часть дерева. При помощи следующих строк кода мы приведем дерево к тому виду, что изображен на схеме.
tree.left = TreeNode(2) tree.right = TreeNode(3) tree.left.left = TreeNode(4) tree.left.right = TreeNode(5)
Наконец, запускаем наш метод.
Ожидаемый результат: 1, 2, 3, 4, 5 . Мы успешно обошли дерево!
Источник
1.2. Обходы деревьев
Обход дерева – это способ методичного исследования его узлов, при котором каждый узел проходится точно один раз. Полное прохождение динамического дерева дает линейную расстановку его узлов.
Возможны два способа прохождения бинарного дерева (если дерево не пусто):
1.2.1. Алгоритмы обхода в глубину
Существует несколько способов обхода в глубину:
пройти в прямом порядке левое поддерево;
пройти в прямом порядке правое поддерево.
пройти в обратном порядке левое поддерево;
пройти в обратном порядке правое поддерево;
Симметричный порядок(см. рис.4.в):
пройти в симметричном порядке левое поддерево;
пройти в симметричном порядке правое поддерево.
Рис.4. Способы обхода дерева в глубину
if ( d->left != NULL && d->right != NULL)
if ( d->left = = NULL && d->right = =NULL)
if ( S!= NULL) из стека (S, d); else d = NULL;
else if (d->left != NULL) d = d->left;
Рекурсивное описание алгоритма прямого обхода:
Алгоритм обратного обхода:
Рекурсивное описание алгоритма обратного обхода:
Алгоритм симметричного обхода можно получить преобразив и соединив оба предыдущих алгоритма
1.2.2. Алгоритмы обхода в ширину
Узлы дерева посещаются слева направо, уровень за уровнем вниз от корня (линейная расстановка узлов дерева, представленна на рис.5).
из_очереди ( Q, d ); обработка ( d );
if ( d->left != NULL ) в_очередь ( Q, d->left );
if ( d->right != NULL ) в_очередь ( Q, d->right );
Рис.5. Порядок обхода дерева в ширину
1.3. Ввод дерева
Чтобы ввести дерево надо выбрать какой-то способ перечисления его узлов. Одним из возможных способов является так называемая списочная запись (представление). Список – это конечная последовательность атомов либо списков, число которых, может быть и равно нулю (атом – это понятие, определяющее элемент из любого множества предметов). Используя скобки, список можно задать перечислением через запятую его атомов (порядок перечисления атомов определяет их упорядочение). Таким образом, дерево, представленное на рис.4.1.б можно записать в виде следующего списка:
( A, ( B, ( С, 0, 0 ), (D, 0, 0) ), ( E, ( F, 0, 0 ) , ( G, ( H, 0, 0 ), ( I, 0, 0 ) )))
Ввод дерева, представленного таким списком, можно описать рекурсивной функцией (тип дерева btree описан выше, здесь type – тип информационного поля элемента – сhar):
d->right = build_tree ( ); scanf( “%c”, &sym );
case ‘,’ : d = build_tree ( ); break ;
Источник