ej2.a.iv

ej2.a.iv

de Bruno Stefano Lombardo Palleiro -
Número de respuestas: 11

Buenas,quería chequear si esta solución es correcta.Gracias

bool esCamino(AB a,Lista l){
    
     if(a==NULL && l==NULL)

           return true;

     else if(a!=NULL && l!=NULL)

       return (a->elem==l->elem) && (esCamino(a->der,l->sig) || esCamino(a->izq,l->sig));

       else

        return false;
}

En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej2.a.iv

de Lucia Thais De Oliveira Gude -
Creo que falta un caso base, en el cual te quedaste sin arbol pero seguis teniendo lista, o al revez, te quedaste sin lista pero todavia queda arbol. Porque el camino tiene que ser desde la punta a una hoja, en esos casos deberias retornar false
En respuesta a Lucia Thais De Oliveira Gude

Re: ej2.a.iv

de Bruno Stefano Lombardo Palleiro -
Entiendo, pero ese caso no estaría contemplado en el último else?
En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej2.a.iv

de Lucia Thais De Oliveira Gude -

No, porque vos en el else comparas elemento con elemento, o sea que ninguno es vacio, y te vas a recursion, pensa que entras de vuelta la funcion y asi sigue hasta llegar un caso base, cuando llegas a un caso base es que tiene un valor y como que ahi podes “volver para atras”, pero tu unico caso base devuelve true.

Por ejemplo un arbol con raiz 5, nodos 3 y 8 Si mi lista es 5 solo, entra al else, llama con lsig que ya es null, pero como el arbol NO es null, entra al else, llamas de vuelta con lsig y te da segmentation fault

En respuesta a Lucia Thais De Oliveira Gude

Re: ej2.a.iv

de Bruno Stefano Lombardo Palleiro -
Claro, entiendo que sólo tengo un caso base , pero no logro ver el segmentation fault que me decís.
En el ejemplo,cuando haces la segunda llamada recursiva ,no iría al último else? Porque la l si es NULL, entonces no se cumple (l!=NULL) y llegaría al else de abajo que da false.
Capaz tendría que poner explicito antes del llamado recursivo la posibilidad que me dijiste en vez de poner un else y false.
Pero no entiendo porque no estaría contemplando ese caso. .
En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej2.a.iv

de Matias Richart -
Hola.

Te falta considerar el caso de que la lista terminó pero en un nodo del árbol que no era una hoja.
Fijate el caso donde por ejemplo la lista termina en un nodo del árbol que solo tiene un subarbol derecho pero no izquierdo.
En ese caso, cuando entres a la recursión para la izquierda, se va a cumplir que a y l son NULL, en tu caso eso devuelve true pero deberías devolver false.

Saludos
En respuesta a Matias Richart

Re: ej2.a.iv

de Bruno Stefano Lombardo Palleiro -
buenas, y como podría corregir eso? porque como mi primer return pegunta si ambos son NULL, me va a devolver true aunque lo verifique después.
tendría que agregarlo como primer caso?
gracias
En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej2.a.iv

de Bruno Stefano Lombardo Palleiro -
Se me ocurrió resolverlo así:
bool esCamino(AB a,Lista l){
if(a==NULL && (l!=NULL) || (a!=NULL && l==NULL) ||( l==NULL && (a->izq!=NULL ||a->der!=NULL)))

return false;

else if(a==NULL && l==NULL)

return true;

else

return (a->elem==l->elem) && (esCamino(a->der,l->sig) || esCamino(a->izq,l->sig));
}
En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej2.a.iv

de Matias Richart -

Hola Bruno.

En tu nueva propuesta cuando a y l son NULL el primer if te va a dar error porque en el tercer or estas accediendo a->izq y a->der.

Te sugiero que lo pienses con una función auxiliar de forma de que el caso de que a y l sean NULL al comienzo lo consideres por fuera de la recursión.

Saludos

En respuesta a Bruno Stefano Lombardo Palleiro

Re: ej2.a.iv

de Amalia Lucia Balestrazzi Silveira -
Buenas,

Yo hice una función parecida, el problema que tenés lo solucioné separando el caso que sería tu else if en 3 subcasos:
Si a->izq != NULL y a->der != NULL, hago eso mismo que hacés vos: return (a->elem==l->elem) && (esCamino(a->der,l->sig) || esCamino(a->izq,l->sig));
Si a->izq == NULL y a->der != NULL devuelvo (a->elem==l->elem) && esCamino(a->der,l->sig) ;
SI a->izq != NULL y a->der == NULL devuelvo (a->elem==l->elem) && esCamino(a->izq,l->sig) ;

De esa manera evito que devuelva true el subarbol vacío.