HOWTO · Python

Implementar una estructura de datos de árbol en Python

En este artículo, veremos cómo implementar una estructura de datos de árbol en Python.

En esta página

Un árbol organiza los datos en nodos conectados por aristas. Cada arista conecta un nodo padre con uno hijo, y un nodo sin hijos es una hoja. Entre los tipos de árboles se encuentran los árboles binarios, ternarios, binarios de búsqueda y AVL; en un árbol binario, cada nodo puede tener como máximo dos hijos. Esta guía construye un árbol binario pequeño con una clase Node personalizada, lo recorre en tres órdenes de profundidad y presenta anytree como alternativa mediante una biblioteca.

Árbol binario con raíz 10, hijos 34 y 89, y los nodos 45 y 50 como hijos de 34

Implementar desde cero una estructura de árbol en Python

Un nodo sencillo de un árbol binario necesita un lugar para almacenar su valor y referencias a sus dos nodos hijos. La clase Node de abajo guarda el valor en data; left y right empiezan en None y luego pueden apuntar a nodos hijos. Al conectar estos objetos se crea el árbol.

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


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

Aquí, root es el nodo padre de 34 y 89. Los nodos 45 y 50 son hijos de 34; 89, 45 y 50 son hojas. Esta estructura es específicamente un árbol binario, porque cada nodo tiene como máximo dos referencias a hijos. Otros tipos de árboles pueden necesitar una representación distinta, como una colección de hijos en lugar de atributos fijos left y right.

Recorrer un árbol binario en Python

Un recorrido procesa cada nodo una sola vez; el orden depende de cuándo se visita el nodo respecto de las llamadas recursivas. En el recorrido en preorden, se visita el nodo actual antes que sus subárboles izquierdo y derecho. En el recorrido en inorden, se visita primero el subárbol izquierdo, luego el nodo actual y, por último, el subárbol derecho. En el recorrido en postorden, se visitan ambos subárboles antes que el nodo actual. El ejemplo completo de abajo construye el mismo árbol e imprime cada orden.

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


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


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


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


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

print("Pre-order:")
preorder(root)
print("In-order:")
inorder(root)
print("Post-order:")
postorder(root)

Las llamadas recursivas siguen las mismas referencias left y right creadas en la primera sección. Para recorrer otro árbol, conserva las funciones de recorrido y cambia la construcción de los nodos; la posición elegida para visitar cada nodo determina el orden de los valores.

Implementar un árbol con una biblioteca de Python

Para árboles con muchos nodos o con funciones que van más allá de este pequeño ejemplo de árbol binario, anytree ofrece relaciones entre nodos y un renderizador. Instálala en el entorno de tu proyecto con pip install anytree. En su API, Node recibe el nombre del nodo como argumento posicional; para asociar un hijo, pasa parent=root como argumento con nombre. RenderTree recorre la jerarquía y proporciona el prefijo que se usa para mostrar cada nivel.

Para crear una estructura igual a la anterior, el patrón de la API es root = Node("10"), seguido de Node("34", parent=root) y Node("89", parent=root). Crea Node("45", parent=left_child) y Node("50", parent=left_child) para colocar ambas hojas debajo de 34; luego, itera con for pre, fill, node in RenderTree(root) e imprime pre + node.name. Estos fragmentos describen la API de la biblioteca; no se incluye evidencia de que se hayan ejecutado.