El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Recorridos de Árboles

Siguiente ►
►

Ya sabes construir árboles binarios; ahora toca visitarlos con método. En una lista solo hay una manera razonable de recorrer los elementos (del primero al último); en un árbol, en cambio, en cada nodo hay que decidir: ¿proceso el nodo antes de bajar, entre sus dos hijos, o después de subir? Cada respuesta define un recorrido con nombre propio — preorden, inorden y postorden — y a ellos se suma el recorrido por niveles, que no baja en profundidad sino que barre el árbol piso a piso con una cola. Elegir el recorrido correcto es lo que diferencia "tocar todos los nodos" de "resolver el problema": en TaskFlow, exportar la jerarquía, calcular horas acumuladas y pintar el organigrama por niveles usan tres recorridos distintos. Además, esta lección reúne a viejos amigos: la recursión y la pila explícita del módulo 3, y la cola del módulo 4.

Contenido

  1. El problema: ¿en qué orden visito los nodos?
  2. Preorden, inorden y postorden: los tres recorridos en profundidad
  3. Traza detallada: los tres recorridos sobre el mismo árbol
  4. Recorrido por niveles: la cola entra en escena
  5. Versiones iterativas con pila explícita
  6. Cuándo usar cada recorrido (con TaskFlow como guía)

El problema: ¿en qué orden visito los nodos?

Recorrer un árbol es visitar cada nodo exactamente una vez. Con la definición recursiva del árbol binario (un nodo + subárbol izquierdo + subárbol derecho), recorrerlo exige hacer tres cosas: procesar el Nodo, recorrer el subárbol Izquierdo y recorrer el subárbol Derecho. Lo único que distingue a los recorridos en profundidad es el momento en que se procesa el nodo (mantendremos siempre izquierda antes que derecha):

Recorrido Orden Nemotecnia
Preorden N, I, D El nodo antes que sus hijos
Inorden I, N, D El nodo entre sus hijos
Postorden I, D, N El nodo después de sus hijos

Los tres son recorridos en profundidad (DFS, depth-first): se hunden por una rama hasta el fondo antes de tocar la siguiente. El cuarto recorrido, por niveles (BFS, breadth-first), rompe el molde: visita todos los nodos de profundidad 0, luego todos los de profundidad 1, etc. Adelanto para el módulo 7: DFS y BFS son en realidad estrategias generales de exploración de grafos; aquí las conocemos en su versión doméstica, sobre árboles, donde son más simples porque no hay ciclos.

Preorden, inorden y postorden: los tres recorridos en profundidad

Las tres funciones son casi idénticas — solo se mueve una línea. Usaremos este árbol durante toda la lección:

graph TD
    A((10)) --> B((6))
    A --> C((15))
    B --> D((3))
    B --> E((8))
    C --> F((12))
    C --> G((20))
class NodoBinario:
    def __init__(self, valor):
        self.valor = valor
        self.izquierdo = None
        self.derecho = None

raiz = NodoBinario(10)
raiz.izquierdo = NodoBinario(6)
raiz.derecho = NodoBinario(15)
raiz.izquierdo.izquierdo = NodoBinario(3)
raiz.izquierdo.derecho = NodoBinario(8)
raiz.derecho.izquierdo = NodoBinario(12)
raiz.derecho.derecho = NodoBinario(20)

def preorden(nodo, resultado):
    if nodo is None:
        return
    resultado.append(nodo.valor)          # N primero...
    preorden(nodo.izquierdo, resultado)   # ...luego I...
    preorden(nodo.derecho, resultado)     # ...luego D

def inorden(nodo, resultado):
    if nodo is None:
        return
    inorden(nodo.izquierdo, resultado)    # I primero...
    resultado.append(nodo.valor)          # ...N en medio...
    inorden(nodo.derecho, resultado)      # ...luego D

def postorden(nodo, resultado):
    if nodo is None:
        return
    postorden(nodo.izquierdo, resultado)  # I...
    postorden(nodo.derecho, resultado)    # ...D...
    resultado.append(nodo.valor)          # ...y N al final

