Los recorridos definen el orden en el que visitamos los nodos de un árbol binario. Dominar las variantes principales permite imprimir, buscar y serializar la estructura sin perder información. En este tema implementamos las versiones recursivas e iterativas de preorden, inorden y postorden, sumamos un recorrido por niveles y finalizamos con un ejemplo ejecutable en Python.
Trabajaremos con el mismo modelo de nodo de los temas anteriores. Mantener una definición consistente asegura que cada helper funcione sin ajustes.
class Nodo:
def __init__(self, valor, nivel=0):
self.valor = valor
self.izquierdo = None
self.derecho = None
self.nivel = nivel
Preorden visita primero el nodo actual, luego el subárbol izquierdo y finalmente el derecho. Es ideal para clonar el árbol o guardarlo en disco.
def recorrer_preorden(nodo):
if nodo is None:
return
print(f"{nodo.valor} (nivel {nodo.nivel})")
recorrer_preorden(nodo.izquierdo)
recorrer_preorden(nodo.derecho)
Esta versión recursiva es directa y funciona siempre que la profundidad no exceda el límite de la pila del programa.
Inorden recorre el subárbol izquierdo, luego el nodo actual y al final el derecho. En un árbol de búsqueda binaria produce la lista de valores en orden ascendente.
def recorrer_inorden(nodo):
if nodo is None:
return
recorrer_inorden(nodo.izquierdo)
print(f"{nodo.valor} (nivel {nodo.nivel})")
recorrer_inorden(nodo.derecho)
Postorden procesa ambos subárboles antes del nodo actual. Se usa para liberar memoria o evaluar expresiones aritméticas donde cada operador necesita los resultados de sus hijos.
def recorrer_postorden(nodo):
if nodo is None:
return
recorrer_postorden(nodo.izquierdo)
recorrer_postorden(nodo.derecho)
print(f"{nodo.valor} (nivel {nodo.nivel})")
Cuando la profundidad es grande podemos optar por pilas explícitas para evitar desbordes. A continuación una implementación simple de preorden iterativo en Python.
def recorrer_preorden_iterativo(raiz):
if raiz is None:
return
pila = [raiz]
while pila:
actual = pila.pop()
print(f"{actual.valor} (nivel {actual.nivel})")
if actual.derecho:
pila.append(actual.derecho)
if actual.izquierdo:
pila.append(actual.izquierdo)
La pila usa una lista nativa; en proyectos grandes podrías extraerla a una clase para controlar memoria y límites de profundidad.
Recorrer por niveles implica visitar los nodos en el orden en que se descubren al avanzar de izquierda a derecha. Utilizamos una cola basada en deque.
from collections import deque
def recorrer_por_niveles(raiz):
if raiz is None:
return
cola = deque([raiz])
while cola:
actual = cola.popleft()
print(f"{actual.valor} (nivel {actual.nivel})")
if actual.izquierdo:
cola.append(actual.izquierdo)
if actual.derecho:
cola.append(actual.derecho)
El siguiente archivo crea un árbol, ejecuta los recorridos principales y muestra los resultados en consola.
from collections import deque
class Nodo:
def __init__(self, valor, nivel=0):
self.valor = valor
self.izquierdo = None
self.derecho = None
self.nivel = nivel
class ArbolBinarioOrdenado:
def __init__(self):
self.raiz = None
self.cantidad = 0
def crear_nodo(self, valor, nivel=0):
return Nodo(valor, nivel=nivel)
def insertar(self, valor):
if self.raiz is None:
self.raiz = self.crear_nodo(valor)
self.cantidad = 1
return self.raiz
actual = self.raiz
while True:
if valor < actual.valor:
if actual.izquierdo is None:
actual.izquierdo = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.izquierdo
actual = actual.izquierdo
else:
if actual.derecho is None:
actual.derecho = self.crear_nodo(valor, nivel=actual.nivel + 1)
self.cantidad += 1
return actual.derecho
actual = actual.derecho
def imprimir_preorden(self, nodo):
if nodo is None:
return
print(f"{nodo.valor} (nivel {nodo.nivel})")
self.imprimir_preorden(nodo.izquierdo)
self.imprimir_preorden(nodo.derecho)
def imprimir_inorden(self, nodo):
if nodo is None:
return
self.imprimir_inorden(nodo.izquierdo)
print(f"{nodo.valor} (nivel {nodo.nivel})")
self.imprimir_inorden(nodo.derecho)
def imprimir_postorden(self, nodo):
if nodo is None:
return
self.imprimir_postorden(nodo.izquierdo)
self.imprimir_postorden(nodo.derecho)
print(f"{nodo.valor} (nivel {nodo.nivel})")
def imprimir_preorden_iterativo(self, nodo):
if nodo is None:
return
pila = [nodo]
while pila:
actual = pila.pop()
print(f"{actual.valor} (nivel {actual.nivel})")
if actual.derecho:
pila.append(actual.derecho)
if actual.izquierdo:
pila.append(actual.izquierdo)
def imprimir_por_niveles(self, nodo):
if nodo is None:
return
cola = deque([nodo])
while cola:
actual = cola.popleft()
print(f"{actual.valor} (nivel {actual.nivel})")
if actual.izquierdo:
cola.append(actual.izquierdo)
if actual.derecho:
cola.append(actual.derecho)
def limpiar_arbol(self):
self._limpiar(self.raiz)
self.raiz = None
self.cantidad = 0
def _limpiar(self, nodo):
if nodo is None:
return
self._limpiar(nodo.izquierdo)
self._limpiar(nodo.derecho)
nodo.izquierdo = None
nodo.derecho = None
if __name__ == "__main__":
arbol = ArbolBinarioOrdenado()
valores = [10, 5, 15, 3, 7, 12, 18]
for valor in valores:
arbol.insertar(valor)
print("Preorden:")
arbol.imprimir_preorden(arbol.raiz)
print("\nInorden:")
arbol.imprimir_inorden(arbol.raiz)
print("\nPostorden:")
arbol.imprimir_postorden(arbol.raiz)
print("\nPreorden iterativo:")
arbol.imprimir_preorden_iterativo(arbol.raiz)
print("\nRecorrido por niveles:")
arbol.imprimir_por_niveles(arbol.raiz)
arbol.limpiar_arbol()