Cerramos el módulo 5 con una confesión: el hash es imbatible cuando le das una clave exacta, pero enmudece ante preguntas como "dame las tareas ordenadas por id" o "todas las de prioridad entre 1 y 3". Sus claves están esparcidas a propósito, sin noción de vecindad ni de orden. Para responder a eso necesitamos una estructura que mantenga los datos organizados, y esa estructura es el árbol. En esta lección aprenderás qué es un árbol, dominarás su vocabulario (raíz, hoja, altura, profundidad...), construirás la clase NodoArbol para árboles genéricos y la usarás para modelar algo que TaskFlow pedía a gritos: la jerarquía proyectos → categorías → tareas → subtareas. Todo lo que viene en este módulo — árboles binarios, ABB, AVL, árboles B, montículos — se apoya en el vocabulario y la intuición de esta lección.

1. Del hash al árbol: por qué necesitamos jerarquía y orden
2. Qué es un árbol: definición y propiedades
3. Terminología: el vocabulario que usaremos todo el módulo
4. Árboles genéricos en Python: la clase NodoArbol
5. TaskFlow jerárquico: proyectos, categorías, tareas y subtareas
6. Recorrer un árbol genérico con recursión
7. Árboles en la vida real

Repasemos qué sabe hacer cada estructura que ya tienes en TaskFlow:

Las tres últimas filas comparten algo: piden relaciones entre elementos (orden, rango, pertenencia jerárquica), no un elemento aislado. Todas las estructuras que conoces hasta ahora son lineales: cada elemento tiene, como mucho, un anterior y un siguiente. Los árboles rompen esa linealidad: un elemento puede tener varios siguientes. Esa pequeña diferencia lo cambia todo.

Este módulo atacará las tres carencias por orden: la jerarquía hoy mismo (árboles genéricos), el orden y los rangos en 06-04 (árboles binarios de búsqueda), y de paso saldaremos en 06-07 la promesa del módulo 4: abrir heapq por dentro.

Un árbol es una estructura de datos jerárquica formada por nodos conectados por aristas, que cumple tres propiedades:

• Hay exactamente un nodo raíz, que no tiene padre.
• Todo nodo que no es la raíz tiene exactamente un padre.
• No hay ciclos: siguiendo aristas nunca vuelves a un nodo ya visitado.

Consecuencia útil: un árbol con n nodos tiene exactamente n - 1 aristas (cada nodo salvo la raíz aporta la arista que lo une a su padre). Y entre la raíz y cualquier nodo existe un único camino — no hay rutas alternativas.

Un apunte que retomaremos en el módulo 7: formalmente, un árbol es un caso particular de grafo (conexo y sin ciclos). Lo dejamos aquí como mención; en los grafos generales un nodo podrá tener varios "padres" y habrá ciclos, y eso exigirá técnicas nuevas.

Fíjate en que los árboles en informática se dibujan al revés que los botánicos: la raíz arriba y las hojas abajo. Es pura convención, pero es universal.

Este vocabulario aparecerá en las siete lecciones siguientes; merece la pena fijarlo bien. Sobre el diagrama anterior:

Dos matices que causan confusión a todo el mundo al principio:

• Profundidad se mide desde la raíz hacia abajo (es propia de cada nodo); altura se mide desde las hojas hacia arriba (la altura de un nodo es la del camino más largo hasta una hoja bajo él; la del árbol es la altura de la raíz). La raíz tiene profundidad 0 y altura máxima; una hoja tiene altura 0 y profundidad variable.
• La palabra subárbol es la clave de la recursión: cada hijo de un nodo es, a su vez, la raíz de un árbol completo. Un árbol es "un nodo + una lista de árboles más pequeños". Esa definición recursiva es la que hace que casi todos los algoritmos de este módulo sean recursivos de forma natural — la recursión del módulo 3 va a trabajar duro aquí.

En un árbol genérico (o n-ario) cada nodo puede tener cualquier número de hijos. La implementación natural: un valor y una lista de hijos. Compárala con el Nodo del módulo 2 — allí siguiente era una referencia; aquí hijos es una lista de referencias. Ese es todo el salto de lo lineal a lo jerárquico.

Punto por punto:

• valor puede ser cualquier cosa: en TaskFlow será a veces un texto (nombre de proyecto o categoría) y a veces el dict de una tarea.
• hijos empieza como lista vacía: todo nodo nace hoja y deja de serlo al recibir hijos.
• agregar_hijo devuelve el hijo añadido: así podemos escribir backend = proyecto.agregar_hijo(NodoArbol("Backend")) y seguir colgando cosas de backend.
• No hay clase "Árbol" envolvente: basta con guardar la raíz. Desde ella se alcanza todo, igual que desde self.cabeza se alcanzaba toda la ListaEnlazada.

Hasta hoy, TaskFlow guardaba las tareas en estructuras planas: una lista enlazada, una cola, una tabla hash. Pero cualquier usuario real organiza su trabajo en niveles: proyectos que contienen categorías, que contienen tareas, que a su vez tienen subtareas (¿recuerdas las subtareas anidadas del módulo 3, que nos provocaron un RecursionError? Eran un árbol pidiendo permiso para existir). Construyámoslo:

Observa la elegancia: no hemos escrito ni una línea nueva de estructura para pasar de 2 a 4 niveles. La lista de hijos no distingue entre "proyecto que contiene categorías" y "tarea que contiene subtareas"; la jerarquía puede crecer tan honda como el usuario quiera.

¿De qué sirve el árbol si no podemos consultarlo? Los recorridos sistemáticos (con nombre, orden garantizado y versión iterativa) son el tema de 06-03; aquí veremos el patrón básico del que derivan todos: procesar el nodo y recursar sobre cada hijo. Primero, contar nodos:

Lee la función a la luz de la definición recursiva de árbol: "el tamaño de un árbol es 1 (su raíz) más la suma de los tamaños de sus subárboles". El caso base (None → 0) y las llamadas sobre estructuras estrictamente más pequeñas garantizan que termina — exactamente los dos requisitos que estudiamos en el módulo 3. Como no hay ciclos y cada nodo tiene un solo padre, cada nodo se visita exactamente una vez: coste O(n).

Ahora algo más vistoso: imprimir el árbol con indentación, como hace tree en la terminal. La profundidad de cada nodo se convierte en sangría:

Salida:

El parámetro profundidad viaja en cada llamada recursiva incrementado en 1: es la traducción directa de la definición "profundidad = nº de aristas desde la raíz". Y una nota de honestidad que ya conoces del módulo 3: si el árbol fuera absurdamente profundo (miles de niveles), la pila de llamadas de Python protestaría con RecursionError; allí aprendimos a convertir la recursión en iteración con una pila explícita, y en 06-03 aplicaremos esa técnica a los recorridos.

Los árboles no son un invento académico; probablemente uses varios cada minuto:

• El sistema de ficheros: /home/joan/proyectos/taskflow/main.py es un camino raíz→hoja. Las carpetas son nodos internos, los ficheros son hojas, y tree es nuestra función mostrar.
• El DOM de una página web: <html> es la raíz, y cada etiqueta anidada un hijo. Cuando JavaScript hace element.children está leyendo una lista hijos como la nuestra.
• Organigramas: la dirección general como raíz, departamentos como subárboles. "¿Cuánta gente depende (directa o indirectamente) de X?" es contar_nodos(X) - 1.
• Menús y categorías de cualquier aplicación o tienda online — exactamente nuestro TaskFlow jerárquico.
• Sintaxis de los lenguajes: el propio intérprete de Python convierte tu código en un árbol (AST) antes de ejecutarlo.

Cuando en tu trabajo veas datos con relación "contiene a" o "depende de un único superior", piensa en árbol.

• Confundir altura y profundidad. Regla nemotécnica: la profundidad se mide desde la raíz (¿a cuántos pisos bajo la superficie estás?); la altura desde las hojas (¿cuánto mides desde el suelo?). En entrevistas se pregunta constantemente.
• Olvidar el caso base en las funciones recursivas. Sin el if nodo is None: return 0, llamar a contar_nodos(None) (por ejemplo, sobre un árbol vacío) explota con AttributeError. Todo algoritmo de árboles debe decidir qué hacer con el árbol vacío.
• Crear ciclos por accidente. Si añades un nodo como hijo de uno de sus propios descendientes, ya no tienes un árbol: los recorridos recursivos no terminarán nunca. Las estructuras con ciclos legítimos existen — son los grafos del módulo 7 — pero requieren otras técnicas.
• Compartir la lista de hijos entre nodos. Un clásico de Python: definir def __init__(self, valor, hijos=[]) con lista mutable por defecto hace que todos los nodos compartan la misma lista. Inicializa siempre self.hijos = [] dentro del __init__.
• Consejo: guarda siempre una referencia a la raíz en una variable estable. Perder la raíz de un árbol es perder el árbol entero, igual que perder cabeza en la lista enlazada.

Escribe contar_tareas(nodo) que devuelva cuántos nodos del subárbol contienen una tarea (es decir, cuyo valor es un dict), ignorando proyectos y categorías. Sobre el árbol de la lección debe devolver 5.

Escribe profundidad_de(nodo, id_buscado) que devuelva la profundidad a la que está la tarea con ese id (la raíz tiene profundidad 0), o None si no existe. profundidad_de(raiz, "T-01a") debe devolver 4.

Escribe hojas(nodo) que devuelva la lista de valores de todas las hojas del subárbol. En el árbol de la lección, Proyecto: App móvil es hoja (no tiene contenido aún) y también lo son las tareas sin subtareas.

Solución 1

Comentario: es contar_nodos con el "1" condicionado. La estructura del recorrido no cambia — cambia qué hacemos en cada nodo. Este patrón (recorrido fijo, acción variable) se repetirá todo el módulo.

Solución 2

Comentario: el detalle importante es el if resultado is not None: return resultado — en cuanto un subárbol encuentra la tarea, dejamos de explorar los hermanos. Sin él, la función seguiría buscando y devolvería None aunque hubiera encontrado el objetivo antes. Fíjate también en que buscar en un árbol genérico es O(n): sin ninguna regla sobre dónde está cada valor, hay que mirar potencialmente todos los nodos. En 06-04 añadiremos esa regla y la búsqueda bajará a O(altura).

Solución 3

Comentario: aquí el caso base útil no es None sino es_hoja(): una hoja se devuelve a sí misma; un nodo interno delega y concatena. Que Proyecto: App móvil aparezca entre las hojas es correcto y revelador: "hoja" es una propiedad estructural (no tener hijos), no semántica (ser una tarea).

Ya tienes el vocabulario (raíz, hoja, padre, subárbol, altura, profundidad, nivel) y la herramienta (NodoArbol con su lista de hijos) que sostendrán todo el módulo, y TaskFlow ha ganado por fin su jerarquía de proyectos → categorías → tareas → subtareas — con recorridos recursivos que reutilizan lo aprendido en el módulo 3. Pero fíjate en la solución del ejercicio 2: buscar en este árbol sigue costando O(n), y las preguntas de orden y rango que dejó pendientes el hash siguen sin respuesta. El camino hacia ella empieza restringiendo el árbol: si cada nodo tiene como máximo dos hijos, con posición distinguida (izquierdo y derecho), aparecen propiedades matemáticas potentísimas — y sobre ellas construiremos la búsqueda en O(log n). Ese árbol restringido es el árbol binario, protagonista de la siguiente lección.