Алгоритмы обхода дерева в Python, которые должен знать каждый разработчик

Алгоритмы являются важной частью карьеры разработчика программного обеспечения, как на собеседованиях, так и на работе. Многие стартапы и компании FAANG, такие как Facebook и Google, в основном сосредотачиваются на алгоритмах и структурах данных во время собеседований, поэтому понимание этих концепций может иметь важное значение для продвижения по карьерной лестнице.

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

Сегодня мы обсудим алгоритмы обхода дерева в Python, о которых часто спрашивают на собеседованиях по разработке программного обеспечения.

Мы уделим особое внимание Python по сравнению с другими языками программирования из-за его растущей популярности среди компаний и простого в использовании синтаксиса.

Содержание

Что такое деревья (trees)?
Номенклатура деревьев
Как обойти деревья
Поиск в глубину
Обход по порядку
Обход предварительного заказа
Обход после заказа
Применение алгоритмов обхода дерева в глубину
Алгоритмы поиска в ширину
Заключение

Что такое деревья (trees)?

В терминологии информатики деревья представляют собой нелинейные иерархические структуры данных.

Дерево содержит набор узлов (также называемых вершинами), где пара узлов соединена друг с другом ребром. В отличие от графа дерево не имеет циклов (поэтому оно называется ациклическим). Мы можем увидеть дерево в действии, используя иерархическую структуру компании ниже:

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

Изображение древовидной структуры данных

Номенклатура деревьев

Узел: Узел или вершина — это структура, которая может содержать данные и соединения с другими узлами (известными как ее дочерние узлы). Связь между двумя узлами называется ребром. Ребро может быть исходящим или входящим к узлу. Например, на рисунке выше узел-2 имеет входящее ребро от узла-1 и два исходящих края к узлу-4 и узлу-5.
Листовой узел: узел без исходящих ребер называется листовым узлом. В приведенном выше примере Node-4, Node-8, Node-10 и Node-7 являются конечными узлами.
Корневой узел: Корневой узел не имеет входящих к нему ребер. Обычно он считается самым верхним узлом дерева. В нашем примере Node-1 является корневым узлом. Как правило, дерево должно иметь ровно один корневой узел.
Высота узла: максимальное количество ребер от узла до конечного узла. В приведенном выше примере высоты узлов Node-3 и Node-4 равны 3 и 0 соответственно.
Глубина узла: количество ребер от корня до узлов в дереве. В приведенном выше примере глубина узлов Node-3 и Node-10 равна 1 и 4 соответственно.
Высота дерева: высота корневого узла или глубина самого глубокого узла.
Степень выхода и степень входа узла: степень входа узла относится к количеству входящих ребер, тогда как исходящая степень относится к количеству исходящих ребер. В приведенном выше примере узел-3 имеет входную степень 1, а исходящую степень 2.
Префикс: здесь мы получаем доступ к дереву, начиная с корневого узла, за которым следует левый дочерний элемент, а затем, наконец, правый дочерний узел.
Постфикс: здесь мы получаем доступ к дереву, начиная сначала с левого дочернего элемента, затем правого дочернего элемента и, наконец, корневого узла.
In-fix: здесь мы получаем доступ к дереву, начиная с левого дочернего элемента, корневого узла и, наконец, правого дочернего элемента.

Как обойти деревья

Обход дерева — это процесс, в котором мы посещаем каждый узел дерева, при необходимости распечатывая данные из этих узлов. Мы всегда начинаем поиск с корневого узла, потому что оттуда доступны все узлы.

Есть два способа обойти дерево. Один использует подход в глубину, а второй использует метод в ширину.

Поиск в глубину

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

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

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

Рисунок, изображающий обход дерева

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

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

Давайте посмотрим на обход по порядку в действии. В приведенном ниже примере Python мы делаем следующее:

Строка 5-9: Создайте класс Node. В классе три участника
- Левый дочерний элемент: содержит левого дочернего элемента узла.
- Правый дочерний элемент: содержит правый дочерний элемент узла.
- Данные: значение узла
Строка 12-29: Функция для вставки данных в дерево
Строки 31-43: Функция для печати дерева
Строка 46-54: Реализация алгоритма обхода по порядку
Строка 56-65: Вставить несколько узлов в дерево и вывести результат обхода по порядку.

from queue import Queue

queue = Queue()

class Node:

def __init__(self, val):

self.leftChild = None

self.rightChild = None

self.data = val

# Insert Node

def insert(self, data):

if data is None:

return

if self.leftChild is None:

self.leftChild = Node(data)

#print(self.data, ‘— Left —>’, data)

data = None

elif self.rightChild is None:

self.rightChild = Node(data)

#print(self.data, ‘— Right —>’, data)

data = None

else:

queue.put(self.leftChild)

queue.put(self.rightChild)

while queue.empty() is False:

queue.get().insert(data)

# Print tree

def printTree(self):

ret = []

ret.append(self.data)

if self.leftChild is not None:

queue.put(self.leftChild)

if self.rightChild is not None:

queue.put(self.rightChild)

#print (len(stack))

while queue.empty() is False:

ret = ret + queue.get().printTree()

return ret

# Inorder traversal

# leftChild -> parent -> rightChild

def inorderTraversal(self, root):

ret = []

if root:

ret = self.inorderTraversal(root.leftChild)

ret.append(root.data)

ret = ret + self.inorderTraversal(root.rightChild)

return ret

root = Node(27)

root.insert(14)

root.insert(5)

root.insert(10)

root.insert(6)

root.insert(31)

root.insert(9)

print(«\n\nData is tree is = «, root.printTree())

print(«\n\nresult of inorder traversal is = «, root.inorderTraversal(root))

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

При работе с предварительным обходом мы сначала посещаем корневой узел, затем левое поддерево и, наконец, правое поддерево.

В нашем примере ниже мы предпримем следующие шаги:

Строка 4-9: Создайте класс Node. В классе три участника
- Левый дочерний элемент: содержит левого дочернего элемента узла.
- Правый дочерний элемент: содержит правый дочерний элемент узла.
- Данные: значение узла
Строка 13-29: Функция для вставки данных в дерево
Строка 32-43: Функция для печати дерева
Строка 48-54: Реализация алгоритма обхода предварительного заказа
Строка 56-65: Вставить несколько узлов в дерево и вывести результат обхода предварительного порядка.

from queue import Queue

queue = Queue()

class Node:

def __init__(self, val):

self.leftChild = None

self.rightChild = None

self.data = val

# Insert Node

def insert(self, data):

if data is None:

return

if self.leftChild is None:

self.leftChild = Node(data)

#print(self.data, ‘— Left —>’, data)

data = None

elif self.rightChild is None:

self.rightChild = Node(data)

#print(self.data, ‘— Right —>’, data)

data = None

else:

queue.put(self.leftChild)

queue.put(self.rightChild)

while queue.empty() is False:

queue.get().insert(data)

# Print tree

def printTree(self):

ret = []

ret.append(self.data)

if self.leftChild is not None:

queue.put(self.leftChild)

if self.rightChild is not None:

queue.put(self.rightChild)

#print (len(stack))

while queue.empty() is False:

ret = ret + queue.get().printTree()

return ret

# preorder traversal

# parent -> leftChild -> rightChild

def preorderTraversal(self, root):

ret = []

if root:

ret.append(root.data)

ret = ret + self.preorderTraversal(root.leftChild)

ret = ret + self.preorderTraversal(root.rightChild)

return ret

root = Node(27)

root.insert(14)

root.insert(5)

root.insert(10)

root.insert(6)

root.insert(31)

root.insert(9)

print(«\n\nData is tree is = «, root.printTree())

print(«\n\nresult of preorder traversal is = «, root.preorderTraversal(root))

Обход после заказа

Как следует из названия, при обходе дерева после заказа мы в последнюю очередь посещаем корневой узел. В этом методе обхода мы сначала обходим левое поддерево, затем правое поддерево и, наконец, корень.

Давайте учиться на примере. В приведенной ниже программе Python мы делаем следующее:

Строка 4-9: Создайте класс Node. В классе три участника
- Левый дочерний элемент: содержит левого дочернего элемента узла.
- Правый дочерний элемент: содержит правый дочерний элемент узла.
- Данные: значение узла
Строка 13-29: Функция для вставки данных в дерево
Строки 31-43: Функция для печати дерева
Строка 48-54: Реализация алгоритма обхода после заказа.
Строка 56-65: Вставьте несколько узлов в дерево и распечатайте результат обхода в обратном порядке.

from queue import Queue

queue = Queue()

class Node:

def __init__(self, val):

self.leftChild = None

self.rightChild = None

self.data = val

# Insert Node

def insert(self, data):

if data is None:

return

if self.leftChild is None:

self.leftChild = Node(data)

#print(self.data, ‘— Left —>’, data)

data = None

elif self.rightChild is None:

self.rightChild = Node(data)

#print(self.data, ‘— Right —>’, data)

data = None

else:

queue.put(self.leftChild)

queue.put(self.rightChild)

while queue.empty() is False:

queue.get().insert(data)

# Print tree

def printTree(self):

ret = []

ret.append(self.data)

if self.leftChild is not None:

queue.put(self.leftChild)

if self.rightChild is not None:

queue.put(self.rightChild)

#print (len(stack))

while queue.empty() is False:

ret = ret + queue.get().printTree()

return ret

# postorder traversal

# leftChild -> rightChild -> parent

def postorderTraversal(self, root):

ret = []

if root:

ret = ret + self.postorderTraversal(root.leftChild)

ret = ret + self.postorderTraversal(root.rightChild)

ret.append(root.data)

return ret

root = Node(27)

root.insert(14)

root.insert(5)

root.insert(10)

root.insert(6)

root.insert(31)

root.insert(9)

print(«\n\nData is tree is = «, root.printTree())

print(«\n\nresult of postorder traversal is = «, root.postorderTraversal(root))

Применение алгоритмов обхода дерева в глубину

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

Алгоритмы поиска в ширину

Алгоритмы поиска в ширину обычно используются как на деревьях, так и на графах. Они реализованы с использованием рекурсии через структуры данных, такие как списки и словари.

Алгоритмы поиска в ширину (BFS) следующие:

Выберите любой узел в дереве или графе. Поставьте в очередь все соседние узлы. Удалите вершину из очереди и пометьте ее как visited. Поставьте все соседние узлы в другую очередь.
Повторяйте шаг 1, пока все узлы не будут посещены или пока вы не придете к своему решению.
Обязательно отметьте все узлы, через которые вы проходите, как visitedперед переходом к следующим, чтобы не застрять в бесконечном цикле.

В нашем интерактивном редакторе кода выше в кодах обхода в глубину наша функция printTreeпечатает treeс использованием BFS. Мы призываем вас внимательно наблюдать за нашей реализацией printTreeи экспериментировать с ней.

Заключение

Поздравляем с завершением знакомства с алгоритмами обхода дерева Python! Но мы только что коснулись поверхности того, что вы можете делать с алгоритмами обхода дерева, что также включает в себя подготовку к интервью.

Несколько алгоритмических вопросов на собеседовании потребуют от вас решения задач с использованием древовидной структуры данных. Некоторые распространенные вопросы на собеседовании: