Tras definir los componentes de un árbol n-ario, necesitamos elegir la estructura de datos que represente los hijos de cada nodo dentro de Python. En este tema contrastamos las alternativas más utilizadas, estudiando sus costos de memoria, facilidad de inserción y compatibilidad con los algoritmos que desarrollaremos en los próximos temas.
Si intentamos copiar el diseño binario y agregamos atributos fijos (hijo1, hijo2, hijo3, ...), obtenemos una estructura estática que no escala. Aparecen los siguientes inconvenientes:
Por eso reemplazaremos esta representación fija por estructuras flexibles que adapten el número de enlaces a las necesidades del árbol.
La alternativa más natural en Python es almacenar una lista de referencias a los hijos. Cada Nodo contiene su propia lista y un ArbolGeneral orquesta las inserciones mediante métodos, manteniendo encapsulados la raíz y la contabilidad.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.hijos = []
def agregar_hijo(self, nodo_hijo):
if nodo_hijo is None:
return
self.hijos.append(nodo_hijo)
class ArbolGeneral:
def __init__(self):
self.raiz = None
def crear_raiz(self, valor):
if self.raiz is None:
self.raiz = Nodo(valor)
return self.raiz
def agregar_hijo(self, padre, valor):
nuevo = Nodo(valor)
padre.agregar_hijo(nuevo)
return nuevo
def imprimir(self, nodo=None, sangria=0):
nodo = nodo or self.raiz
if nodo is None:
return
print(" " * sangria + f"-{nodo.valor}")
for hijo in nodo.hijos:
self.imprimir(hijo, sangria + 1)
if __name__ == "__main__":
arbol = ArbolGeneral()
raiz = arbol.crear_raiz(1)
nodo_a = arbol.agregar_hijo(raiz, 2)
nodo_b = arbol.agregar_hijo(raiz, 3)
arbol.agregar_hijo(nodo_a, 4)
arbol.agregar_hijo(nodo_a, 5)
arbol.imprimir()Con esta representación, insertar es tan fácil como anexar un nuevo elemento a la lista. El costo principal es recorrer la colección para obtener el n-ésimo hijo o reordenar cuando el orden importa.
Cuando el grado máximo es conocido y pequeño, una lista acotada simplifica el acceso directo a cualquier hijo. Definimos una constante con el grado y controlamos la cantidad ocupada. Esta estrategia sigue siendo orientada a objetos con una clase de nodo especializada y un árbol que encapsula la raíz.
MAX_HIJOS = 4
class NodoGradoFijo:
def __init__(self, valor):
self.valor = valor
self.hijos = [None] * MAX_HIJOS
self.cantidad_hijos = 0
def agregar_hijo(self, nodo_hijo):
if nodo_hijo is None or self.cantidad_hijos >= MAX_HIJOS:
return False
self.hijos[self.cantidad_hijos] = nodo_hijo
self.cantidad_hijos += 1
return True
class ArbolGradoFijo:
def __init__(self):
self.raiz = None
def crear_raiz(self, valor):
if self.raiz is None:
self.raiz = NodoGradoFijo(valor)
return self.raiz
def agregar_hijo(self, padre, valor):
hijo = NodoGradoFijo(valor)
return padre.agregar_hijo(hijo)
if __name__ == "__main__":
arbol = ArbolGradoFijo()
raiz = arbol.crear_raiz("root")
arbol.agregar_hijo(raiz, "left")
arbol.agregar_hijo(raiz, "right")
print(raiz.hijos[: raiz.cantidad_hijos])Utilizar listas acotadas permite indexar hijos inmediatamente, pero limita la cantidad de descendientes y obliga a desplazar elementos si queremos insertar en posiciones intermedias.
El patrón hijo-izquierdo/hermano-derecho (LCRS) convierte cualquier árbol n-ario en un árbol binario donde la referencia primer_hijo actúa como enlace hacia el subárbol más profundo y siguiente_hermano enlaza los nodos laterales. La clase ArbolGeneral puede envolver este modelo para centralizar la raíz y los métodos de inserción.
class NodoLCRS:
def __init__(self, valor):
self.valor = valor
self.primer_hijo = None
self.siguiente_hermano = None
self.padre = None
def agregar_hijo(self, nodo_hijo):
if nodo_hijo is None:
return
nodo_hijo.padre = self
nodo_hijo.siguiente_hermano = self.primer_hijo
self.primer_hijo = nodo_hijo
class ArbolGeneralLCRS:
def __init__(self):
self.raiz = None
def crear_raiz(self, valor):
if self.raiz is None:
self.raiz = NodoLCRS(valor)
return self.raiz
def agregar_hijo(self, padre, valor):
nuevo = NodoLCRS(valor)
padre.agregar_hijo(nuevo)
return nuevo
def recorrer_hijos(self, nodo):
hijo = nodo.primer_hijo
while hijo:
yield hijo
hijo = hijo.siguiente_hermanoPara recorrer a todos los hijos de un nodo basta con iterar sobre la cadena de hermanos. Los algoritmos de borrado o copia se implementan como operaciones binarias, simplificando la recursión.
La elección depende del escenario: si esperamos nodos con cientos de hijos, la lista dinámica o LCRS son superiores; si solo existen hasta 3 o 4 hijos y necesitamos accederlos por posición, la lista acotada es práctica.
En la práctica no existe una opción universal; lo importante es documentar la elección y encapsular las operaciones para poder migrar entre representaciones sin reescribir todo el código.
Para poner en práctica la representación con listas de hijos, a continuación presentamos un script orientado a objetos listo para ejecutar en VS Code o PyCharm. El ejemplo crea un árbol general, imprime su contenido y delega en el recolector de basura la liberación de memoria.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.hijos = []
def agregar_hijo(self, nodo_hijo):
if nodo_hijo is None:
return
self.hijos.append(nodo_hijo)
class ArbolGeneral:
def __init__(self):
self.raiz = None
def crear_raiz(self, valor):
if self.raiz is None:
self.raiz = Nodo(valor)
return self.raiz
def agregar_hijo(self, padre, valor):
nuevo = Nodo(valor)
padre.agregar_hijo(nuevo)
return nuevo
def imprimir(self, nodo=None, sangria=0):
nodo = nodo or self.raiz
if nodo is None:
return
print(" " * sangria + f"-{nodo.valor}")
for hijo in nodo.hijos:
self.imprimir(hijo, sangria + 1)
def crear_arbol_demo(self):
self.raiz = Nodo(1)
nodo_a = Nodo(2)
nodo_b = Nodo(3)
nodo_c = Nodo(4)
self.raiz.agregar_hijo(nodo_c)
self.raiz.agregar_hijo(nodo_b)
self.raiz.agregar_hijo(nodo_a)
nodo_d = Nodo(5)
nodo_e = Nodo(6)
nodo_b.agregar_hijo(nodo_e)
nodo_b.agregar_hijo(nodo_d)
return self.raiz
if __name__ == "__main__":
arbol = ArbolGeneral()
arbol.crear_arbol_demo()
print("Arbol con lista dinamica de hijos:")
arbol.imprimir()El programa demuestra cómo insertar hijos en cualquier orden, recorrerlos con recursión y dejar que Python administre la memoria sin fugas.