Поиск в ширину на 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 . Мы успешно обошли дерево!
Источник
Обход бинарных деревьев: рекурсия, итерации и указатель на родителя
Основы о бинарных деревьях представлены, в том числе, здесь . Добавлю свои «5 копеек» и данным постом систематизирую материалы, связанные с обходом бинарных деревьев, а именно сравнений возможностей рекурсии и итераций, а также обсуждение возможностей использования указателя на родительский узел.
Итак… язык Java, класс узла имеет следующий вид:
Примечание: Указатель на родителя parent – как правило не имеет большого смысла, однако, как следует из заголовка и будет показано, может быть полезен в ряде случаев.
Обход деревьев – последовательная обработка (просмотр, изменение и т.п.) всех узлов дерева, при котором каждый узел обрабатывается строго один раз. При этом получается линейная расстановка узлов дерева.
В зависимости от траекторий выделяют два типа обхода:
— горизонтальный (в ширину); и
— вертикальный (в глубину).
Горизонтальный обход подразумевает обход дерева по уровням (level-ordered) – вначале обрабатываются все узлы текущего уровня, после чего осуществляется переход на нижний уровень.
При вертикальном обходе порядок обработки текущего узла и узлов его правого и левого поддеревьев варьирует и по этому признаку выделяют три варианта вертикального обхода:
— прямой (префиксный, pre-ordered): вершина – левое поддерево – правое поддерево;
— обратный (инфиксный, in-ordered): левое поддерево – вершина – правое поддерево; и
— концевой (постфиксный, post-ordered): левое поддерево – правое поддерево – вершина.
Сам обход во всех случаях в принципе один и тот же, различается порядок обработки. Для представления в каком порядке будет проходить обработка узлов дерева удобно следовать по «контуру обхода». При прямом обходе узел будет обработан в точке слева от узла, при обратном снизу от узла и при концевом, соответственно, справа от узла.
Другими словами «находясь» в некотором узле, нам нужно знать, нужно ли его обрабатывать и куда двигаться дальше.
Рекурсия
Все три варианта вертикального обхода элементарно реализуются рекурсивными функциями.
void recPreOrder() < treatment(); if (left!=null) left.recPreOrder(); if (right!=null) right.recPreOrder(); >void recInOrder() < if (left!=null) left.recInOrder(); treatment(); if (right!=null) right.recInOrder(); >void recPostOrder()
Рекурсия крайне удобна не только при обходе, но также при построении дерева, поиска в дереве, а также балансировки. Однако рекурсией нельзя осуществить горизонтальный обход дерева. В этом случае, а так же при обеспокоенности перегрузкой программного стека, следует применять итерационный подход.
Контейнеры
В случае использования итераций необходимо хранить сведенья о посещенных, но не обработанных узлах. Используются контейнеры типа стек (для вертикального обхода) и очередь (для горизонтального обхода).
Горизонтальный обход:
обрабатываем первый в очереди узел, при наличии дочерних узлов заносим их в конец очереди. Переходим к следующей итерации.
static void contLevelOrder(Node top) < Queuequeue=new LinkedList<> (); do< top.treatment(); if (top.left!=null) queue.add(top.left); if (top.right!=null) queue.add(top.right); if (!queue.isEmpty()) top=queue.poll(); >while (!queue.isEmpty()); > Вертикальный прямой обход:
обрабатываем текущий узел, при наличии правого поддерева добавляем его в стек для последующей обработки. Переходим к узлу левого поддерева. Если левого узла нет, переходим к верхнему узлу из стека.
static void contPreOrder(Node top) < Stackstack = new Stack<> (); while (top!=null || !stack.empty()) < if (!stack.empty())< top=stack.pop(); >while (top!=null) < top.treatment(); if (top.right!=null) stack.push(top.right); top=top.left; >> > Вертикальный обратный обход:
из текущего узла «спускаемся» до самого нижнего левого узла, добавляя в стек все посещенные узлы. Обрабатываем верхний узел из стека. Если в текущем узле имеется правое поддерево, начинаем следующую итерацию с правого узла. Если правого узла нет, пропускаем шаг со спуском и переходим к обработке следующего узла из стека.
static void contInOrder(Node top) < Stackstack = new Stack<> (); while (top!=null || !stack.empty()) < if (!stack.empty())< top=stack.pop(); top.treatment(); if (top.right!=null) top=top.right; else top=null; >while (top!=null) < stack.push(top); top=top.left; >> > Вертикальный концевой обход:
Здесь ситуация усложняется – в отличие от обратного обхода, помимо порядка спуска нужно знать обработано ли уже правое поддерево. Одним из вариантов решения является внесение в каждый экземпляр узла флага, который бы хранил соответствующую информацию (не рассматривается). Другим подходом является «кодирование» непосредственно в очередности стека — при спуске, если у очередного узла позже нужно будет обработать еще правое поддерево, в стек вносится последовательность «родитель, правый узел, родитель». Таким образом, при обработке узлов из стека мы сможем определить, нужно ли нам обрабатывать правое поддерево.
static void contPostOrder(Node top) < Stackstack = new Stack<> (); while (top!=null || !stack.empty())< if (!stack.empty())< top=stack.pop(); if (!stack.empty() && top.right==stack.lastElement())< top=stack.pop(); >else < top.treatment(); top=null; >> while (top!=null) < stack.push(top); if (top.right!=null)< stack.push(top.right); stack.push(top); >top=top.left; > > > Об указателе на родителя
Наличие в экземпляре класса указателя на родителя приносит определенные хлопоты при построении и балансировки деревьев. Однако, возможность из произвольного узла дерева «дойти» до любого из его узлов может придтись весьма кстати. Все, за чем нужно следить при «подъеме» на верхний уровень – пришли ли от правого потомка или от левого.
Так, с использованием родительских указателей будет выглядеть код вертикального концевого обхода.
static void parentPostOrder(Node top) < boolean fromright=false; Node shuttle=top, holder; while(true)< while (fromright)< shuttle.treatment(); if (shuttle==top) return; holder=shuttle; shuttle=shuttle.parent; fromright=shuttle.right==holder; if (!fromright && shuttle.right!=null) shuttle=shuttle.right; else fromright=true; >while (shuttle.left!=null) shuttle=shuttle.left; if (shuttle.right!=null) shuttle=shuttle.right; else fromright=true; > > Другой класс задач, которые позволяет решить родительский указатель, как уже было упомянуто — перемещение внутри дерева.
Так, что бы перейти на n-ый по счету узел от текущего узла, без «ориентации в дереве» пришлось бы обходить дерево с самого начала, до известного узла, а потом еще n-узлов. С использованием же родительского указателя при обратном обходе дерева перемещение на steps узлов от текущего узла (start) будет иметь следующий вид.
public static Node walkTheTree(Node start, int steps) < boolean fromright=true; Node shuttle=start, holder; if (shuttle.right!=null)< shuttle=shuttle.right; while (shuttle.left!=null) shuttle=shuttle.left; fromright=false; >int counter=0; do < while (true)< if (!fromright && ++counter==steps) return shuttle; if (!fromright && shuttle.right!=null)< shuttle=shuttle.right; break; >holder=shuttle; shuttle=shuttle.parent; fromright=(holder==shuttle.right); > while (shuttle.left!=null) shuttle=shuttle.left; >while (true); > Примечание: В общем случае также требуется предотвратить возможность попытки выхода за пределы дерева (подняться выше корневого узла).
Источник