Python - Algoritmos de recorrido de árbol
El recorrido es un proceso para visitar todos los nodos de un árbol y también puede imprimir sus valores. Porque todos los nodos están conectados a través de bordes (enlaces), siempre comenzamos desde el nodo raíz (cabeza). Es decir, no podemos acceder aleatoriamente a un nodo en un árbol. Hay tres formas que usamos para atravesar un árbol:
- Recorrido en orden
- Traversal de reserva
- Recorrido posterior al pedido
Recorrido en orden
En este método de recorrido, primero se visita el subárbol izquierdo, luego la raíz y luego el subárbol derecho. Siempre debemos recordar que cada nodo puede representar un subárbol en sí mismo.
En el siguiente programa de Python, usamos la clase Node para crear marcadores de posición para el nodo raíz, así como los nodos izquierdo y derecho. Luego creamos una función de inserción para agregar datos al árbol. Finalmente, la lógica de recorrido Inorder se implementa creando una lista vacía y agregando el nodo izquierdo primero seguido por el nodo raíz o padre. Por último, se agrega el nodo izquierdo para completar el recorrido Inorder. Tenga en cuenta que este proceso se repite para cada subárbol hasta que se atraviesan todos los nodos.
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))Cuando se ejecuta el código anterior, produce el siguiente resultado:
[10, 14, 19, 27, 31, 35, 42]Traversal de reserva
En este método de recorrido, primero se visita el nodo raíz, luego el subárbol izquierdo y finalmente el subárbol derecho.
En el siguiente programa de Python, usamos la clase Node para crear marcadores de posición para el nodo raíz, así como los nodos izquierdo y derecho. Luego creamos una función de inserción para agregar datos al árbol. Finalmente, la lógica transversal de la reserva se implementa creando una lista vacía y agregando el nodo raíz primero seguido por el nodo izquierdo. Por último, se agrega el nodo derecho para completar el recorrido del pedido anticipado. Tenga en cuenta que este proceso se repite para cada subárbol hasta que se atraviesan todos los nodos.
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))Cuando se ejecuta el código anterior, produce el siguiente resultado:
[27, 14, 10, 19, 35, 31, 42]Recorrido posterior al pedido
En este método de recorrido, el nodo raíz se visita en último lugar, de ahí el nombre. Primero atravesamos el subárbol izquierdo, luego el subárbol derecho y finalmente el nodo raíz.
En el siguiente programa de Python, usamos la clase Node para crear marcadores de posición para el nodo raíz, así como los nodos izquierdo y derecho. Luego creamos una función de inserción para agregar datos al árbol. Finalmente, la lógica transversal de post-orden se implementa creando una lista vacía y agregando el nodo izquierdo primero seguido por el nodo derecho. Por último, se agrega el nodo raíz o padre para completar el recorrido posterior al pedido. Tenga en cuenta que este proceso se repite para cada subárbol hasta que se atraviesan todos los nodos.
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))Cuando se ejecuta el código anterior, produce el siguiente resultado:
[10, 19, 14, 31, 42, 35, 27]