for f in (preorden, inorden, postorden):
    r = []
    f(raiz, r)
    print(f.__name__, r)
# preorden  [10, 6, 3, 8, 15, 12, 20]
# inorden   [3, 6, 8, 10, 12, 15, 20]
# postorden [3, 8, 6, 12, 20, 15, 10]

Tres observaciones antes de la traza:

  • Los tres cuestan O(n) en tiempo (cada nodo se visita una vez) y O(altura) en memoria — la pila de llamadas del módulo 3 llega a apilar tantas llamadas como profundidad tenga la rama más honda.
  • En preorden, la raíz sale la primera; en postorden, la última. Este detalle será clave en el ejercicio de reconstrucción de 06-08.
  • Mira la salida de inorden: [3, 6, 8, 10, 12, 15, 20]. Ordenada. No es casualidad: este árbol cumple (spoiler) la propiedad que definirá la próxima lección, y el inorden de un árbol así siempre sale en orden ascendente. Es el anuncio formal: en 06-04 esto pasará de curiosidad a teorema y herramienta.

Traza detallada: los tres recorridos sobre el mismo árbol

Sigamos preorden paso a paso, con la pila de llamadas a la vista (sangría = profundidad de la llamada):

preorden(10): añade 10                        → [10]
  preorden(6): añade 6                        → [10, 6]
    preorden(3): añade 3                      → [10, 6, 3]
      preorden(None) x2: return
    preorden(8): añade 8                      → [10, 6, 3, 8]
      preorden(None) x2: return
  preorden(15): añade 15                      → [10, 6, 3, 8, 15]
    preorden(12): añade 12                    → [10, 6, 3, 8, 15, 12]
    preorden(20): añade 20                    → [10, 6, 3, 8, 15, 12, 20]

Cada llamada añade su valor nada más entrar y luego delega. Ahora inorden sobre el subárbol izquierdo (el patrón se repite arriba):

inorden(10)
  inorden(6)
    inorden(3)
      inorden(None): return   ← 3 no tiene hijo izquierdo
      añade 3                                 → [3]
      inorden(None): return
    añade 6                   ← solo tras agotar TODO su subárbol izquierdo → [3, 6]
    inorden(8)
      añade 8                                 → [3, 6, 8]
  añade 10                    ← el 10 espera a que acabe su rama izquierda entera → [3, 6, 8, 10]
  inorden(15) ...                             → [3, 6, 8, 10, 12, 15, 20]

Y postorden: cada nodo espera a que terminen sus dos subárboles — por eso 6 sale después de 3 y 8, y la raíz 10 sale la última de todas. Un truco visual para autocomprobarte sin trazar:

graph TD
    A(("10 ③")) --> B(("6 ②"))
    A --> C(("15 ⑥"))
    B --> D(("3 ①"))
    B --> E(("8 ④"))
    C --> F(("12 ⑤"))
    C --> G(("20 ⑦"))

Recorre el contorno del árbol partiendo de la raíz por la izquierda: en preorden anotas cada nodo la primera vez que lo tocas por su izquierda; en inorden, cuando lo pasas por debajo (los números del diagrama son el orden inorden); en postorden, la última vez que lo tocas, por su derecha. Con un lápiz y 20 segundos verificas cualquier recorrido.

Recorrido por niveles: la cola entra en escena

Para visitar por niveles (10, luego 6 y 15, luego 3-8-12-20) la recursión no ayuda: la profundidad no es el orden que queremos. La herramienta correcta la construiste en el módulo 4 — una cola FIFO. El algoritmo: encola la raíz; mientras la cola no esté vacía, desencola un nodo, procésalo y encola a sus hijos. Los hijos, al entrar por detrás, esperan su turno a que termine el nivel actual.

from collections import deque      # el deque del módulo 4: O(1) por ambos extremos

