Python - Algoritmos de árvore transversal
Traversal é um processo para visitar todos os nós de uma árvore e pode imprimir seus valores também. Porque, todos os nós são conectados por meio de arestas (links), sempre começamos a partir do nó raiz (cabeça). Ou seja, não podemos acessar aleatoriamente um nó em uma árvore. Existem três maneiras que usamos para atravessar uma árvore -
- Transversal em ordem
- Pré-encomendar Traversal
- Traversal pós-pedido
Transversal em ordem
Neste método transversal, a subárvore esquerda é visitada primeiro, então a raiz e depois a subárvore direita. Devemos sempre lembrar que cada nó pode representar uma subárvore em si.
No programa python abaixo, usamos a classe Node para criar espaços reservados para o nó raiz, bem como os nós esquerdo e direito. Em seguida, criamos uma função de inserção para adicionar dados à árvore. Finalmente, a lógica de travessia Inorder é implementada criando uma lista vazia e adicionando o nó esquerdo primeiro, seguido pelo nó raiz ou pai. Por fim, o nó esquerdo é adicionado para completar a travessia da ordem. Observe que este processo é repetido para cada subárvore até que todos os nós sejam percorridos.
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))Quando o código acima é executado, ele produz o seguinte resultado -
[10, 14, 19, 27, 31, 35, 42]Pré-encomendar Traversal
Nesse método de passagem, o nó raiz é visitado primeiro, depois a subárvore esquerda e, finalmente, a subárvore direita.
No programa python abaixo, usamos a classe Node para criar espaços reservados para o nó raiz, bem como os nós esquerdo e direito. Em seguida, criamos uma função de inserção para adicionar dados à árvore. Finalmente, a lógica de passagem de pré-pedido é implementada criando uma lista vazia e adicionando o nó raiz primeiro, seguido pelo nó esquerdo. Por fim, o nó certo é adicionado para completar a travessia da pré-encomenda. Observe que este processo é repetido para cada subárvore até que todos os nós sejam percorridos.
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))Quando o código acima é executado, ele produz o seguinte resultado -
[27, 14, 10, 19, 35, 31, 42]Traversal pós-pedido
Neste método de passagem, o nó raiz é visitado por último, daí o nome. Primeiro, percorremos a subárvore esquerda, depois a subárvore direita e, finalmente, o nó raiz.
No programa python abaixo, usamos a classe Node para criar espaços reservados para o nó raiz, bem como os nós esquerdo e direito. Em seguida, criamos uma função de inserção para adicionar dados à árvore. Finalmente, a lógica de travessia pós-pedido é implementada criando uma lista vazia e adicionando o nó esquerdo primeiro seguido pelo nó direito. Por fim, o nó raiz ou pai é adicionado para completar a travessia pós-pedido. Observe que este processo é repetido para cada subárvore até que todos os nós sejam percorridos.
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))Quando o código acima é executado, ele produz o seguinte resultado -
[10, 19, 14, 31, 42, 35, 27]