Skip to content

Tema 5: Estructuras de Datos Jerárquicas (Árboles)

📝 Resumen Ejecutivo

Esta sesión marca la transición de estructuras lineales (pilas/colas) a estructuras jerárquicas (árboles), donde los elementos tienen relaciones múltiples "padre-hijo". Se definen las métricas fundamentales para analizar árboles (altura, profundidad, grado) y se introducen los algoritmos recursivos de recorrido: Preorden, Inorden y Postorden, esenciales para operaciones como el clonado o la búsqueda ordenada.

🗝️ Conceptos Clave

  • Stack (Pila): Clase de Java (java.util) que hereda de Vector (LIFO).
  • Queue (Cola): Interfaz en Java (FIFO), no una clase instanciable directamente.
  • Árbol: Estructura no lineal de nodos interconectados jerárquicamente.
  • Altura de un nodo: Longitud del camino más largo desde el nodo hasta una hoja.
  • Profundidad: Longitud del camino desde la raíz hasta el nodo.
  • Recorridos (Traversals): Métodos sistemáticos para visitar todos los nodos (Preorden, Inorden, Postorden).

📚 Desarrollo del Temario

1. Repaso y Contexto: Stack y Queue en Java

Antes de entrar en árboles, es vital entender las herramientas que Java ofrece para estructuras lineales, aunque ¡OJO AL DATO!: Para las actividades de la asignatura debéis implementarlas manualmente, no usar estas librerías directamente.

  • Stack (Pila):
    • Es una Clase ya implementada que pertenece a java.util.
    • Hereda de Vector, lo que implica que es una colección dinámica basada en arrays.
    • Métodos listos para usar: push(), pop(), peek().
  • Queue (Cola):
    • Es una Interfaz, no una clase. Define el contrato de comportamiento FIFO.
    • No se puede instanciar directamente (new Queue() daría error). Requiere clases que la implementen como LinkedList o PriorityQueue.

2. Estructuras Lineales vs. Jerárquicas

El cambio de paradigma es fundamental para entender la complejidad algorítmica.

Característica Estructuras Lineales Estructuras Jerárquicas
Organización Secuencial (uno detrás de otro). No lineal (múltiples relaciones/conexiones).
Tipos Listas, Pilas, Colas. Árboles, Grafos.
Ejemplos Reales Historial de navegador (Pilas), Cola de impresión o panadería (Colas). Sistema de archivos (carpetas), DOM de una web (HTML), Árboles de decisión.

Ejemplo del Profesor: "Imagina un sistema de archivos. Tienes una carpeta raíz, de ella cuelga 'Primero' y 'Segundo', y de 'Primero' cuelgan 'Bases de Datos' y 'Cálculo'. Visualmente, eso es un árbol.".

3. El TAD Árbol (Conceptos Básicos)

Un árbol se define como una estructura jerárquica de interconexión de nodos en forma "padre-hijo".

Terminología Anatómica

  • Nodo: Cada elemento individual del árbol (ej. 5, 3, 7).
  • Padre: Antecesor directo. (7 es padre de 2) .
  • Hijo: Descendiente directo. (2 es hijo de 7) .
  • Raíz: El nodo superior único sin padre (antecesor común de todos).
  • Hoja (Nodo Terminal): Nodo sin hijos (las "puntas" del árbol).
  • Subárbol: Árbol formado por un nodo y sus descendientes, contenido en el árbol principal.

4. Características Computables (Métricas)

Es crucial distinguir entre altura y profundidad, ya que suelen confundirse en los exámenes.

A. Camino y Longitud

  • Camino: Secuencia de nodos conectados (\(n_1, n_2... n_k\)) donde cada uno es padre del siguiente.
  • Longitud del camino: Número de nodos menos 1 (es decir, el número de "aristas" o líneas que los unen).
    • Ejemplo: Camino 5-7-1-4 (4 nodos) Longitud = 3.

B. Altura (Height) vs. Profundidad (Depth)

  • Altura de un nodo: Longitud del camino más largo desde ese nodo hasta una hoja.
    • Cálculo: Miras todos los caminos posibles hacia abajo y te quedas con el mayor.
    • Altura del árbol: Es la altura del nodo raíz.
  • Profundidad (Nivel): Longitud del camino desde la raíz hasta el nodo.
    • Raíz = Profundidad 0. Hijos de raíz = Profundidad 1.

C. Grado

  • Grado de un nodo: Número de hijos directos que tiene.
    • Las hojas siempre tienen grado 0.
  • Grado del árbol: El máximo de los grados de todos sus nodos.
  • Clasificación:
    • Árbol N-ario: Grado N.
    • Árbol Binario: Grado 2 (máximo 2 hijos por nodo).

5. Recorridos (Traversals)

Recorrer un árbol significa visitar todos sus nodos en una secuencia sistemática. La clave aquí es la recursividad.

A. Preorden (Preorder)

Orden: Raíz Izquierda Derecha. 1. Procesar (visitar) la Raíz. 2. Recorrer recursivamente el Subárbol Izquierdo. 3. Recorrer recursivamente el Subárbol Derecho.

  • Aplicación: Muy útil para clonar árboles, ya que visitas el nodo antes de intentar crear sus hijos.

B. Inorden (Inorder)

Orden: Izquierda Raíz Derecha. 1. Recorrer recursivamente el Subárbol Izquierdo. 2. Procesar la Raíz. 3. Recorrer recursivamente el Subárbol Derecho.

  • ¡OJO AL DATO!: En los Árboles Binarios de Búsqueda (BST), el recorrido inorden devuelve los valores ordenados ascendentemente (de menor a mayor).

C. Postorden (Postorder)

Orden: Izquierda Derecha Raíz. 1. Recorrer recursivamente el Subárbol Izquierdo. 2. Recorrer recursivamente el Subárbol Derecho. 3. Procesar la Raíz.

  • Aplicación: Fundamental para eliminar nodos/borrar el árbol. Debes eliminar (o liberar memoria de) los hijos antes de eliminar al padre.

6. Lógica de Implementación (Recursividad)

El profesor enfatizó la lógica de inserción en un Árbol Binario de Búsqueda (BST). Aunque el código no estaba en las diapositivas, es vital para la práctica.

Regla del BST: * Menores a la izquierda. * Mayores a la derecha. * Sin duplicados (generalmente).

Algoritmo de Inserción Recursiva (Pseudo-código verbal): 1. Caso Base: Si el hueco está vacío (null), crea el nuevo nodo ahí. 2. Caso Recursivo: * Si valor_nuevo < valor_actual: Llama a insertar en el hijo izquierdo. * Si valor_nuevo > valor_actual: Llama a insertar en el hijo derecho. * Si son iguales: No haces nada (o actualizas), porque no suele admitir repetidos.

Cita del Profesor: "Por eso se utiliza la recursión, porque estás llamando a insertar en distintas posiciones. Primero lo llamas desde la raíz, si está ocupado, rotas el puntero a la izquierda o derecha y vuelves a llamar a la función insertar como si ese nodo fuera la nueva raíz."

🧠 Preguntas de Autoevaluación

  1. Diferencia conceptual: ¿Por qué Stack en Java se considera una "clase" y Queue una "interfaz"? ¿Qué implica esto al instanciarlas?
  2. Cálculo: Si tienes un camino de 5 nodos (A-B-C-D-E), ¿cuál es la longitud de ese camino? (Respuesta: 4).
  3. Análisis: Si realizas un recorrido Inorden en un Árbol Binario de Búsqueda (BST), ¿en qué orden obtendrás los datos?
  4. Métrica: ¿Cuál es la altura de un nodo hoja? ¿Y su grado?
  5. Aplicación: Si necesitas programar una función para borrar un árbol completo de la memoria, ¿qué recorrido (Pre, In, Post) usarías y por qué?