El árbol representa los nodos conectados por bordes. Es una estructura de datos no lineal. Tiene las siguientes propiedades:
-
Un nodo está marcado como nodo raíz.
-
Cada nodo que no sea la raíz está asociado con un nodo principal.
-
Cada nodo puede tener un número arbiatry de nodo chid.
Creamos una estructura de datos de árbol en Python utilizando el concepto de nodo os discutido anteriormente. Designamos un nodo como nodo raíz y luego agregamos más nodos como nodos secundarios. A continuación se muestra el programa para crear el nodo raíz.
Crear raíz
Simplemente creamos una clase Node y agregamos asignar un valor al nodo. Esto se convierte en un árbol con solo un nodo raíz.
Ejemplo
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()
Producción
Cuando se ejecuta el código anterior, produce el siguiente resultado:
10
Insertar en un árbol
Para insertar en un árbol usamos la misma clase de nodo creada anteriormente y le agregamos una clase de inserción. La clase de inserción compara el valor del nodo con el nodo principal y decide agregarlo como un nodo izquierdo o un nodo derecho. Finalmente, la clase PrintTree se usa para imprimir el árbol.
Ejemplo
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()
Producción
Cuando se ejecuta el código anterior, produce el siguiente resultado:
3 6 12 14
Atravesando un árbol
El árbol se puede atravesar decidiendo una secuencia para visitar cada nodo. Como podemos ver claramente, podemos comenzar en un nodo y luego visitar el subárbol izquierdo primero y el subárbol derecho a continuación. O también podemos visitar el subárbol derecho primero y el subárbol izquierdo a continuación. En consecuencia, existen diferentes nombres para estos métodos de recorrido de árbol.
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. Debido a que 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
-
Preordenar Traversal
-
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 para los nodos izquierdo y derecho. Luego, creamos una función de inserción para agregar datos al árbol. Finalmente, la lógica transversal en orden 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 en orden. Tenga en cuenta que este proceso se repite para cada subárbol hasta que se atraviesan todos los nodos.
Ejemplo
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))
Producción
Cuando se ejecuta el código anterior, produce el siguiente resultado:
[10, 14, 19, 27, 31, 35, 42]
Preordenar Traversal
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 para 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 del 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.
Ejemplo
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))
Producción
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 para 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.
Ejemplo
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))
Producción
Cuando se ejecuta el código anterior, produce el siguiente resultado:
[10, 19, 14, 31, 42, 35, 27]