def por_niveles(raiz):
    if raiz is None:
        return []
    resultado = []
    cola = deque([raiz])
    while cola:
        nodo = cola.popleft()               # sale el más antiguo (FIFO)
        resultado.append(nodo.valor)
        if nodo.izquierdo:
            cola.append(nodo.izquierdo)     # los hijos, al final de la cola
        if nodo.derecho:
            cola.append(nodo.derecho)
    return resultado

print(por_niveles(raiz))   # [10, 6, 15, 3, 8, 12, 20]

Traza del estado de la cola (izquierda = próximo en salir):

Paso Sale Entra Cola después Resultado
1 10 6, 15 [6, 15] [10]
2 6 3, 8 [15, 3, 8] [10, 6]
3 15 12, 20 [3, 8, 12, 20] [10, 6, 15]
4-7 3, 8, 12, 20 — [] [10, 6, 15, 3, 8, 12, 20]

Y aquí se cierra un círculo pendiente: el ejercicio binarios_hasta(n) del módulo 4 ("1, 10, 11, 100, 101...") hacía exactamente esto — cada cadena binaria s encolaba a sus "hijos" s+'0' y s+'1'; estabas recorriendo por niveles el árbol binario perfecto de todas las cadenas binarias, sin haber visto un árbol todavía. Este recorrido es un BFS con todas las letras; en el módulo 7 lo generalizaremos a grafos, donde necesitará el conjunto visitados que anticipamos en 05-04 (en un árbol no hace falta: sin ciclos y con un solo padre, es imposible encolar dos veces el mismo nodo). Coste: O(n) en tiempo; en memoria, O(anchura máxima) — en un árbol perfecto, el último nivel tiene ≈ n/2 nodos, así que puede ser O(n).

Versiones iterativas con pila explícita

En el módulo 3 aprendiste (con las subtareas anidadas y su RecursionError) que toda recursión puede convertirse en iteración gestionando tú la pila. Con árboles muy profundos — un árbol degenerado de 10 000 nodos supera el límite de recursión de Python — esta conversión pasa de elegancia a necesidad. Preorden iterativo:

def preorden_iterativo(raiz):
    if raiz is None:
        return []
    resultado = []
    pila = [raiz]                      # una lista de Python como pila (módulo 3)
    while pila:
        nodo = pila.pop()              # LIFO: sale el último apilado
        resultado.append(nodo.valor)
        if nodo.derecho:               # ¡derecho PRIMERO!...
            pila.append(nodo.derecho)
        if nodo.izquierdo:             # ...para que el izquierdo quede encima
            pila.append(nodo.izquierdo)
    return resultado

print(preorden_iterativo(raiz))   # [10, 6, 3, 8, 15, 12, 20] — igual que el recursivo

El detalle contraintuitivo: se apila el hijo derecho antes que el izquierdo, porque la pila invierte — el último en entrar es el primero en salir, y queremos procesar antes el izquierdo. Compara con por_niveles: el mismo esqueleto, cambiando la cola por una pila. Esa simetría (cola → por niveles/BFS; pila → en profundidad/DFS) es una de las ideas más bellas del curso y reaparecerá literal en el módulo 7.

El inorden iterativo es más sutil: no puedes procesar un nodo al sacarlo sin más, porque su turno llega después de todo su subárbol izquierdo. La técnica: deslizarse hasta el fondo izquierdo apilando el camino, y al retroceder, procesar y saltar al subárbol derecho.

def inorden_iterativo(raiz):
    resultado = []
    pila = []
    nodo = raiz
    while pila or nodo is not None:
        while nodo is not None:        # 1) bajar por la izquierda apilando el camino
            pila.append(nodo)
            nodo = nodo.izquierdo
        nodo = pila.pop()              # 2) sin más izquierda: toca este nodo
        resultado.append(nodo.valor)
        nodo = nodo.derecho            # 3) y ahora su subárbol derecho
    return resultado

print(inorden_iterativo(raiz))   # [3, 6, 8, 10, 12, 15, 20]

La pila reproduce a mano lo que la pila de llamadas hacía sola: recordar los ancestros pendientes de procesar. (El postorden iterativo es aún más enrevesado — dos pilas o marcado de visitados — y rara vez se necesita; con saber que existe, suficiente.)

Cuándo usar cada recorrido (con TaskFlow como guía)

La regla general: pregúntate qué necesita estar hecho antes de procesar un nodo.

Necesitas... Recorrido Por qué En TaskFlow
Procesar el padre antes que los hijos (crear, copiar, serializar) Preorden El padre debe existir antes de colgar hijos Exportar el árbol de proyectos con indentación
Los valores en orden ascendente (en un ABB) Inorden Izquierda < nodo < derecha (lo probaremos en 06-04) Listado de tareas ordenado por id
Los resultados de los hijos antes de procesar el padre (agregar, liberar, borrar) Postorden El padre resume/depende de sus subárboles Horas acumuladas por proyecto
Procesar por cercanía a la raíz Por niveles La cola garantiza el orden por profundidad Vista "proyectos → categorías → tareas" piso a piso

Otro ejemplo clásico de postorden: borrar un árbol en lenguajes con gestión manual de memoria — hay que liberar los hijos antes que el padre para no perder sus referencias. Y los árboles de expresiones aritméticas dan los tres: preorden = notación prefija, inorden = la notación habitual con paréntesis, postorden = la notación polaca inversa que evaluamos con una pila en el módulo 3.

Dos de los usos de TaskFlow, en código. El preorden que exporta la jerarquía (¡es la función mostrar de 06-01! — procesaba el nodo y luego los hijos: era un preorden sin saberlo) y el postorden que acumula horas:

def horas_acumuladas(nodo):
    """Horas del subárbol: las propias más las de todos los descendientes.
    Cada nodo lleva en valor un dict con al menos {'titulo', 'horas'}."""
    if nodo is None:
        return 0
    total_hijos = sum(horas_acumuladas(h) for h in [nodo.izquierdo, nodo.derecho])
    return nodo.valor["horas"] + total_hijos     # el padre, DESPUÉS de sus hijos

No hay forma de saber cuánto cuesta un proyecto sin sumar antes sus partes: la naturaleza del problema impone postorden. (En 06-08 lo haremos en grande, con presupuestos sobre el árbol genérico.)

Errores Comunes y Consejos

  • Apilar el hijo izquierdo primero en el preorden iterativo. La pila invierte el orden: derecho primero, izquierdo después. Es el despiste número uno; si tu preorden iterativo sale "en espejo", es esto.
  • Usar una pila para el recorrido por niveles (o una cola para DFS). La estructura auxiliar es el recorrido: pila → profundidad, cola → niveles. Si mezclas, obtienes el otro recorrido sin querer.
  • Procesar el nodo en el momento equivocado. Calcular totales acumulados en preorden obliga a contorsiones; en postorden salen solos. Antes de programar, decide qué información debe fluir: de padres a hijos (preorden, como el parámetro profundidad) o de hijos a padres (postorden, como las horas).
  • Confiar en la recursión con árboles de profundidad desconocida. Un árbol degenerado con miles de nodos revienta la pila de llamadas (RecursionError, módulo 3). Para datos de origen externo, la versión iterativa es la defensiva.
  • Consejo: memoriza las salidas de este árbol de ejemplo (pre: raíz primero; in: ordenado; post: raíz al final). Tener un caso resuelto en la cabeza te permite validar cualquier implementación en segundos.

Ejercicios

Ejercicio 1: por niveles, con los niveles separados

Modifica por_niveles para que devuelva una lista de listas, una por nivel: [[10], [6, 15], [3, 8, 12, 20]]. Pista: antes de vaciar cada nivel, len(cola) te dice cuántos nodos lo forman.

Ejercicio 2: profundidad máxima sin recursión

Usando el resultado del ejercicio 1 (o directamente una cola), escribe altura_iterativa(raiz) que calcule la altura del árbol sin recursión. Para el árbol de la lección debe devolver 2.

Ejercicio 3: exportar TaskFlow en preorden iterativo

Sobre el árbol genérico (NodoArbol de 06-01, con lista hijos), escribe exportar(raiz) iterativo con pila explícita que devuelva las líneas indentadas de la jerarquía (como mostrar de 06-01, pero sin recursión y devolviendo una lista). Pista: apila parejas (nodo, profundidad), y apila los hijos en orden inverso para conservar su orden natural.

Soluciones

Solución 1

def niveles_separados(raiz):
    if raiz is None:
        return []
    resultado = []
    cola = deque([raiz])
    while cola:
        tamano_nivel = len(cola)            # todos los que hay AHORA son de este nivel
        nivel = []
        for _ in range(tamano_nivel):
            nodo = cola.popleft()
            nivel.append(nodo.valor)
            if nodo.izquierdo:
                cola.append(nodo.izquierdo)
            if nodo.derecho:
                cola.append(nodo.derecho)
        resultado.append(nivel)
    return resultado

print(niveles_separados(raiz))   # [[10], [6, 15], [3, 8, 12, 20]]

Comentario: la clave es la instantánea tamano_nivel = len(cola) — al empezar cada vuelta del while, la cola contiene exactamente un nivel completo, y el for lo consume mientras encola el siguiente. Sin la instantánea, los hijos recién encolados se mezclarían con el nivel en curso. Este patrón "procesar por tandas" es un clásico de entrevistas.

Solución 2

def altura_iterativa(raiz):
    return len(niveles_separados(raiz)) - 1

print(altura_iterativa(raiz))   # 2

Comentario: la altura es el número de niveles menos 1 (la raíz es el nivel 0), y de paso el árbol vacío devuelve −1, consistente con la convención de 06-02. Sin recursión no hay RecursionError posible: esta versión aguanta el árbol degenerado que tumbaría a la recursiva.

Solución 3

def exportar(raiz):
    if raiz is None:
        return []
    lineas = []
    pila = [(raiz, 0)]                       # pareja (nodo, profundidad)
    while pila:
        nodo, prof = pila.pop()
        if isinstance(nodo.valor, dict):
            etiqueta = f"[{nodo.valor['id']}] {nodo.valor['titulo']}"
        else:
            etiqueta = nodo.valor
        lineas.append("    " * prof + etiqueta)
        for hijo in reversed(nodo.hijos):    # inverso: el primero queda arriba
            pila.append((hijo, prof + 1))
    return lineas

Comentario: dos ideas se combinan. Primera: al no haber pila de llamadas que recuerde la profundidad, viajamos con ella en la tupla — el equivalente manual del parámetro profundidad de 06-01. Segunda: reversed(nodo.hijos) generaliza el truco "derecho antes que izquierdo" a n hijos. El resultado es idéntico línea a línea al de mostrar, pero inmune al RecursionError: TaskFlow ya puede exportar jerarquías de cualquier profundidad.

Conclusión

Ya dominas las cuatro maneras canónicas de visitar un árbol: preorden (el nodo primero — copiar, serializar, exportar), inorden (el nodo en medio — y esa salida ordenada cuyo secreto se revela en la próxima lección), postorden (el nodo al final — agregar y liberar de hijos a padres) y por niveles (la cola del módulo 4 barriendo piso a piso — tu primer BFS, que en el módulo 7 saltará a los grafos). Y sabes bajarlos a tierra con pila explícita cuando la profundidad amenaza a la recursión. Con la estructura (06-02) y los recorridos (06-03) en la mano, llega el momento de la recompensa: añadir al árbol binario una regla de colocación — menores a la izquierda, mayores a la derecha — y ver cómo, de golpe, buscar cuesta O(altura), el inorden regala los datos ordenados y las consultas por rango que el hash no sabía responder ("prioridad entre 1 y 3") por fin tienen dueño. Es el árbol binario de búsqueda, y es la próxima lección.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados