Implementar una estructura de datos de árbol en Python

1. Implementar un árbol desde cero en Python
2. Atravesar un árbol binario en Python
3. Implementar un árbol usando una biblioteca de Python

Un árbol es una de las estructuras de datos. Una estructura de datos no es más que cómo organizamos los datos en la memoria. Un árbol es una combinación de nodos (también conocidos como vértices) y aristas. Un árbol puede tener cualquier número de nodos y bordes. Un nodo es donde almacenamos los datos y un borde es una ruta entre 2 nodos. Hay varios tipos de árboles disponibles, como árbol binario, árbol ternario, árbol binario de búsqueda, árbol AVL, etc.

Tipos de nodos en un árbol:

1. Nodo padre: un nodo que tiene uno o más hijos.
2. Nodo hijo: un nodo que tiene un nodo padre.
3. Nodo hoja: un nodo que no tiene hijos.

En este artículo, veamos primero cómo implementar un árbol desde cero sin usar ninguna biblioteca, y luego verá cómo implementar un árbol con la ayuda de una biblioteca de Python.

Implementar un árbol desde cero en Python

Para crear un árbol en Python, primero tenemos que empezar creando una clase Node que representará un solo nodo. Esta clase Node contendrá 3 variables; la primera es la left que apunta al hijo izquierdo, la segunda variable data que contiene el valor de ese nodo y la variable right apunta al hijo derecho.

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

Inicialicemos un árbol.

root = Node(10)

root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

El árbol se ve como abajo.

          10
        /    \
       34      89
     /    \ 
    45    50 

Siempre que cree un objeto de la clase Node, se llamará al constructor __init__ y se inicializarán todas las variables dentro de ese constructor. La root contiene el nodo raíz del árbol, que tiene un valor de 10, y root.left y root.right mediante el cual insertaremos el hijo de la izquierda con el valor de 34 y el de la derecha child al nodo raíz con el valor 89. Dado que es un árbol binario, cada nodo contendrá como máximo dos nodos.

Al final, insertamos dos nodos más en el árbol, es decir, 45 y 50, como hijos del nodo 34. Puede insertar la cantidad de nodos que desee dentro de un árbol, según el tipo de árbol que esté creando.

Atravesar un árbol binario en Python

Ahora que hemos creado un árbol, recorramos el árbol para imprimir los elementos del árbol. Un recorrido visita todos los nodos de un árbol. Cada nodo de un árbol se visitará tres veces en el recorrido. Una forma en la que atravesamos un árbol es de arriba a abajo y de izquierda a derecha.

Recorrido de pedidos anticipados

Mientras atravesamos un árbol, siempre que vemos el nodo por primera vez, imprimimos ese nodo y luego realizamos la recursividad en el nodo izquierdo y luego en el nodo derecho.

def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

Producción :

10 
34 
45 
50 
89

Recorrido en orden

Mientras realizamos el recorrido en orden, primero realizamos la recursividad en el nodo izquierdo y luego, cuando visitamos el mismo nodo por segunda vez, imprimimos ese nodo. Luego realizamos recursividad en el nodo derecho.

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

Producción :

45 
34 
50 
10 
89

Recorrido posterior al pedido

Para el recorrido posterior al pedido, realizamos la recursividad en el nodo izquierdo y el nodo derecho, y luego, cuando visitamos el mismo nodo por tercera vez, imprimimos ese nodo.

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)

Producción :

45
50
34
89
10

Implementar un árbol usando una biblioteca de Python

Como hemos visto, implementar un árbol desde cero lleva algo de tiempo y requiere mucho código. Una forma más fácil de implementar un árbol en Python es usando una biblioteca llamada anytree. La biblioteca anytree le permite crear un árbol sin escribir una tonelada de código.

Para usar la biblioteca anytree, primero tenemos que instalarla con la ayuda del siguiente comando.

pip install anytree

Aquí, también estamos creando el mismo árbol que hemos creado anteriormente. Ahora podemos importar Node y RenderTree desde la biblioteca anytree.

from anytree import Node, RenderTree

root = Node(10)

level_1_child_1 = Node(34, parent=root)
level_1_child_2 = Node(89, parent=root)
level_2_child_1 = Node(45, parent=level_1_child_1)
level_2_child_2 = Node(50, parent=level_1_child_2)

for pre, fill, node in RenderTree(root):
    print("%s%s" % (pre, node.name))

# Tree Structure
#          10
#        /    \
#       34      89
#     /    \
#    45    50

Producción :

10
├── 34
│   └── 45
└── 89
    └── 50

Aquí, el Node creará un nodo para nosotros que toma dos parámetros; el primero es el valor del nodo y el segundo es el nombre del nodo principal (este es un parámetro opcional). Dado que en nuestro árbol el nodo root es el único nodo que no tiene ningún padre, mientras creamos el nodo root, solo pasaremos el primer parámetro: el valor del nodo y no el segundo parámetro. El método RenderTree nos ayudará a imprimir el árbol completo como se muestra en la salida.