Ej 5.4 y 5.5

Ej 5.4 y 5.5

de Fabricio Gabriel Techera Rosado -
Número de respuestas: 5

para el 4.4 me hice un procedimiento recursivo, lo llame borrarRec, y arranca con un if( a != NULL) y todo lo demas esta adentro, entonces si es NULL no hace nada, queria saber si eso era correcto. en la funcion borrar directamente puse la condicion que debia cumpliar y si las cumplia invocaba el procedimiento borrarRec(AG a&, int x)


para el 4.5 fue un poco mas complicado, hice otro procedimiento llamado eliminarArbol(AG a&, int x) que elimina hoja por hoja el arbol y termina por eliminar la raiz y dejando el puntero apuntando a NULL.

el problema mas grande fue hallar el x para borrarsub, ya que a diferencia de borrar debia de evaluar si este tenia hijo y borrar todo el hijo. para eso use la funcion del video 4, buscar, e hice una funcion mas llamada anterior, que me da el puntero anterior a uno que pertenezca al arbol y es de la siguiente manera.

AG anterior(AG a, AG b)

{

if (a == NULL)

return NULL;

else if(a->sH == b || a->Ph == b)

return a;

else

{

AG Bhijos = anterior(a->ph, b);

AG Bhermanos = anterior(a->sH, b);

if (Bhijos != NULL)

return Bhijos;

else

return Bhermanos;

}

}


luego dentro de borrarsub tome el siguiente if 

AG aux = buscar(x, a);

AG aux2 = anterior(a, aux);

if (aux2->pH == aux)

{

aux2->pH = aux->sH;

aux->sH = NULL;

eliminarArbol(aux);

}

else

{

aux2->sH = aux->sH;

aux->sH = NULL;

eliminarArbol(aux);

}

al final de todo esto retorno el parametro que me dieron que es a, ya que el puntero inicial no se puede ver alterado por letra,

mi duda es respecto a la funcion anterior, si es buena practica o se debia de hacer de otra manera.

En respuesta a Fabricio Gabriel Techera Rosado

Re: Ej 5.4 y 5.5

de Matias Richart -

Hola. Te respondo entre líneas.


Saludos

--

para el 4.4 me hice un procedimiento recursivo, lo llame borrarRec, y arranca con un if( a != NULL) y todo lo demas esta adentro, entonces si es NULL no hace nada, queria saber si eso era correcto. en la funcion borrar directamente puse la condicion que debia cumpliar y si las cumplia invocaba el procedimiento borrarRec(AG a&, int x)

me imagino que haces referencia al Ej5.(e).

está bien que si es null no haga nada

es difícil decirte algo más sin ver el código.

para el 4.5 fue un poco mas complicado, hice otro procedimiento llamado eliminarArbol(AG a&, int x) que elimina hoja por hoja el arbol y termina por eliminar la raiz y dejando el puntero apuntando a NULL.

eso está bien.

el problema mas grande fue hallar el x para borrarsub, ya que a diferencia de borrar debia de evaluar si este tenia hijo y borrar todo el hijo. para eso use la funcion del video 4, buscar, e hice una funcion mas llamada anterior, que me da el puntero anterior a uno que pertenezca al arbol y es de la siguiente manera.

yo te recomiendo que pienses una solución alternativa.

la verdad que tu propuesta es un poco complicada y sin ver el código completo no podría decirte si está bien.

lo que te sugiero es que hagas el buscar como parte de tu código recursivo de borrar, de esa forma, cuando encuentres el nodo a eliminar, ya tienes el puntero que luego vas a modificar y no es necesario tu propuesta de "anterior"

AG anterior(AG a, AG b)

{

if (a == NULL)

return NULL;

else if(a->sH == b || a->Ph == b)

return a;

else

{

AG Bhijos = anterior(a->ph, b);

AG Bhermanos = anterior(a->sH, b);

if (Bhijos != NULL)

return Bhijos;

else

return Bhermanos;

}

}


luego dentro de borrarsub tome el siguiente if 

AG aux = buscar(x, a);

AG aux2 = anterior(a, aux);

if (aux2->pH == aux)

