Алгоритм обхода дерева python

Поиск в ширину на 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. Стратегия

Вот как мы будем обходить узлы:

1. Найдем высоту дерева от корня до самого дальнего листа.
2. В цикле переберем все уровни (заканчивая верхушкой).
3. Обойдем каждый уровень, выводя все узлы.

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 . Мы успешно обошли дерево!

Источник

Обход двоичного дерева на Python

Да, двоичные деревья — не самая любимая тема программистов. Это одна из тех старых концепций, о целесообразности изучения которых постоянно ведутся споры. В работе вам довольно редко придется реализовывать двоичные деревья и обходить их, так зачем же уделять им так много внимания на технических собеседованиях?

Сегодня мы не будем переворачивать двоичное дерево (ффухх!), но рассмотрим пару методов его обхода. К концу статьи вы поймете, что двоичные деревья не так страшны, как кажется.

Что такое двоичное дерево?

Недавно мы разбирали реализацию связных списков на Python. Каждый такой список состоит из некоторого количества узлов, указывающих на другие узлы. А если бы узел мог указывать не на один другой узел, а на большее их число? Вот это и есть деревья. В них каждый родительский узел может иметь несколько узлов-потомков. Если у каждого узла максимум два узла-потомка (левый и правый), такое дерево называется двоичным (бинарным).

В приведенном выше примере «корень» дерева, т. е. самый верхний узел, имеет значение 1. Его потомки — 2 и 3. Узлы 3, 4 и 5 называют «листьями»: у них нет узлов-потомков.

Строим двоичное дерево на Python

Как построить дерево на Python? Реализация будет похожей на наш класс Node в реализации связного списка. В этом случае мы назовем класс TreeNode .

Определим метод __init__() . Как всегда, он принимает self . Также мы передаем в него значение, которое будет храниться в узле.

class TreeNode: def __init__(self, value):

Установим значение узла, а затем определим левый и правый указатель (для начала поставим им значение None ).

class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None

И… все! Что, думали, что деревья куда сложнее? Если речь идет о двоичном дереве, единственное, что его отличает от связного списка, это то, что вместо next у нас тут есть left и right .

Давайте построим дерево, которое изображено на схеме в начале статьи. Верхний узел имеет значение 1. Далее мы устанавливаем левые и правые узлы, пока не получим желаемое дерево.

tree = TreeNode(1) tree.left = TreeNode(2) tree.right = TreeNode(3) tree.left.left = TreeNode(4) tree.left.right = TreeNode(5)

Обход двоичного дерева

Итак, вы построили дерево и теперь вам, вероятно, любопытно, как же его увидеть. Нет никакой команды, которая позволила бы вывести на экран дерево целиком, тем не менее мы можем обойти его, посетив каждый узел. Но в каком порядке выводить узлы?

Самые простые в реализации обходы дерева — прямой (Pre-Order), обратный (Post-Order) и центрированный (In-Order). Вы также можете услышать такие термины, как поиск в ширину и поиск в глубину, но их реализация сложнее, ее мы рассмотрим как-нибудь потом.

Итак, что из себя представляют три варианта обхода, указанные выше? Давайте еще раз посмотрим на наше дерево.

При прямом обходе мы посещаем родительские узлы до посещения узлов-потомков. В случае с нашим деревом мы будем обходить узлы в таком порядке: 1, 2, 4, 5, 3.

Обратный обход двоичного дерева — это когда вы сначала посещаете узлы-потомки, а затем — их родительские узлы. В нашем случае порядок посещения узлов при обратном обходе будет таким: 4, 5, 2, 3, 1.

При центрированном обходе мы посещаем все узлы слева направо. Центрированный обход нашего дерева — это посещение узлов 4, 2, 5, 1, 3.

Давайте напишем методы обхода для нашего двоичного дерева.

Pre-Order

Начнем с определения метода pre_order() . Наш метод принимает один аргумент — корневой узел (расположенный выше всех).

Дальше нам нужно проверить, существует ли этот узел. Вы можете возразить, что лучше бы проверить существование потомков этого узла перед их посещением. Но для этого нам пришлось бы написать два if-предложения, а так мы обойдемся одним.

def pre_order(node): if node: pass

Написать обход просто. Прямой обход — это посещение родительского узла, а затем каждого из его потомков. Мы «посетим» родительский узел, выведя его на экран, а затем «обойдем» детей, вызывая этот метод рекурсивно для каждого узла-потомка.

# Выводит родителя до всех его потомков def pre_order(node): if node: print(node.value) pre_order(node.left) pre_order(node.right)

Просто, правда? Можем протестировать этот код, совершив обход построенного ранее дерева.

Post-Order

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

Вместо «посещения» родительского узла и последующего «обхода» детей, мы сначала «обойдем» детей, а затем «посетим» родительский узел. То есть, мы просто передвинем print на последнюю строку! Не забудьте поменять имя метода на post_order() во всех вызовах.

# Выводит потомков, а затем родителя def post_order(node): if node: post_order(node.left) post_order(node.right) print(node.value)

Каждый узел-потомок посещен до посещения его родителя.

In-Order

Наконец, напишем метод центрированного обхода. Как нам обойти левый узел, затем родительский, а затем правый? Опять же, нужно переместить предложение print!

# выводит левого потомка, затем родителя, затем правого потомка def in_order(node): if node: in_order(node.left) print(node.value) in_order(node.right)

Вот и все, мы рассмотрели три простейших способа совершить обход двоичного дерева.

Источник