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

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

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

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

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

Мы рассмотрим:

• Что такое деревья?
• Номенклатура деревьев
• Как обходить деревья
• Обход по глубине
  • Обход в порядке следования
  • Обход в предварительном порядке
  • Обход в порядке следования
    • Применение алгоритмов обхода деревьев по принципу «глубина-первый
• Обход дерева по глубине
• Освойте алгоритмы обхода деревьев в Python уже сегодня

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

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

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

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

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

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

• Корневой узел: Корневой узел не имеет входящих ребер. Обычно он считается самым верхним узлом дерева. В нашем примере Узел-1 является корневым узлом. Как правило, дерево должно иметь только один корневой узел.

• Высота узла: Максимальное количество ребер от узла до листового узла. В приведенном выше примере высота узла-3 и узла-4 равна 3 и 0, соответственно.

• Глубина узла: Количество ребер от корня до узлов в дереве. В приведенном выше примере глубина узла-3 и узла-10 равна 1 и 4 соответственно.

• Высота дерева: Высота корневого узла или глубина самого глубокого узла.

• Out-degree и in-degree узла: Входящая степень узла означает количество входящих ребер, а исходящая степень — количество исходящих ребер. В приведенном выше примере узел 3 имеет входящую степень 1, но исходящую степень 2.

• Пре-фикс: Это когда мы обращаемся к дереву, начиная сначала с корневого узла, затем к левому дочернему узлу и, наконец, к правому дочернему узлу.

• Пост-фикс: Это когда мы обращаемся к дереву, начиная сначала с левого дочернего узла, затем с правого дочернего узла и, наконец, с корневого узла.

• Ин-фикс: В этом случае мы обращаемся к дереву, начиная с левого дочернего узла, корневого узла и, наконец, правого дочернего узла.

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

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

Существует два способа обхода дерева. Один из них — поиск в глубину, а второй — поиск в ширину.

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

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

• Обход в порядке следования
• обход в предварительном порядке
• Обход в порядке следования

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

Обход в порядке следования

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

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

• Строка 5-9: Создаем класс Node. Класс имеет три члена
  • Left child: содержит левый дочерний элемент узла
  • Правый ребенок: содержит правый ребенок узла
  • Данные: значение узла
• Строка 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("nnData is tree is = ", root.printTree())

print("nnresult of inorder traversal is = ", root.inorderTraversal(root))





-->
('nnData is tree is = ', [27, 14, 5, 10, 6, 31, 9])
('nnresult of inorder traversal is = ', [10, 14, 6, 27, 31, 5, 9])

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

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

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

• Строка 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("nnData is tree is = ", root.printTree())

print("nnresult of preorder traversal is = ", root.preorderTraversal(root))

-->
('nnData is tree is = ', [27, 14, 5, 10, 6, 31, 9])
('nnresult of preorder traversal is = ', [27, 14, 10, 6, 5, 31, 9])

Обход последовательностей

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

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

• Строка 4-9: Создаем класс Node. Класс имеет три члена
  • Left child: содержит левый дочерний элемент узла
  • Правый ребенок: содержит правый ребенок узла
  • Данные: значение узла
• Строка 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("nnData is tree is = ", root.printTree())

print("nnresult of postorder traversal is = ", root.postorderTraversal(root))

-->
('nnData is tree is = ', [27, 14, 5, 10, 6, 31, 9])
('nnresult of postorder traversal is = ', [10, 6, 14, 31, 9, 5, 27])

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

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

Алгоритмы поиска в порядке убывания

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

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

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

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

Освойте алгоритмы обхода деревьев в Python уже сегодня

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

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

• Дано двоичное дерево, найдите его высоту.
• Порядковый обход двоичного дерева
• Максимальная глубина двоичного дерева
• Сумма чисел от корня до листьев

Кроме того, вы можете ознакомиться с образовательным курсом Ace the Python Coding Interview. Вы узнаете, как справиться со всеми тонкостями, необходимыми для успешного прохождения собеседования по кодированию на Python, особенно по структурам данных и алгоритмам.

Как всегда, счастливого обучения!

Продолжайте изучать Python, структуры данных и алгоритмы на сайте Educative

• 8 структур данных, которые должен знать каждый программист Python
• Изучайте Python: Списки, множества и кортежи
• Алгоритмы 101: как реализовать обход дерева в JavaScript

Начните обсуждение

Какие еще концепции Python полезно знать всем разработчикам? Была ли эта статья полезной? Сообщите нам об этом в комментариях ниже!