Бинарное дерево на Python

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

• Один из узлов помечен как корневой.

• Каждый узел, отличный от корневого, связан с одним родительским узлом.

• Каждый узел может иметь произвольное количество узлов-наследников.

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

Создание корневого узла

Мы просто создаем класс Node и присваиваем ему значение. Так мы получаем дерево, в котором есть только корень.

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
   def PrintTree(self):
      print(self.data)

root = Node(10)
root.PrintTree()

Вывод

После выполнения кода выше, вы получите следующий результат:

10

Добавление узлов в дерево

Чтобы добавить узел в дерево, мы воспользуемся тем же классом Node, который описали выше, и добавим в него метод insert. Этот метод будет сравнивать значение нового узла с родительским узлом и решать, добавить ли его в дерево как левый узел или как правый. Метод PrintTree будет использоваться для вывода дерева.

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data

   def insert(self, data):
# Compare the new value with the parent node
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
            elif data > self.data:
               if self.right is None:
                  self.right = Node(data)
               else:
                  self.right.insert(data)
      else:
         self.data = data

# Print the tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
      print( self.data),
      if self.right:
         self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()

Вывод

После выполнения кода выше, вы получите следующий результат:

3 6 12 14

Проход по дереву

Дерево можно обойти, выбрав последовательность посещения узлов. Очевидно, что мы можем начать с корня, затем посетить левое поддерево, а затем правое. Или же можно начать с правого поддерева, а потом посетить левое.

Соответственно, у каждого из этих методов обхода есть свое название.

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

Обход – это процесс, позволяющий посетить все узлы дерева и вывести их значения. Поскольку все узлы соединены ребрами (ссылками), мы всегда будем начинать с корня. То есть мы не можем просто взять и получить доступ к случайному узлу в дереве. Есть три способа, которыми мы можем воспользоваться, чтобы обойти дерево:

• Обратный обход;

• Прямой обход;

• Центрированный обход.

Обратный обход

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

В коде ниже мы используем класс Node для создания плейсхолдеров для корня, левого и правого узлов-наследников. Затем мы создаем метод insert для добавления данных в дерево. Наконец, логика обратного обхода реализуется путем создания пустого списка и добавления в него сначала левого узла, после которого идет корень.

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

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
# Insert Node
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         else data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
      else:
         self.data = data
# Print the Tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
      print( self.data),
      if self.right:
         self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
   def inorderTraversal(self, root):
      res = []
      if root:
         res = self.inorderTraversal(root.left)
         res.append(root.data)
         res = res + self.inorderTraversal(root.right)
      return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))  

Вывод

После выполнения кода выше, вы получите следующий результат:

[10, 14, 19, 27, 31, 35, 42]

Прямой обход

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

В коде ниже мы используем класс Node для создания плейсхолдеров для корня, левого и правого узлов-наследников. Затем мы создаем метод insert для добавления данных в дерево. Наконец, логика прямого обхода реализуется путем создания пустого списка и добавления в него сначала корня, после которого идет левый узел.

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

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
# Insert Node
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         elif data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
         else:
            self.data = data
# Print the Tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
      print( self.data),
      if self.right:
         self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
   def PreorderTraversal(self, root):
      res = []
      if root:
         res.append(root.data)
         res = res + self.PreorderTraversal(root.left)
         res = res + self.PreorderTraversal(root.right)
      return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))

Вывод

После выполнения кода выше, вы получите следующий результат:

[27, 14, 10, 19, 35, 31, 42]

Центрированный обход

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

В коде ниже мы используем класс Node для создания плейсхолдеров для корня, левого и правого узлов-наследников. Затем мы создаем метод insert для добавления данных в дерево. Наконец, логика центрированного обхода реализуется путем создания пустого списка и добавления в него сначала левого узла, а затем правого.

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

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
# Insert Node
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         else if data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:

               self.right.insert(data)
      else:
         self.data = data
# Print the Tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))

Вывод

После выполнения кода выше, вы получите следующий результат:

[10, 19, 14, 31, 42, 35, 27]

Материал подготовлен в рамках курса «Python Developer. Basic».

Всех желающих приглашаем на онлайн-интенсив «Мобильное приложение для автоматических рассылок с использованием Kivy Framework». За 2 дня интенсива мы создадим мобильное приложение (с использованием Kivy Framework) для планирования автоматических рассылок почтовых сообщений. С его помощью мы сможем отправлять коллегам поздравления с днем рождения и другими важными праздниками и событиями.

РЕГИСТРАЦИЯ