Бинарное дерево на 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()После выполнения кода выше, вы получите следующий результат:
Добавление узлов в дерево
Чтобы добавить узел в дерево, мы воспользуемся тем же классом 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()После выполнения кода выше, вы получите следующий результат:
Проход по дереву
Дерево можно обойти, выбрав последовательность посещения узлов. Очевидно, что мы можем начать с корня, затем посетить левое поддерево, а затем правое. Или же можно начать с правого поддерева, а потом посетить левое.
Соответственно, у каждого из этих методов обхода есть свое название.
Алгоритмы обхода деревьев
Обход – это процесс, позволяющий посетить все узлы дерева и вывести их значения. Поскольку все узлы соединены ребрами (ссылками), мы всегда будем начинать с корня. То есть мы не можем просто взять и получить доступ к случайному узлу в дереве. Есть три способа, которыми мы можем воспользоваться, чтобы обойти дерево:
Обратный обход
При таком обходе сначала посещается левое поддерево, затем корень, а затем правое поддерево. Мы всегда помним о том, что каждый узел может представлять само поддерево.
В коде ниже мы используем класс 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)) После выполнения кода выше, вы получите следующий результат:
Прямой обход
В этом методе обхода сначала посещается корень, затем левое поддерево, и, наконец, правое поддерево.
В коде ниже мы используем класс 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))После выполнения кода выше, вы получите следующий результат:
Центрированный обход
В этом методе обхода корень посещается последним, отсюда получается название обхода. Сначала мы обходим левое поддерево, потом правое, и, наконец, корень.
В коде ниже мы используем класс 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))После выполнения кода выше, вы получите следующий результат:
Материал подготовлен в рамках курса «Python Developer. Basic».
Всех желающих приглашаем на онлайн-интенсив «Мобильное приложение для автоматических рассылок с использованием Kivy Framework». За 2 дня интенсива мы создадим мобильное приложение (с использованием Kivy Framework) для планирования автоматических рассылок почтовых сообщений. С его помощью мы сможем отправлять коллегам поздравления с днем рождения и другими важными праздниками и событиями.
РЕГИСТРАЦИЯ