Бинарное дерево на 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))
Вывод
После выполнения кода выше, вы получите следующий результат:
Бинарное дерево на Python
Дерево представляет из себя узлы, соединенные ребрами, и является нелинейной структурой данных. Бинарное дерево обладает следующими особенностями: Один из узлов помечен как корневой.Каждый.
habr.com
Источник
Бинарное Дерево
Двоичное дерево — древовидная структура данных, в которой у родительских узлов не может быть больше двух детей.
Строим двоичное дерево на Python
Определим метод __init__() . Как всегда, он принимает self . Также мы передаем в него значение, которое будет храниться в узле. Установим значение узла, а затем определим левый и правый указатель (для начала поставим им значение None).
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right И… все! Если речь идет о двоичном дереве, единственное, что его отличает от связного списка, это то, что вместо next у нас тут есть left и right.
Давайте построим дерево, которое изображено на схеме в начале статьи. Верхний узел имеет значение 1. Далее мы устанавливаем левые и правые узлы, пока не получим желаемое дерево.
tree = TreeNode(1) tree.left = TreeNode(2) tree.right = TreeNode(3) tree.left.left = TreeNode(4) tree.left.right = TreeNode(5) Создание дерева из list
def from_list(l): nodes = [TreeNode(v) for v in l] kids = nodes[::-1] root = kids.pop() for node in nodes: if node: if kids: node.left = kids.pop() if kids: node.right = kids.pop() return root t = TreeNode.from_list([4,2,7,1,3,6,9]) print(t) def creatBTree(data, index): pNode = None if index len(data): if data[index] == None: return pNode = TreeNode(data[index]) pNode.left = creatBTree(data, 2 * index + 1) # [1, 3, 7, 15, . ] pNode.right = creatBTree(data, 2 * index + 2) # [2, 5, 12, 25, . ] return pNode lst = [5,4,8,11,None,13,4,7,2,None,None,None,1] root = creatBTree(lst, 0) Обход двоичного дерева
Итак, вы построили дерево и теперь вам, вероятно, любопытно, как же его увидеть. Нет никакой команды, которая позволила бы вывести на экран дерево целиком, тем не менее мы можем обойти его, посетив каждый узел. Но в каком порядке выводить узлы?
Самые простые в реализации обходы дерева
Вы также можете услышать такие термины, как поиск в ширину и поиск в глубину, но их реализация сложнее, ее мы рассмотрим как-нибудь потом.
Итак, что из себя представляют три варианта обхода, указанные выше? Давайте еще раз посмотрим на наше дерево.
При прямом обходе мы посещаем родительские узлы до посещения узлов-потомков. В случае с нашим деревом мы будем обходить узлы в таком порядке: 1, 2, 4, 5, 3.
Обратный обход двоичного дерева — это когда вы сначала посещаете узлы-потомки, а затем — их родительские узлы. В нашем случае порядок посещения узлов при обратном обходе будет таким: 4, 5, 2, 3, 1.
При центрированном обходе мы посещаем все узлы слева направо. Центрированный обход нашего дерева — это посещение узлов 4, 2, 5, 1, 3.
Давайте напишем методы обхода для нашего двоичного дерева.
Прямой обход (Pre-Order)
Написать обход просто. Прямой обход — это посещение родительского узла, а затем каждого из его потомков. Мы «посетим» родительский узел, выведя его на экран, а затем «обойдем» детей, вызывая этот метод рекурсивно для каждого узла-потомка.
# Выводит родителя до всех его потомков def pre_order(node): if node: print(node.value) pre_order(node.left) pre_order(node.right) Дополнительные ссылки
Источник