Programación Específica > Diseño de Algoritmos
Arboles Y Nodos Hojas Inciales
Conti:
Hola! ^^
Tengo un problema con cierto algoritmo.Veamos:
Dado un árbol binario(no ordenado), eliminar todos los nodos hojas iniciales, es decir aquellos que que son hojas en el momento que me dan el árbol.
El archivo que adjunto, es un dibujito para verlo mas claro.(perdón me ha salido un poco cutre :lol: )
Tendría que borrar los que estan en rojo, ya ya esta.
El problema reside en que cada vez que intento diseñar el algoritmo,simepre me sale una solución recursiva que ser carga todo el árbol,además de los que tiene que eliminar,pero que elimine todo el arbol no forma parte del juego :blink: .
¿una paqueña pista porfi? :(
Continuaré mi batalla por sacarlo :lightsabre:
ps:reutilizo muchos métodos del tipo abstracto árbol binario.(como recorrido preorden,etc)
Gracias ^^.
lencho:
--- Cita de: "Conti" --- Hola! ^^
Tengo un problema con cierto algoritmo.Veamos:
Dado un árbol binario(no ordenado), eliminar todos los nodos hojas iniciales, es decir aquellos que que son hojas en el momento que me dan el árbol.
El archivo que adjunto, es un dibujito para verlo mas claro.(perdón me ha salido un poco cutre :lol: )
Tendría que borrar los que estan en rojo, ya ya esta.
El problema reside en que cada vez que intento diseñar el algoritmo,simepre me sale una solución recursiva que ser carga todo el árbol,además de los que tiene que eliminar,pero que elimine todo el arbol no forma parte del juego :blink: .
¿una paqueña pista porfi? :(
Continuaré mi batalla por sacarlo :lightsabre:
ps:reutilizo muchos métodos del tipo abstracto árbol binario.(como recorrido preorden,etc)
Gracias ^^.
--- Fin de la cita ---
jaja, recuerdo haber echo ese algoritmo cuando di el examen para ser auxiliar de catedra.
Luego te ayudo, ahorita estoy corto de tiempo.
BYTE.
AnioN:
como tenes que diseñar el algoritmo?, en algun lenguaje en particular?. Una vez en C lo hice, y la solucion es simple. Tenes que recorrer todo el arbol y comprobas que ambos punteros de cada nodo sean igual a null y listo.
hano:
Un recorrido en el árbol, pero con cuidado, vaya que se elimine un nodo hijo, y el padre, al tener dos hijos null, es eliminado también.
El recorrido creo que debería ser preorden, estilo cola. Recorrer primero los nodos padres. Comprobar los dos hijos. Si un hijo es hoja, eliminarlo, si no, añadirlo a la cola para visitar en la siguiente iteración.
Conti:
Voy pillando la idea.Según lo que decís debería ser algo así no?(ejemplo usando c++)
--- Código: Text --- void eliminarHojas(Arbol<T> a,Cola<T> &c){ if(!a.esVacio()){//esVacio nos devuelve un booleano segun sea vacio o no el árbol if(a.raiz()->hijoIzquierdo == null && a.raiz()->hijoDerecho==null){ delete a.raiz(); }else{ c.insertar(a.raiz); eliminarHojas(a.HijoIzquierdo(),c); eliminarHojas(a.HijoDerecho(),c); } }}//una vez finalice el metodo solo tengo que ir sacando d ela cola los elementos ///que se irán visitando /*El metodo raiz() devuelve al nodo raiz del subarbolEl metodo HijoDerecho() devuelve el subarbol derecho de esa raizEl metodo HijoIzquierdo() devuelve el subarbol izquierdo de esa raizCada nodo e suna estructura que contiene:T infoArbol<T> hijoIzquierdoArbol<T> hijoDerecho*/ A ver si por ahí van los tiros :smartass:
Navegación
[#] Página Siguiente
Ir a la versión completa