Бинарное дерево на 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) для планирования автоматических рассылок почтовых сообщений. С его помощью мы сможем отправлять коллегам поздравления с днем рождения и другими важными праздниками и событиями.

РЕГИСТРАЦИЯ