Un árbol en programación es una estructura de datos no lineal que organiza información de forma jerárquica, como si fuera un árbol genealógico o un organigrama empresarial. Entender qué es un árbol, cómo se compone y qué propiedades tiene te servirá para resolver problemas algorítmicos donde la jerarquía importa.

¿Qué es un árbol y por qué es un tipo de grafo?

Un árbol es un caso especial de grafo. La diferencia es que tiene un punto de entrada único llamado raíz, desde donde se desprenden los demás nodos siguiendo una dirección clara.

Piensa en una empresa: arriba hay un jefe, debajo sus empleados directos y, debajo de ellos, más personas a su cargo. Esa misma lógica de jerarquía es la que modelamos cuando trabajamos con árboles en estructuras de datos.

¿Qué diferencia hay entre un árbol y un grafo? Un árbol es un grafo con un nodo raíz y dirección jerárquica, sin ciclos. Cualquier grafo puede tener múltiples puntos de entrada y conexiones libres.

¿Cómo se estructuran los nodos padres e hijos?

La terminología de los árboles toma prestado el lenguaje familiar. Cada nodo puede tener hijos, y cuando hablamos de los nodos que están más arriba en la estructura los llamamos ancestros, igual que en un árbol genealógico.

Desde el nodo raíz se desprenden los hijos izquierdo y derecho, y cada uno de esos hijos puede convertirse a su vez en padre de nuevos nodos. Así se construye la jerarquía completa.

¿Qué es un árbol binario y un árbol n-ario?

Un árbol binario es aquel donde cualquier nodo tiene a lo sumo dos hijos: uno a la izquierda y otro a la derecha. Es la forma más común que verás en ejercicios de algoritmos.

Pero no toda jerarquía se modela con dos hijos. Cuando un nodo puede tener N cantidad de hijos hablamos de un árbol n-ario. Por ejemplo, si modelas una empresa donde un líder puede tener tres personas a cargo, ese sería un árbol n-ario de grado tres.

Lo que nunca cambia es que un árbol tiene una sola cabeza: un único nodo raíz desde el que parte toda la estructura.

¿Cuáles son las propiedades clave de un árbol?

Antes de resolver problemas con árboles necesitas dominar la notación. Estos son los conceptos que aparecerán una y otra vez en algoritmos.

¿Qué son los niveles y la altura de un árbol?

Cada nivel de un árbol es una generación de nodos. La raíz está en el nivel uno, sus hijos en el nivel dos, los nietos en el nivel tres, y así sucesivamente.

La altura de un árbol se define por la cantidad de niveles que tiene. Si tu árbol tiene tres niveles, su altura es tres. Algunos textos también usan la palabra generación para referirse a este mismo concepto.

¿Cómo se calcula la altura de un árbol? Cuenta el número de niveles desde la raíz hasta el nodo hoja más profundo. Si hay tres niveles, la altura es tres.

¿Qué diferencia un árbol lleno de uno no lleno?

Un árbol lleno es aquel donde todos los nodos, excepto las hojas, tienen la cantidad máxima de hijos posibles. En un árbol binario lleno, cada padre tiene exactamente dos hijos.

Un árbol no lleno, en cambio, tiene al menos un nodo padre con menos hijos de los que podría tener. Si un nodo de un árbol binario solo tiene un hijo en lugar de dos, el árbol ya no está lleno.

¿Qué son los nodos hoja?

Los nodos hoja son los últimos nodos de cada camino, los que ya no tienen hijos. Son los extremos finales de la estructura, donde termina la jerarquía.

En cualquier árbol vas a tener varios nodos hoja, uno por cada rama que llega a su fin.

¿Qué son el orden y el grado de un árbol?

Aquí hay una distinción sutil pero importante que conviene tener clara.

• Orden: la cantidad máxima de hijos que un nodo puede tener según la definición del árbol. En un árbol binario el orden es dos. En un n-ario donde permites hasta tres hijos, el orden es tres.
• Grado: la cantidad máxima de hijos que un nodo realmente tiene en tu árbol concreto. Si definiste un árbol con orden tres pero ningún nodo llega a tener tres hijos, el grado podría ser dos.

La diferencia se nota cuando defines la estructura teórica frente a lo que efectivamente construiste con tus datos.

Dominar estos conceptos (raíz, padres, hijos, ancestros, hojas, niveles, altura, árbol lleno, orden y grado) te prepara para el siguiente paso: aplicar recursión, una técnica fundamental no solo para árboles y grafos, sino para la programación en general.

¿Qué jerarquía de tu día a día modelarías como árbol? Cuéntame en los comentarios cómo la estructurarías.