GUÍA 28-10-26 Estructuras de Datos

CN122 · miércoles 28/10/2026 · 13:00-14:15 · Sesión 23

Árboles generales · Terminología y representación

DEFINICIÓN

Un árbol es un grafo conexo sin ciclos con un nodo distinguido como raíz. Equivalentemente: entre cualesquiera dos nodos existe exactamente un camino.

TERMINOLOGÍA

• Raíz — el nodo sin padre. Hoja — nodo sin hijos.
• Grado de un nodo — número de hijos. Grado del árbol — el máximo.
• Nivel — distancia desde la raíz, que se cuenta desde 0.
• Altura — el nivel máximo. Un árbol de un solo nodo tiene altura 0.
• Subárbol — cualquier nodo con todos sus descendientes.

REPRESENTACIÓN HIJO-IZQUIERDO HERMANO-DERECHO

Un nodo con número arbitrario de hijos se representa con solo dos apuntadores: uno al primer hijo y otro al siguiente hermano. Así cualquier árbol general se convierte en uno binario.

• typedef struct Nodo { int dato; struct Nodo *hijo, *hermano; } Nodo;

Es un resultado importante: basta estudiar árboles binarios para cubrir todos los árboles. Por eso el resto del curso se concentra en ellos.

RECORRIDOS GENERALES

• En profundidad, con recursión o pila.
• Por niveles, con cola: es un BFS sobre el árbol.

APLICACIONES

• Sistemas de archivos: directorios y archivos.
• Árbol sintáctico de un compilador.
• DOM de una página web.
• Jerarquías organizacionales y taxonomías.

PRÁCTICA

Representar un sistema de archivos con hijo-hermano; calcular altura, contar hojas y listar por niveles.