Ejercicio 9

Re: Ejercicio 9

de Fernando Fernandez -
Número de respuestas: 0

Primero pensemos en el problema en sí y todavía no en la implementación.

Un árbol puede ser vacío. En ese caso la amplitud es 0 ya que no hay nodos. Tenemos resuelto el caso base.

Si no es vacío el árbol consiste en la raíz y una colección de subárboles. Asumimos que, dado que son más chicos, supimos calcular la amplitud de cada uno de los subárboles. ¿Qué nos falta para resolver el problema? Vamos a necesitar calcular la cantidad de hijos de la raíz. Supongamos que implementamos una función que obtiene esto. Entonces, la amplitud del árbol es lo que sea mayor entre la cantidad de hijos de la raíz, que sabemos calcular mediante la función recién mencionada, o la mayor de las amplitudes de  los subárboles, que ya habíamos calculado de manera recursiva.

Lo que nos está faltando es saber como aplicar la recursión a cada uno de los subárboles.

Acá hacemos lo que es habitual cuando tratamos con árboles finitarios, que es generalizar el problema y resolverlo para una colección de subárboles (un bosque). Ahora queremos calcular la amplitud de un bosque. Si podemos calcular esto tenemos resuelto el problema: la amplitud del árbol no vacío es el máximo entre la cantidad de hijos de la raíz y la amplitud del bosque de subárboles. 

La amplitud de un bosque es la mayor de las amplitudes de cada uno de sus árboles. Si el bosque es vacío la amplitud es 0. Si no, la amplitud es el máximo entre la amplitud del primer árbol y la amplitud del resto del bosque.

Y ahora usamos la representación de árboles finitarios mediante árboles binarios con semántica primer hijo, siguiente hermano. Esta parte es la que falta hacer. Y van a ser unas pocas líneas para calcular la cantidad de hijos (o tal vez la cantidad de hermanos) y otras pocas líneas para completar la función.

Esta explicación ha sido bastante larga. Después que tenés un poco de práctica con este tipo de problemas los primeros párrafos se piensan de manera automática. Lo decisivo es pensar en resolver los problemas en su generalización para bosques.