Programación Específica > Diseño de Algoritmos
Arboles Y Nodos Hojas Inciales
hano:
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 --- eliminarHojas(raiz) { si raiz tiene HijoHizquierdo si raiz.HijoIzquierdo es hoja eliminar HijoIzquierdo si no eliminarHojas(raiz.HijoIzquierdo) si raiz tiene HijoDerecho si raiz.HijoDerecho es hoja eliminar HijoDerecho si no eliminarHojas(raiz.HijoDerecho )}
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.
Conti:
Gracias a todos por la ayuda.Al final la solución era algo parecido a:
--- Código: Text --- void eliminarHojas(Arbol<T> a){ if(!a.esVacio()){ if(a.HijoDerecho().esVacio()&& a.HijoIzquierdo().esVacio()){ a.borrar()//en principio noe sta implementado,pero borraría ese nodo padre del subarbol }else{ eliminarHojas(a.HijoIzquierdo()); eliminarHojas(a.HijoDerecho()); } } }} Un saludo!
Nebire:
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...
Ithilien:
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!
Navegación
[*] Página Anterior
Ir a la versión completa