elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ayuda, no puedo borrar nodos de un Arbol Binario de Busqueda (Solucionado) [C++]		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ayuda, no puedo borrar nodos de un Arbol Binario de Busqueda (Solucionado) [C++]  (Leído 12,685 veces)
DarkSorcerer

Desconectado Desconectado

Mensajes: 69



Ver Perfil
Ayuda, no puedo borrar nodos de un Arbol Binario de Busqueda (Solucionado) [C++]
« 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
  1. #ifndef NODO_H
  2. #define	NODO_H
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. class Nodo {
  8. public:
  9.  
  10.     int dato;
  11.     Nodo *izquierdo;
  12.     Nodo *derecho;
  13.  
  14.     Nodo(int d);
  15.     virtual ~Nodo();
  16.  
  17. private:
  18.  
  19. };
  20.  
  21. #endif	/* NODO_H */
  22.  
  23.  

Código
  1. #include "Nodo.h"
  2.  
  3. Nodo::Nodo(int d) {
  4.  
  5.     this->dato = d;
  6.     this->izquierdo = NULL;
  7.     this->derecho = NULL;
  8.  
  9. }
  10.  
  11. Nodo::~Nodo() {
  12.  
  13.     cout << "\n\nEliminando nodo " << dato << ".\n\n";
  14.  
  15. }
  16.  
  17.  

Código
  1. #ifndef ARBOLBINARIO_H
  2. #define	ARBOLBINARIO_H
  3. #include "Nodo.h" 
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. class ArbolBinario {
  9. public:
  10.  
  11.     Nodo *raiz;
  12.  
  13.     ArbolBinario(); //Implementado.
  14.     virtual ~ArbolBinario(); //Implementado.
  15.     void insertarRecursivo(int d); //Implementado exitosamente.
  16.     void insertarIterativo(int d); //Preguntar como resolverlo.
  17.     void eliminarRecursivo(int d); 
  18.     void eliminarIterativo(int d);
  19.     bool buscarRecursivo(int d); //Implementado exitosamente.
  20.     bool buscarIterativo(int d); //Implementado exitosamente.
  21.     void preordenRecursivo(); //Implementado exitosamente.
  22.     void preordenIterativo(); //Implementado exitosamente.
  23.     void inordenRecursivo(); //Implementado exitosamente.
  24.     void inordenIterativo(); //Implementado exitosamente.
  25.     void posordenRecursivo(); //Implementado exitosamente.
  26.     void posordenIterativo(); 
  27.     void recorrerNiveles(); //Implementado exitosamente.
  28.     int contarNodos(); //Implementado exitosamente.
  29.     int contarHojas(); //Implementado exitosamente.
  30.     int alturaArbol1(); //Implementado exitosamente.
  31.     int alturaArbol2(); //Implementado exitosamente.
  32.     Nodo* buscarMenor(); //Implementado exitosamente.
  33.     Nodo* buscarMayor(); //Implementado exitosamente.
  34.     Nodo* buscarMenor(Nodo *p); //Implementado exitosamente
  35.     Nodo* buscarMayor(Nodo *p); //Implementado exitosamente
  36.     Nodo* obtenerNodo(int d); //Implementado exitosamente.
  37.     void copiar(ArbolBinario *a); //Implementado exitosamente.
  38.     bool comparar(ArbolBinario *a); //Implementado exitosamente.
  39.     void destruir(); //Implementado exitosamente.
  40.  
  41. private:
  42.  
  43.     Nodo* insertarRecursivo(int d, Nodo *p); 
  44.     void eliminarRecursivo(int d, Nodo *q, Nodo *p); 
  45.     bool buscarRecursivo(int d, Nodo *p); 
  46.     void preordenRecursivo(Nodo *p); 
  47.     void inordenRecursivo(Nodo *p); 
  48.     void posordenRecursivo(Nodo *p); 
  49.     int contarNodos(Nodo *p); 
  50.     int contarHojas(Nodo *p); 
  51.     int alturaArbol1(Nodo *p); 
  52.     int alturaArbol2(Nodo *p); 
  53.     Nodo* obtenerNodo(int d, Nodo *p); 
  54.     Nodo* copiar(Nodo *p); 
  55.     bool comparar(Nodo *p, Nodo *q); 
  56.     void destruir(Nodo *p); 
  57.     void cortarNodo(Nodo *p, Nodo *q);
  58.  
  59. };
  60.  
  61. #endif	/* ARBOLBINARIO_H */
  62.  

Código
  1. #include "ArbolBinario.h"
  2. #include <queue>
  3. #include <stack>
  4.  
  5. ArbolBinario::ArbolBinario() {
  6.  
  7.     this->raiz = NULL;
  8.  
  9. }
  10.  
  11. ArbolBinario::~ArbolBinario() {
  12.  
  13.     cout << "\n\nEliminando arbol binario.\n\n";
  14.     destruir();
  15.  
  16. }
  17.  
  18. void ArbolBinario::insertarRecursivo(int d){
  19.  
  20.     this->raiz = insertarRecursivo(d,raiz);
  21.  
  22. }
  23.  
  24. Nodo* ArbolBinario::insertarRecursivo(int d, Nodo *p){
  25.  
  26.     if(p == NULL){
  27.  
  28.         p = new Nodo(d);
  29.         return p;
  30.  
  31.     }else{
  32.  
  33.         if(p->dato == d){
  34.  
  35.             return p;
  36.  
  37.         }
  38.  
  39.         if(d < p->dato){
  40.  
  41.             p->izquierdo = insertarRecursivo(d,p->izquierdo);
  42.  
  43.         }else{
  44.  
  45.             p->derecho = insertarRecursivo(d,p->derecho);
  46.  
  47.         }
  48.  
  49.         return p;
  50.  
  51.     }
  52.  
  53. }
  54.  
  55. void ArbolBinario::insertarIterativo(int d){
  56.  
  57.     if(raiz == NULL){
  58.  
  59.         this->raiz = new Nodo(d);
  60.  
  61.     }else{
  62.  
  63.         Nodo *actual;
  64.         Nodo *detras;
  65.  
  66.         while(actual != NULL){
  67.  
  68.             if(actual->dato == d){
  69.  
  70.                 return;
  71.  
  72.             }
  73.  
  74.             detras = actual;
  75.  
  76.             if(d < actual->dato){
  77.  
  78.                 actual = actual->izquierdo;
  79.                 detras->izquierdo = actual;
  80.  
  81.             }else{
  82.  
  83.                 actual = actual->derecho;
  84.                 detras->derecho = actual;
  85.  
  86.             }
  87.  
  88.         }
  89.  
  90.         actual = new Nodo(d);
  91.  
  92.     }
  93.  
  94. }
  95.  
  96. void ArbolBinario::eliminarRecursivo(int d){
  97.  
  98.     eliminarRecursivo(d,raiz,raiz);
  99.  
  100. }
  101.  
  102. void ArbolBinario::eliminarRecursivo(int d, Nodo *q, Nodo *p){
  103.  
  104.     if(p != NULL){
  105.  
  106.         if(p->dato == d){
  107.  
  108.             cortarNodo(q,p);
  109.  
  110.  
  111.         }else{
  112.  
  113.             q = p;
  114.  
  115.             if(d < p->dato){
  116.  
  117.                 p = p->izquierdo;
  118.                 eliminarRecursivo(d,q,p);
  119.  
  120.             }else{
  121.  
  122.                 p = p->derecho;
  123.                 eliminarRecursivo(d,q,p);
  124.  
  125.             }
  126.  
  127.         }
  128.  
  129.     }
  130.  
  131. }
  132.  
  133. void ArbolBinario::cortarNodo(Nodo *q, Nodo *p){
  134.  
  135.     //Si el nodo a eliminar es una hoja, se borra sin problemas.   
  136.  
  137.     if(p->izquierdo == NULL && p->derecho == NULL){
  138.  
  139.         delete p;
  140.         return;
  141.  
  142.     }
  143.  
  144.     //Si el nodo tiene solo un hijo izquierdo, se remplaza por su nieto.
  145.  
  146.     if(p->izquierdo != NULL && p->derecho == NULL){
  147.  
  148.         if(p->dato < q->dato){
  149.  
  150.             q->izquierdo = p->izquierdo;
  151.             delete p;
  152.  
  153.         }else{
  154.  
  155.             q->derecho = p->izquierdo;
  156.             delete p;
  157.  
  158.         }
  159.  
  160.         return;
  161.  
  162.     }
  163.  
  164.     //Si el nodo tiene un solo hijo derecho, se remplaza por su nieto.
  165.  
  166.     if(p->izquierdo == NULL && p->derecho != NULL){
  167.  
  168.         if(p->dato < q->dato){
  169.  
  170.             q->izquierdo = p->derecho;
  171.             delete p;
  172.  
  173.         }else{
  174.  
  175.             q->derecho = p->derecho;
  176.             delete p;
  177.  
  178.         }
  179.  
  180.         return;
  181.  
  182.     }
  183.  
  184.     //De lo contrario, se encuentra en lo profundo de las ramas. Remplazar por 
  185.     //el menor del subarbol derecho.
  186.  
  187.     Nodo *menor = buscarMenor(p->derecho);    
  188.     p->dato = menor->dato;
  189.     delete menor;
  190.     return;
  191.  
  192. }
  193.  
« Última modificación: 8 Marzo 2014, 11:28 am por DarkSorcerer » En línea
DarkSorcerer

Desconectado Desconectado

Mensajes: 69



Ver Perfil
Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++]
« Respuesta #1 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)
En línea
eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++]
« Respuesta #2 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
  1. void ArbolBinario::cortarNodo(Nodo *q, Nodo *p){
  2.  
  3.     //Si el nodo a eliminar es una hoja, se borra sin problemas.   
  4.  
  5.     if(p->izquierdo == NULL && p->derecho == NULL){
  6.  
  7.         delete p;
  8.         return;
  9.  
  10.     }
  11.     // ...
  12. }

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
  1. void ArbolBinario::cortarNodo(Nodo *q, Nodo **p){
  2.  
  3.     //Si el nodo a eliminar es una hoja, se borra sin problemas.   
  4.  
  5.     if((*p)->izquierdo == NULL && (*p)->derecho == NULL){
  6.  
  7.         delete *p;
  8.         *p = NULL;
  9.         return;
  10.  
  11.     }
  12.     // ...
  13. }

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
  1.         Nodo *actual;
  2.         Nodo *detras;
  3.  
  4.         while(actual != NULL){

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.
En línea
amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++]
« Respuesta #3 en: 5 Marzo 2014, 13:33 pm »
Cita de: eferion en  5 Marzo 2014, 13:02 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...
En línea
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++]
« Respuesta #4 en: 5 Marzo 2014, 13:39 pm »
Cita de: amchacon en  5 Marzo 2014, 13:33 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.
En línea
DarkSorcerer

Desconectado Desconectado

Mensajes: 69



Ver Perfil
Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++]
« Respuesta #5 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
  1. void ArbolBinario::eliminarRecursivo(int d){
  2.  
  3.     this->raiz = eliminarRecursivo(d,raiz);
  4.  
  5. }

Código
  1. Nodo* ArbolBinario::eliminarRecursivo(int d, Nodo *p){
  2.  
  3.     if(p == NULL){
  4.  
  5.         return p;
  6.  
  7.     }else{
  8.  
  9.         if(p->dato == d){
  10.  
  11.             p = podarNodo(p);
  12.             return p;
  13.  
  14.         }
  15.  
  16.         if(d < p->dato){
  17.  
  18.             p->izquierdo = eliminarRecursivo(d,p->izquierdo);
  19.  
  20.         }else{
  21.  
  22.             p->derecho = eliminarRecursivo(d,p->derecho);
  23.  
  24.         }
  25.  
  26.         return p;
  27.  
  28.     }
  29.  
  30. }

Código
  1. Nodo* ArbolBinario::podarNodo(Nodo *p){
  2.  
  3.     //Si el nodo es una hoja
  4.  
  5.     if(p->izquierdo == NULL && p->derecho == NULL){
  6.  
  7.         delete p;
  8.         return NULL;
  9.  
  10.     }
  11.  
  12.     //Si el nodo tiene solo un hijo (el izquierdo)
  13.  
  14.     if(p->izquierdo != NULL && p->derecho == NULL){
  15.  
  16.         Nodo *q = p->izquierdo;
  17.         delete p;
  18.         return q;
  19.  
  20.     }
  21.  
  22.     //Si el nodo tiene solo un hijo (el derecho))
  23.  
  24.     if(p->izquierdo == NULL && p->derecho != NULL){
  25.  
  26.         Nodo *q = p->derecho;
  27.         delete p;
  28.         return q;
  29.  
  30.     }
  31.  
  32.     Nodo *q = nodoMenor(p->derecho);
  33.     p->dato = q->dato;
  34.     delete q;
  35.     return p;
  36.  
  37. }
  38.  
                       
« Última modificación: 7 Marzo 2014, 10:49 am por DarkSorcerer » En línea
eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++]
« Respuesta #6 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
  1. q->Padre->izquierdo = NULL;

obviamente no es algo tan directo porque desde un nodo no tienes acceso al padre...
« Última modificación: 7 Marzo 2014, 10:57 am por eferion » En línea
DarkSorcerer

Desconectado Desconectado

Mensajes: 69



Ver Perfil
Re: Ayuda, no puedo eliminar nodos de un Arbol Binario de Busqueda ni insertar [C++]
« Respuesta #7 en: 8 Marzo 2014, 02:47 am »
Cita de: 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
  1. q->Padre->izquierdo = NULL;

obviamente no es algo tan directo porque desde un nodo no tienes acceso al padre...
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 :D

Saludos
« Última modificación: 8 Marzo 2014, 02:49 am por DarkSorcerer » En línea
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
MOVIDO: Arbol binario de busqueda
ASM 		Eternal Idol 0 2,645 Último mensaje 15 Septiembre 2009, 19:18 pm
por Eternal Idol
Problemas con imprimir un arbol binario de busqueda junto a una lista simple!!
Programación C/C++ 		01munrra 1 5,171 Último mensaje 23 Junio 2011, 02:24 am
por BlackZeroX
Interrupción en programa de C++ extraña - Arbol binario de busqueda.
Programación C/C++ 		lb12 0 1,562 Último mensaje 7 Enero 2015, 22:13 pm
por lb12
Urgenteeeeee!!! Ayuda con arbol binario de busqueda
Programación C/C++ 		mathias_vg 2 2,047 Último mensaje 20 Noviembre 2015, 18:54 pm
por 0xFer
Eliminación de nodos en un árbol binario ordenado.
Programación C/C++ 		NextByte 0 1,734 Último mensaje 5 Abril 2019, 18:52 pm
por NextByte
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines