Con la estructura de nodos lista, necesitamos recorrer el árbol para visitar, procesar y verificar cada dato. En este tema aplicamos los patrones de recorrido más comunes usando clases Nodo y ArbolGeneral en Python, tanto con listas de hijos como con el esquema hijo-izquierdo/hermano-derecho.
En el recorrido preorden visitamos el nodo actual antes que sus hijos. Este orden resulta ideal para serializar el árbol, copiarlo u obtener una vista jerárquica.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.primer_hijo = None
self.siguiente_hermano = None
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)
nuevo.siguiente_hermano = padre.primer_hijo
padre.primer_hijo = nuevo
return nuevo
def preorden(self, nodo=None):
nodo = nodo or self.raiz
if nodo is None:
return
print(nodo.valor, end=" ")
hijo = nodo.primer_hijo
while hijo:
self.preorden(hijo)
hijo = hijo.siguiente_hermano
def construir_demo():
arbol = ArbolGeneral()
raiz = arbol.crear_raiz(1)
b = arbol.agregar_hijo(raiz, 3)
a = arbol.agregar_hijo(raiz, 2)
arbol.agregar_hijo(a, 4)
arbol.agregar_hijo(a, 5)
arbol.agregar_hijo(b, 6)
return arbol
if __name__ == "__main__":
arbol = construir_demo()
arbol.preorden()
print()El ciclo de hijos itera sobre los hermanos y cada llamada recursiva procesa el subárbol completo del hijo.
El recorrido postorden procesa primero a los hijos y luego al nodo. Este orden es el preferido para liberar memoria, calcular alturas o evaluar expresiones.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.primer_hijo = None
self.siguiente_hermano = None
class ArbolGeneral:
def __init__(self, raiz):
self.raiz = raiz
def postorden(self, nodo=None):
nodo = nodo or self.raiz
if nodo is None:
return
hijo = nodo.primer_hijo
while hijo:
self.postorden(hijo)
hijo = hijo.siguiente_hermano
print(nodo.valor, end=" ")
def construir_demo():
raiz = Nodo(1)
a = Nodo(2)
b = Nodo(3)
c = Nodo(4)
raiz.primer_hijo = a
a.siguiente_hermano = b
b.siguiente_hermano = c
d = Nodo(5)
e = Nodo(6)
b.primer_hijo = d
d.siguiente_hermano = e
return ArbolGeneral(raiz)
if __name__ == "__main__":
arbol = construir_demo()
arbol.postorden()
print()Recuerda que cada llamada delimita un subárbol completo; al terminar, disponemos del orden necesario para tareas como la liberación de nodos.
El breadth-first search (BFS) recorre los nodos nivel por nivel utilizando una cola. En Python usamos collections.deque para encolar y desencolar eficientemente.
from collections import deque
class Nodo:
def __init__(self, valor):
self.valor = valor
self.primer_hijo = None
self.siguiente_hermano = None
class ArbolGeneral:
def __init__(self, raiz):
self.raiz = raiz
def bfs(self):
if self.raiz is None:
return
cola = deque([self.raiz])
while cola:
actual = cola.popleft()
print(actual.valor, end=" ")
hijo = actual.primer_hijo
while hijo:
cola.append(hijo)
hijo = hijo.siguiente_hermano
def construir_demo():
raiz = Nodo(1)
a = Nodo(2)
b = Nodo(3)
c = Nodo(4)
raiz.primer_hijo = a
a.siguiente_hermano = b
b.siguiente_hermano = c
d = Nodo(5)
e = Nodo(6)
b.primer_hijo = d
d.siguiente_hermano = e
return ArbolGeneral(raiz)
if __name__ == "__main__":
arbol = construir_demo()
arbol.bfs()
print()Este recorrido es ideal para analizar la estructura por niveles, calcular anchuras y exportar el árbol a formatos que dependen de orden topológico.
Las funciones anteriores se apoyan en recursión natural. Sin embargo, cuando la altura del árbol es grande podría convenir una versión iterativa con pilas manuales.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.primer_hijo = None
self.siguiente_hermano = None
class ArbolGeneral:
def __init__(self, raiz):
self.raiz = raiz
def preorden_iterativo(self):
if self.raiz is None:
return
pila = [self.raiz]
while pila:
actual = pila.pop()
print(actual.valor, end=" ")
hijos = []
hijo = actual.primer_hijo
while hijo:
hijos.append(hijo)
hijo = hijo.siguiente_hermano
for h in reversed(hijos):
pila.append(h)
def construir_demo():
raiz = Nodo(1)
a = Nodo(2)
b = Nodo(3)
c = Nodo(4)
raiz.primer_hijo = a
a.siguiente_hermano = b
b.siguiente_hermano = c
d = Nodo(5)
e = Nodo(6)
b.primer_hijo = d
d.siguiente_hermano = e
return ArbolGeneral(raiz)
if __name__ == "__main__":
arbol = construir_demo()
arbol.preorden_iterativo()
print()La versión iterativa evita desbordar la pila del sistema a costa de administrar estructuras auxiliares.
Los recorridos por niveles utilizan colas, mientras que las variantes iterativas de preorden y postorden emplean pilas. También es posible apoyar los recorridos en listas y arreglos temporales para preservar el orden original de los hijos. Elegir la estructura correcta depende de si necesitamos FIFO (cola), LIFO (pila) o un almacenamiento temporal ordenado.
En Python las colas (deque) y pilas (listas) se liberan automáticamente al salir del ámbito, pero sigue siendo buena práctica encapsular su uso en funciones o métodos para aislar la lógica de recorrido.
Todos los recorridos visitan cada nodo una sola vez, por lo que su complejidad temporal es O(n), siendo n la cantidad de nodos del árbol. La complejidad espacial depende de la estructura auxiliar:
Monitorear estas cotas ayuda a evitar sorpresas cuando el árbol crece con datos reales.