Python - алгоритмы обхода дерева
Обход - это процесс посещения всех узлов дерева и также может распечатать их значения. Поскольку все узлы соединены ребрами (связями), мы всегда начинаем с корневого (головного) узла. То есть мы не можем получить произвольный доступ к узлу в дереве. Есть три способа, которые мы используем, чтобы пройти по дереву:
- Обход по порядку
- Предварительный заказ обхода
- Пост-заказ обход
Обход по порядку
В этом методе обхода сначала посещается левое поддерево, затем корень, а затем правое поддерево. Мы всегда должны помнить, что каждый узел может представлять собой поддерево.
В приведенной ниже программе на Python мы используем класс Node для создания заполнителей для корневого узла, а также для левого и правого узлов. Затем мы создаем функцию вставки для добавления данных в дерево. Наконец, реализуется логика обхода Inorder путем создания пустого списка и добавления сначала левого узла, а затем корневого или родительского узла. Наконец, добавлен левый узел, чтобы завершить обход Inorder. Обратите внимание, что этот процесс повторяется для каждого поддерева, пока не будут пройдены все узлы.
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()
# 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]
Предварительный заказ обхода
В этом методе обхода сначала посещается корневой узел, затем левое поддерево и, наконец, правое поддерево.
В приведенной ниже программе на Python мы используем класс Node для создания заполнителей для корневого узла, а также для левого и правого узлов. Затем мы создаем функцию вставки для добавления данных в дерево. Наконец, реализуется логика обхода предварительного заказа путем создания пустого списка и добавления сначала корневого узла, а затем левого узла. Наконец, правый узел добавлен для завершения обхода предварительного заказа. Обратите внимание, что этот процесс повторяется для каждого поддерева, пока не будут пройдены все узлы.
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]
Пост-заказ обход
В этом методе обхода корневой узел посещается последним, отсюда и название. Сначала мы обходим левое поддерево, затем правое поддерево и, наконец, корневой узел.
В приведенной ниже программе на Python мы используем класс Node для создания заполнителей для корневого узла, а также для левого и правого узлов. Затем мы создаем функцию вставки для добавления данных в дерево. Наконец, реализуется логика обхода пост-заказа путем создания пустого списка и добавления сначала левого узла, а затем правого узла. Наконец, добавляется корневой или родительский узел для завершения обхода пост-заказа. Обратите внимание, что этот процесс повторяется для каждого поддерева, пока не будут пройдены все узлы.
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()
# 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]