Обход дерева python рекурсия

Русские Блоги

Алгоритм (2) — обход бинарного дерева (рекурсивный / итеративный) реализация pyhton

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

Существует две общие стратегии обхода дерева: обход в глубину и обход в ширину.
(само дерево является рекурсивной структурой)

1. DFS сначала в глубину

DFS (поиск в глубину) — это метод обхода двоичных деревьев в глубину. Сначала в глубину начинается с корневого узла и выполняется поиск в глубину до определенного листового узла. В соответствии с относительным порядком обхода левого дочернего, правого дочернего и корневого узла , его можно разделить на обход первого порядка (корень-лево-право), обход средней необходимости (левый-корень-право) и последующий обход (левый-правый-корень).

1.1 Рекурсивное решение DFS

Три последовательности рекурсивного решения с ориентацией в глубину имеют одинаковую структуру. Самый важный момент рекурсии: условие окончания рекурсии, (1) текущий узел пуст или рекурсивная программа завершает выполнение последней строки.

1.1.1 Обход первого порядка

Корневой-левый-правый вывод: [1,2,4,8,9,5,3,6,7]

class Solution(object): def PreOrder_rec(self,root): res=[] def DFS_pre(node,res): if node==None: return res.append(node.val) # Первый в DFS_pre(node.left,res) # Рекурсивное левое поддерево DFS_pre(node.right,res) # Рекурсивное правое поддерево DFS_pre(root,res) return res 

1.1.2 Обход по порядку

Левый корень-правый вывод: [8,4,9,2,5,1,6,3,7]

class Solution(object): def InOrder_rec(self, root): res=[] def DFS_In(node,res): if node==None: return DFS_In(node.left,res) res.append(node.val) DFS_In(node.right,res) DFS_In(root,res) return res 

1.1.3 Пост-заказ обхода

Лево-правый корневой вывод [8,9,4,5,2,6,7,3,1]

class Solution(object): def BackOrder_rec(self, root): res=[] def DFS_Back(node,res): if node==None: return DFS_Back(node.left,res) DFS_Back(node.right,res) res.append(node.val) DFS_Back(root,res) return res 

1.2 Итеративное решение DFS

Итерация двоичного дерева в глубину должна использоватьКуча(Первый пришел, последний ушел). Вставляйте разные узлы в стек в трех разных последовательностях.

1.2.1 Обход предварительного заказа

Корневой-левый-правый вывод: [1,2,4,8,9,5,3,6,7]. Поддерживать стек стека (список может быть эффективно реализован на Python)
начать с корневого узла (curr = Root);
Если текущий узел не пуст, получите доступ к значению текущего узла, вставьте правый узел поддерева текущего узла в стек и обновите текущий узел: curr = curr.left .;
Если текущий узел пуст: вытолкнуть последний правый узел поддерева, сохраненный в стеке.

class Solution(object): def PreOrder_iter(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ res=[] stack=[] curr=root while(curr or stack): if curr: res.append(curr.val) stack.append(curr.right) # При рекурсии к конечному узлу стек увеличится на None curr=curr.left # Когда появляется None pop, выполняется еще одна операция res без увеличения else: curr=stack.pop() return res 

1.2.2 Обход по порядку

Левый корень-правый вывод: [8,4,9,2,5,1,6,3,7]
Поддерживать стек стека (список можно эффективно реализовать на Python).
Из корневого узла (curr = Root):
Если текущий узел не пуст: вставьте текущий узел в стек и обновите текущий узел: curr = curr.left;
Если текущий узел пуст: извлечь последний узел, сохраненный в стеке, получить доступ к значению этого узла и обновить текущий узел: curr = curr.right.

class Solution(object): def InOrer_iter(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ res=[] stack=[] curr=root while(curr or stack): if curr: stack.append(curr) curr=curr.left # Всегда ищите левое поддерево до листового узла и вставляйте узлы на пути в стек else: curr=stack.pop() res.append(curr.val) curr=curr.right # Посетить правый узел поддерева return res 

1.2.3 Пост-заказ обхода

Лево-правый корневой вывод [8,9,4,5,2,6,7,3,1]
Поддерживать стек стека (список можно эффективно реализовать на Python).
Из корневого узла (curr = Root):
Если текущий узел не пуст: вставьте текущий узел в стек и обновите текущий узел: curr = curr.left;
Если текущий узел пуст: извлечь последний узел, сохраненный в стеке, получить доступ к значению этого узла и обновить текущий узел: curr = curr.right.

class Solution(object): def BackOrder_iter(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ res=[] stack=[] curr=root while(curr or stack): # Левый и правый корни разбиваются на: корень правый левый + обратный порядок (корень правый левый и корень левый и правый - это одна и та же структура реализации) if curr: res.append(curr.val) stack.append(curr.left) curr=curr.right else: curr=stack.pop() return res[::-1] 

2. Первый BFS в ширину

BFS (поиск в ширину) — это метод обхода двоичных деревьев в ширину, также называемыйОбход уровнейОт корневого узла бинарное дерево просматривается слой за слоем. 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9

С помощью очередиПервым пришел последний Характеристики узла будут продолжать помещаться в очередь. Используйте список в Python, чтобы быстро реализовать очереди.
Итерационное решение Выход [1,2,3,4,5,6,7,8,9]

class Solution(object): def BFS_iter1(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ levels=[] queue=[root] if not root: return levels while(queue): # node=queue.pop(0) levels.append(node.val) if node.left: # Все элементы, загруженные в очередь, непустые. queue.append(node.left) if node.right: queue.append(node.right) return levels 

leetcode 102 Чтобы объединить элементы каждого слоя выходного результата, вам необходимо вести список для размещения элементов каждого слоя, levels = [[1], [2,3], [4,5,6,7], [8,9]], а переменная уровня используется для указания уровня текущего узла.

Итерационное решение : Выход [[1], [2,3], [4,5,6,7], [8,9]]

class Solution(object): def levelOrder_iter2(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ levels=[] queue=[root] if not root: return levels while(queue): # Перед обработкой каждого слоя добавьте уровни один раз и установите значение узла этого слоя levels.append([]) n_q=len(queue) # Количество узлов в этом слое for i in range(n_q): # i: [0, n_q-1] # Обрабатываем узлы этого слоя один за другим: сначала вытаскиваем верх очереди, записываем значение и помещаем потомков в очередь, если есть левый и правый потомки node=queue.pop(0) levels[-1].append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return levels 

Рекурсивное решение Выход [[1], [2,3], [4,5,6,7], [8,9]]
— это фактически BFS, реализованная DFS. Каждый раз, когда DFS пересекает новый узел, он добавляется в список уровня, на котором он расположен.

class Solution(object): def levelOrder_rec(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ levels=[] if not root: return levels def BFS_rec(node,level): if len(levels)==level: # level, как индекс уровней, должен быть levels.append([]) levels[level].append(node.val) # Поместите текущий узел в указанный слой if node.left: # Если есть левый и правый потомки, рекурсивно вызвать BFS_rec BFS_rec(node.left,level+1) if node.right: BFS_rec(node.right,level+1) BFS_rec(root,0) return levels 

Источник

Обход двоичного дерева на 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)

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

Источник