Primer parcial 2019 - Problema 3.a

Primer parcial 2019 - Problema 3.a

de Daniel Ezequiel Diniz Figueredo -
Número de respuestas: 3

Buenas. 

No logro  entender del todo la solución mostrada para con el problema en cuestión.

Sea la misma:


Mi problema radica en imaginarme un caso borde: una lista encadenada.
En tal caso, ¿por qué la función retornaría uno? ¿No debería de retornar la altura del nodo "más a la derecha", o "a la izquierda"? (Suponiendo un largo arbitrario mayor que uno)

Quizá estoy entendiendo mal algo relacionado con la letra, y todo esto es un mal entendido. Pero, no me termina de cerrar la idea.

Si es que se nota en donde falla mi razonamiento, agradecería enormemente que se me guiara, constructivamente, a alguna forma correcta de pensar el mismo.

Desde ya, muchas gracias por su tiempo, y sépase disculpar las molestias ocasionadas. 

Saludos,
Daniel

En respuesta a Daniel Ezequiel Diniz Figueredo

Re: Primer parcial 2019 - Problema 3.a

de Daniel Ezequiel Diniz Figueredo -
Nótese que con "más a la derecha" y/o "a la izquierda" hago referencia a la hoja del árbol.

Con respecto a esto, entiendo que una hoja es, de por sí, un árbol perfecto. Espero se me corrija en caso contrario.

Saludos,
Daniel
En respuesta a Daniel Ezequiel Diniz Figueredo

Re: Primer parcial 2019 - Problema 3.a

de Nestor Rocchetti -
Buenos días Daniel,

Muchas gracias por tu planteo. 

Según la letra del parcial, un árbol perfecto cumple que cada nodo que no es hoja tiene un hijo izquierdo y uno derecho. Entonces, para calcular la altura mínima de un árbol binario subyacente con estas características y cuya raíz es la misma raíz del árbol original, se necesita implementar un algoritmo recursivo del estilo del que se plantea en la solución. 
En el algoritmo planteado se comprueba la altura del árbol perfecto en post-orden y se realiza de la siguiente manera: la altura del árbol binario es 1 más la menor de las alturas de los subárboles izquierdo y derecho, que en el código se ve como "1 + ( ( hizq <= hder ) ?hizq : hder". 
En el caso de una lista encadenada (o sea cuando uno de los hijos queda indefinido para todos los nodos del árbol), evaluar la condición anterior da como resultado 1 ya que el nodo raíz no tiene definido uno de los dos hijos.

Saludos, 
Néstor