Título: Ayuda, no puedo borrar nodos de un Arbol Binario de Busqueda (Solucionado) [C++] Publicado por: DarkSorcerer en 22 Febrero 2014, 02:04 am ACTUALIZACIÓN: Ya pudo resolver mis problemas, logré codificar 100% los métodos
Llevo muchas horas fraccionada en algunos días sin poder solucionar mi problema, resulta que estoy teniendo serios problemas con la implementación de los métodos para eliminar nodos de un arbol binario de búsqueda, tanto de forma recursiva o iterativa, también tengo un serio problema agregando nuevos valores pero de manera ITERATIVA, de la forma recursiva no tengo problema. Acerca del metodo de eliminacion, yo solo tengo la teoría, pero la práctica es donde estoy perdiendo a tal punto que me están dando ganas de tirar la computadora por la ventana, ojalá me puedan ayudar. Bueno, lo que tengo entendido que para la eliminación de un arbol binario de busqueda, se pueden presentar 3 casos 1 - Que el nodo sea una hoja, lo cual es sencillo de eliminar (directamente) 2 - Que el nodo solo tenga un hijo, donde será necesario conectar el padre de ese nodo con el hijo del nodo eliminado. 3 - Si no se cumplen los 2 casos anteriores, se puede remplazar por el menor del subarbol derecho, por lo que cree una funcion que buscara el menor segun el nodo señalado. Pongo el codigo del Arbol y del Nodo, ojala puedan ayudarme, no pondre todo el codigo del programa por que es muy grande, solo los que tengo problemas Código
Código
Código
Código
Título: Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++] Publicado por: DarkSorcerer en 5 Marzo 2014, 12:27 pm No se preocupen por los otras funciones, no he tenido problemas con la implementacion, solo tengo problemas con la eliminacion (recursivo e iterativo) e insercion (solo iterativo)
Título: Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++] Publicado por: eferion en 5 Marzo 2014, 13:02 pm Un problema que tienes es que no actualizas el arbol al eliminar los nodos.
Por ejemplo: Código
haces el delete... ok... pero "p" sigue apuntando a una dirección... solo que no es válida. Deberías pasar un puntero doble a esa función para poder hacer algo tal que: Código
El problema es que el código no se puede probar porque el código que has pasado está incompleto. Más cosillas: Código
Usar variables sin inicializar directamente en un bucle??? mala idea, quizás debieras plantearte un bucle do-while e inicializar "actual" y "detras" a nullptr ( nullptr es nuevo en el estandard C++11 y viene a sustituir a NULL. Y en cuanto a errores, así a simple vista veo esos. El diseño de la clase ArbolBinario deja que desear... si todos los métodos van a ser públicos no se qué sentido tiene crear una clase... pero eso no afecta al funcionamiento del programa. Título: Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++] Publicado por: amchacon en 5 Marzo 2014, 13:33 pm si todos los métodos van a ser públicos no se qué sentido tiene crear una clase... pero eso no afecta al funcionamiento del programa. Pues yo veo unos cuantos métodos privados...Título: Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++] Publicado por: eferion en 5 Marzo 2014, 13:39 pm Pues yo veo unos cuantos métodos privados... El único miembro de la clase ArbolBinario... una instancia de tipo Nodo... es público... todo lo que se añada después de eso es absurdo. Si yo puedo modificar el estado de un objeto a mi antojo sin pasar por su interfaz no tiene sentido la encapsulación. Título: Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++] Publicado por: DarkSorcerer en 7 Marzo 2014, 10:46 am Gracias por darse el tiempo de contestar, por fortuna pude lograr avanzar, ya pude implementar el algoritmo de inserción de manera iterativa y funciona sin problemas y siempre respetando el orden del arbol, también avancé el algoritmo de eliminación recursiva, modifique algunas cosas, estoy a punto de terminar, pero me falta la parte mas dificil y que esta semicompleta.
Bueno, por ahora mi algoritmo de eliminación recursiva funciona cuando los nodos son hojas o cuando tienen un solo subarbol, que puede ser izquierdo o derecho, los comprobé y funciona bien, pero me quiero detener cuando el nodo tiene subarboles izquierdo y derecho a la vez. Investigando mucho descubrí que el nodo hay que reemplazarlo por el menor del subarbol derecho Mi arbol es asi: 15 6 20 3 9 18 24 1 4 7 12 17 Ahora, si quiero eliminar el 15, lo que yo esperaba era esta secuencia Secuencia 1: Buscar el menor numero del subarbol derecho y remplazar su valor por el 15 (no borrar nada aún), por lo que el arbol debería quedar así 17 6 20 3 9 18 24 1 4 7 12 17 Paso 2: Como el menor nodo del subarbol derecho siempre sera una hoja, se puede eliminar sin problemas usando delete, entonces el arbol quedaria asi 17 6 20 3 9 18 24 1 4 7 12 Esa es la teoría para que no se pierda el orden, pero la práctica no me resulta, el destructor del nodo lo implementé de tal manera de que imprima el valor del nodo por pantalla para verificar si está en lo correcto. Recorriendo el arbol en inorden, se ve así 1 3 4 6 7 9 12 15 17 18 20 24 Ahora, cuando quiero eliminar el valor 15, me aparece por pantalla que se eliminó el nodo 17 (antes de eliminar, copié el valor 17 en el nodo que contiene el numero a eliminar), pero el problema sucede cuando quiero recorrer en inorden, me aparece esto 1 3 4 6 7 9 12 17 1629931900 18 20 24 Como después del 12 venia el 15 , se remplazó por el 17 y el nodo que contenía dicho número se eliminó por ser hoja, pero lo más extraño que salga el valor 1629931900 , es algo que no me explico, por que las otras eliminaciones los tuve sin problemas, pero se me dió el caso cuando era para cuando el nodo tenía 2 hijos. Una aclaración, cuando mencioné el recorrido inorden, no se confundan que se da cuando se recorre de esa manera, me sucede también para preorden, posorden y por niveles. Les dejo mi código del algoritmo Código
Código
Código
Título: Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++] Publicado por: eferion en 7 Marzo 2014, 10:54 am haces un delete q... pero qué pasa con el padre que tenía q???
Ese nodo sigue apuntando a una posición de memoria que ahora ya no es válida. Dicho con otras palabras. Te falta una instrucción tal que Código
obviamente no es algo tan directo porque desde un nodo no tienes acceso al padre... Título: Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++] Publicado por: DarkSorcerer en 8 Marzo 2014, 02:47 am haces un delete q... pero qué pasa con el padre que tenía q??? La verdad es que quería evitar a toda costa crear un atributo "Padre" para el nodo, solo quería usar hijo izquierdo y derecho, pero de todas maneras, tu respuesta me sirvió mucho y me dió una gran idea y pude solucionar mi problema, ahora me funciona sin que el programa falle, y eso de que además de borrar debe apuntar a NULL lo tendré en cuenta, se me escapó ese detalle. Ahora intentaré implementar el algoritmo pero de manera iterativa :DEse nodo sigue apuntando a una posición de memoria que ahora ya no es válida. Dicho con otras palabras. Te falta una instrucción tal que Código
obviamente no es algo tan directo porque desde un nodo no tienes acceso al padre... Saludos |