SoloCodigo

Programación Específica => Diseño de Algoritmos => Mensaje iniciado por: Conti en Sábado 3 de Marzo de 2007, 13:19

Título: Arboles Y Nodos Hojas Inciales
Publicado por: Conti en Sábado 3 de Marzo de 2007, 13:19
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 ^^.
Título: Re: Arboles Y Nodos Hojas Inciales
Publicado por: lencho en Sábado 3 de Marzo de 2007, 13:44
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 ^^.
jaja, recuerdo haber echo ese algoritmo cuando di el examen para ser auxiliar de catedra.
Luego te ayudo, ahorita estoy corto de tiempo.

BYTE.
Título: Re: Arboles Y Nodos Hojas Inciales
Publicado por: AnioN en Sábado 3 de Marzo de 2007, 13:48
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.
Título: Re: Arboles Y Nodos Hojas Inciales
Publicado por: hano en Sábado 3 de Marzo de 2007, 18:14
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.
Título: Re: Arboles Y Nodos Hojas Inciales
Publicado por: Conti en Sábado 3 de Marzo de 2007, 19:29
Voy pillando la idea.Según lo que decís debería ser algo así no?(ejemplo usando c++)
Código: Text
  1.  
  2. void eliminarHojas(Arbol<T> a,Cola<T> &c){
  3.   if(!a.esVacio()){//esVacio nos devuelve un booleano segun sea vacio o no el árbol
  4.     if(a.raiz()->hijoIzquierdo == null && a.raiz()->hijoDerecho==null){
  5.       delete a.raiz();
  6.     }else{
  7.       c.insertar(a.raiz);
  8.       eliminarHojas(a.HijoIzquierdo(),c);
  9.       eliminarHojas(a.HijoDerecho(),c);
  10.     }
  11.   }
  12. }//una vez finalice el metodo solo tengo que ir sacando d ela cola los elementos
  13. ///que se irán visitando
  14.  
  15. /*
  16. El metodo raiz() devuelve al nodo raiz del subarbol
  17. El metodo HijoDerecho() devuelve el subarbol derecho de esa raiz
  18. El metodo HijoIzquierdo() devuelve el subarbol izquierdo de esa raiz
  19. Cada nodo e suna estructura que contiene:
  20. T info
  21. Arbol<T> hijoIzquierdo
  22. Arbol<T> hijoDerecho
  23. */
  24.  
  25.  
A ver si por ahí van los tiros  :smartass:
Título: Re: Arboles Y Nodos Hojas Inciales
Publicado por: hano en Sábado 3 de Marzo de 2007, 20:47
Si lo quieres hacer recursivo, no hace falta la cola. La cola sería para la implementación iterativa.

En el código, insertas en la cola, pero no sacas nunca.

Posible pseudo código...
Código: Text
  1.  
  2. eliminarHojas(raiz) {
  3.    si raiz tiene HijoHizquierdo
  4.       si raiz.HijoIzquierdo es hoja
  5.          eliminar HijoIzquierdo
  6.       si no
  7.          eliminarHojas(raiz.HijoIzquierdo)
  8.  
  9.    si raiz tiene HijoDerecho
  10.       si raiz.HijoDerecho es hoja
  11.          eliminar HijoDerecho
  12.       si no
  13.          eliminarHojas(raiz.HijoDerecho )
  14. }
  15.  
  16.  

En la llamada inicial simplemente habría que comprobar que el nodo raiz no sea hoja también.

Una vez que funcione la solución recursiva, sería bueno intentarlo con una cola de forma iterativa.
Título: Re: Arboles Y Nodos Hojas Inciales
Publicado por: Conti en Miércoles 7 de Marzo de 2007, 09:22
Gracias a todos por la ayuda.Al final la solución era algo parecido a:
Código: Text
  1.  
  2. void eliminarHojas(Arbol<T> a){
  3.   if(!a.esVacio()){
  4.     if(a.HijoDerecho().esVacio()&& a.HijoIzquierdo().esVacio()){
  5.       a.borrar()//en principio noe sta implementado,pero borraría ese nodo padre del subarbol
  6.      
  7.     }else{
  8.       eliminarHojas(a.HijoIzquierdo());
  9.       eliminarHojas(a.HijoDerecho());
  10.       }
  11.     }
  12.   }
  13. }
  14.  
  15.  
Un saludo!
Título: Re: Arboles Y Nodos Hojas Inciales
Publicado por: Nebire en Miércoles 11 de Julio de 2007, 17:00
De acuerdo a tu dibujo, debes borrar sólo él último nodo, es decir el que no tiene más nodos bajo si.

En teoría si se te borró todo el árbol es bastante probable que lo llevaras bien enfocado y el problema está en la recursión.

es decir tras eliminar un nodo, su ancestro ahora es la hoja, por tanto si le das recursividad, se borrará ese, que a su vez dejará el nodo superior como hoja...y al final podas todo el árbol....

El árbol solo ha de ser ecorrido una vez, cada elemento sólo se debe comprobar una vez. Si con todo lo quieres hacer recursivo, entonces cuando se pasa por un nodo, si se decidió no borrar se marca, y antes de borrar se comprueba cada marca si se ´marcó no borrar aunque sea nodo final, no se deb borrar...
Título: Re: Arboles Y Nodos Hojas Inciales
Publicado por: Ithilien en Domingo 26 de Agosto de 2007, 17:25
Lo que puedes hacer, por ejemplo, es hacer un recorrido en preorden y eliminar los nodos cuyos punteros a hijos sean null. Si no quieres hacerlo recursivo porque no puedas, yo hice una vez un recorrido en preorden, iterativo, usando pilas ( de la stl para c++ ).

Saludos!