{

aux2->pH = aux->sH;

aux->sH = NULL;

eliminarArbol(aux);

}

else

{

aux2->sH = aux->sH;

aux->sH = NULL;

eliminarArbol(aux);

}

al final de todo esto retorno el parametro que me dieron que es a, ya que el puntero inicial no se puede ver alterado por letra,

mi duda es respecto a la funcion anterior, si es buena practica o se debia de hacer de otra manera.

la verdad me quedan dudas de que tu propuesta funcione.
si te interesa, escribí el código completo y lo vemos. igualmente te recomiendo que sigas la sugerencia anterior que hice.

En respuesta a Matias Richart

Re: Ej 5.4 y 5.5

de Fabricio Gabriel Techera Rosado -

muchas gracias por las aclaraciones, igual acabo de ojear la solucion que propusieron en el pdf de soluciones del prac4 y entendi a que se referia con implementar la busqueda en el codigo, cosa que no me quedaba bien clara.


Le dejo de todas maneras le dejo el codigo de como lo realicepara que lo pueda revisar y decirme si mi propuesta serviria o no, aunque claramente es mas larga.


AG borrarSub(AG a, int x)

{

if (pertenece(a, x) && !esArbolHoja(a))

{

AG aux = buscar(x, a);

AG aux2 = anterior(a, aux);

if (aux2->pH == aux)

{

aux2->pH = aux->sH;

aux->sH = NULL;

eliminarArbol(aux);

}

else

{

aux2->sH = aux->sH;

aux->sH = NULL;

eliminarArbol(aux);

}

}

return a;

}




void eliminarArbol(AG a&)

{

if(a != NULL)

{

eliminarArbol(a->sH);

eliminarArbol(a->pH);

delete a;

a = NULL;

}

}


AG anterior(AG a, AG b)

{

if (a == NULL)

return NULL;

else if(a->sH == b || a->Ph == b)

return a;

else

{

AG Bhijos = anterior(a->ph, b);

AG Bhermanos = anterior(a->sH, b);

if (Bhijos != NULL)

return Bhijos;

else

return Bhermanos;

}

}

En respuesta a Fabricio Gabriel Techera Rosado

Re: Ej 5.4 y 5.5

de Matias Richart -

Hola.

Si, tu solución hace lo que pide la letra.

Lo que es importante tener en cuenta, no es tanto el largo, sino las cosas que podrías mejorar para no realizar tantas recorridas del árbol

En tu propuesta usas pertenece, buscar y anterior todas funciones muy similares y que cada una tiene que recorrer (posiblemente) todo el árbol.

Saludos

En respuesta a Matias Richart

Re: Ej 5.4 y 5.5

de Maria Alejandra Galetta Paz -

Buenas tardes, a mi también se me generaron dudas respecto a este ejercicio. 

En concreto me sucedió que hice el ejercicio 5.4 en forma muy parecida a las soluciones que colgaron, pero en lugar de usar una función auxiliar use un procedimiento auxiliar. Es decir, en el procedimiento auxiliar si el entero, estaba presente en al arbol y el nodo en el que estaba no tenía hijos, eliminaba el nodo. De lo contrario aplicaba el procedimiento a la a->pH y a->sH. Es esto correcto?, si es necesario paso el código para ver si esta bien.

Ahora vi que en la soluciones usan una función auxiliar con un resultado tipo bool. Si bien entendí como funciona, me queda la duda de como esta implementado en el void de borrar esa función, ya esta usada como procedimiento y no como una función. Se debería entonces en ese void declarar una variable bool para poder usar esa función auxiliar, o es correcto hacerlo de esa forma?

Muchas gracias

En respuesta a Maria Alejandra Galetta Paz

Re: Ej 5.4 y 5.5

de Matias Richart -

Hola.

Por lo que comentás, tu solución es correcta.

En nuestra solución se devuelve un booleano con el objetivo de evitar recorrer el sH si ya se encontró el nodo en la recorrida del pH.

En la función principal, el resultado booleano no nos interesa, por lo que no se guarda el resultado en ninguna variable. Eso se puede hacer y no pasa nada.

Saludos