Comprender cómo se recorre un árbol y cómo se mide su profundidad es fundamental para resolver problemas algorítmicos con estructuras jerárquicas. Estos conceptos permiten procesar datos de forma ordenada y eficiente, tanto en árboles binarios como en árboles con múltiples hijos.
¿Qué significa recorrer un árbol en diferentes órdenes?
Cuando tenemos un árbol —por ejemplo, un árbol binario con un nodo actual (A), un hijo izquierdo (I) y un hijo derecho (D)— podemos visitarlo de distintas maneras según el orden en que procesamos cada nodo. Existen tres órdenes clásicos que determinan cuándo se visita el nodo actual en relación con sus hijos [0:30].
¿Cómo funciona el recorrido inorder?
En el recorrido inorder, el orden de visita es:
- Primero se recorre el hijo izquierdo.
- Luego se procesa el nodo actual.
- Finalmente se recorre el hijo derecho.
Este patrón resulta especialmente útil en árboles binarios de búsqueda, donde produce una secuencia ordenada de valores.
¿Qué cambia en preorder y postorder?
El recorrido preorder [1:12] coloca al nodo actual antes que sus hijos: primero se procesa el nodo actual, después el hijo izquierdo y por último el hijo derecho. La palabra "pre" indica que el nodo va primero. En un árbol eneario (con más de dos hijos), el esquema es el mismo: primero el nodo actual y después se itera por todos los hijos en un ciclo.
El recorrido postorder [1:55] invierte la prioridad: primero se atienden los hijos (izquierdo y luego derecho) y al final se procesa el nodo actual. "Post" significa que el nodo se visita después de sus descendientes.
¿Qué es la profundidad de un árbol y cómo se calcula?
La profundidad de un árbol mide la cantidad de nodos o niveles en un camino desde la raíz hasta una hoja [2:18]. Las hojas son los nodos que se encuentran en la parte más baja del árbol, sin hijos.
- La profundidad mínima es el camino más corto desde la raíz hasta la hoja más cercana.
- La profundidad máxima (también llamada diámetro) es el camino más largo desde la raíz hasta la hoja más lejana.
Por ejemplo, en un árbol donde una rama alcanza dos niveles y otra alcanza cuatro, la profundidad mínima es dos y la máxima es cuatro [2:45].
¿Cómo se implementa el cálculo de profundidad con recursión?
El algoritmo recursivo para calcular la profundidad recibe una raíz como entrada [3:05]. El caso base se cumple cuando la raíz es nula, es decir, cuando ya no existe un nodo por visitar.
El proceso funciona así:
- Se llama recursivamente a la función para el hijo izquierdo y se guarda el resultado.
- Se llama recursivamente para el hijo derecho y se guarda en otra variable.
- Si no existe hijo izquierdo, se retorna el valor del derecho más uno.
- Si no existe hijo derecho, se retorna el valor del izquierdo más uno.
- Si ambos existen, se retorna el mínimo entre los dos caminos más uno para la profundidad mínima.
Para obtener la profundidad máxima, el único cambio es usar max en lugar de min al comparar los dos caminos [4:15].
¿Qué cambia en un árbol eneario?
Cuando el árbol no es binario sino eneario [4:30], no se revisan solo izquierda y derecha. En su lugar, se itera por todos los hijos con un ciclo. Se mantiene una variable maxima_profundidad (o mínima, según el caso) que se actualiza cada vez que se encuentra un camino mayor al almacenado previamente.
python
def profundidad(raiz):
if raiz is None:
return 0
max_prof = 0
for hijo in raiz.hijos:
max_prof = max(max_prof, profundidad(hijo))
return max_prof + 1
La lógica es idéntica a la del árbol binario: la diferencia radica en recorrer un grupo de hijos en vez de solo dos referencias fijas.
Con estos fundamentos claros —inorder, preorder, postorder y el cálculo de profundidad— ya cuentas con las herramientas necesarias para abordar problemas prácticos como Sum root to leaf numbers. ¿Qué tipo de recorrido usarías tú para resolver ese reto? Comparte tu enfoque en los comentarios.
