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

Kate · 7 Авг 2021

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

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

Мы можем создать древовидную структуру данных в 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]