Ejercicio 2.5

Ejercicio 2.5

de Michel Ezequiel Guerrero Da Silva -
Número de respuestas: 1

Buenas, vi que subieron sus soluciones, pero aun asi queria consultar si la que habia pensado está bien, y si utilice bien el tema del pasaje por referencia:

uint altura(AB a) {

if (a == NULL)

return 0;

else return (1 + max(altura(a->izq), altura(a->der)));

}


Lista insertarAlPrincipio(Lista l, uint elem) {

if (l == NULL) {

l = new nodoLista;

l->elem = elem;

l->sig = NULL

}

else {

Lista pos = new nodoLista;

pos->elem = elem;

pos->sig = l->sig;

l = pos;

};

return l;

}


void caminoMasLargoRec(AB a, Lista &l) {

if (a != NULL) { 

l = insertarAlPrincipio(l, a->elem);

if ((a->izq != NULL) && (a->der != NULL) && (altura(a->izq) >= altura(a->der)))

caminoMasLargoRec(a->izq, l);

else if ((a->izq != NULL) && (a->der != NULL) && (altura(a->izq) < altura(a->der))) 

caminoMasLargoRec(a->der);

else if (a->izq != NULL)

caminoMasLargoRec(a->izq);

else if (a->der != NULL)

caminoMasLargoRec(a->der);

};

}


Lista caminoMasLargo(AB a) {

if (a == NULL)

return NULL;

else {

Lista l;

caminoMasLargoRec(a, l);

l = insertarAlPrincipio(l, a->elem); //inserto el elemnto de la raiz de a que me quedó pendiente

return l;

}

}

En respuesta a Michel Ezequiel Guerrero Da Silva

Re: Ejercicio 2.5

de Sofia Tito Virgilio Rodriguez -

Hola Michel,

Tu solución resuelve el problema. Y además el pasaje por referencia se utiliza correctamente. Pero tiene algunos detalles.

Algunos detalles que yo encontré serían:

  • El if(a!=NULL) de caminoMasLargoRec es innecesario porque si te fijas, implícitamente tomaste como precondición que el parámetro de entrada sea distinto de NULL, ya que siempre veríficas que el árbol sea distinto de NULL antes de invocar a la función con dicho árbol, así que nunca la vas a invocar con un árbol que sea NULL. (La otra opción sería evitar las verificaciones previas a la invocación y considerar el caso a == NULL dentro de la función)
  • Al insertar al principio en la lista estarías obteniendo el camino más largo en el orden desde las hojas a la raíz, capaz que sería más natural que los elementos en la lista quedaran guardados desde la raiz a las hojas, es decir, que la raiz sea el primer elemento de la lista, y la hoja del camino más largo el último (esto se puede lograr insertando al final en lugar de al principio)
  • Estás insertando la raiz dos veces, no es necesario que lo hagas en caminoMasLargo, porque si te fijas, es lo primero que haces en caminoMasLargoRec, ¿se ve esto?
  • Finalmente, en varias llamadas recursivas te olvidaste de pasar l como parámetro!

Luego, hay que tener en cuenta que puede ser un poco ineficiente invocar a altura en cada llamada recursiva, ya que se están recorriendo nodos del árbol reiteradas veces, eso es lo que se busca optimizar un poco más en la solución que nosotros planteamos.

Cualquier cosa que genere dudas volvé a consultar,

Saludos!