Ayuda, no puedo borrar nodos de un Arbol Binario de Busqueda (Solucionado) [C++]

[DarkSorcerer]

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 (cpp) [Seleccionar] Expandir

#ifndef NODO_H
#define NODO_H
#include <iostream>

using namespace std;

class Nodo {
public:
   
   int dato;
   Nodo *izquierdo;
   Nodo *derecho;
   
   Nodo(int d);
   virtual ~Nodo();
   
private:

};

#endif /* NODO_H */



Código (cpp) [Seleccionar] Expandir

#include "Nodo.h"

Nodo::Nodo(int d) {
   
   this->dato = d;
   this->izquierdo = NULL;
   this->derecho = NULL;
   
}

Nodo::~Nodo() {
   
   cout << "\n\nEliminando nodo " << dato << ".\n\n";
   
}



Código (cpp) [Seleccionar] Expandir

#ifndef ARBOLBINARIO_H
#define ARBOLBINARIO_H
#include "Nodo.h"
#include <iostream>

using namespace std;

class ArbolBinario {
public:
   
   Nodo *raiz;
   
   ArbolBinario(); //Implementado.
   virtual ~ArbolBinario(); //Implementado.
   void insertarRecursivo(int d); //Implementado exitosamente.
   void insertarIterativo(int d); //Preguntar como resolverlo.
   void eliminarRecursivo(int d);
   void eliminarIterativo(int d);
   bool buscarRecursivo(int d); //Implementado exitosamente.
   bool buscarIterativo(int d); //Implementado exitosamente.
   void preordenRecursivo(); //Implementado exitosamente.
   void preordenIterativo(); //Implementado exitosamente.
   void inordenRecursivo(); //Implementado exitosamente.
   void inordenIterativo(); //Implementado exitosamente.
   void posordenRecursivo(); //Implementado exitosamente.
   void posordenIterativo();
   void recorrerNiveles(); //Implementado exitosamente.
   int contarNodos(); //Implementado exitosamente.
   int contarHojas(); //Implementado exitosamente.
   int alturaArbol1(); //Implementado exitosamente.
   int alturaArbol2(); //Implementado exitosamente.
   Nodo* buscarMenor(); //Implementado exitosamente.
   Nodo* buscarMayor(); //Implementado exitosamente.
   Nodo* buscarMenor(Nodo *p); //Implementado exitosamente
   Nodo* buscarMayor(Nodo *p); //Implementado exitosamente
   Nodo* obtenerNodo(int d); //Implementado exitosamente.
   void copiar(ArbolBinario *a); //Implementado exitosamente.
   bool comparar(ArbolBinario *a); //Implementado exitosamente.
   void destruir(); //Implementado exitosamente.
   
private:
   
   Nodo* insertarRecursivo(int d, Nodo *p);
   void eliminarRecursivo(int d, Nodo *q, Nodo *p);
   bool buscarRecursivo(int d, Nodo *p);
   void preordenRecursivo(Nodo *p);
   void inordenRecursivo(Nodo *p);
   void posordenRecursivo(Nodo *p);
   int contarNodos(Nodo *p);
   int contarHojas(Nodo *p);
   int alturaArbol1(Nodo *p);
   int alturaArbol2(Nodo *p);
   Nodo* obtenerNodo(int d, Nodo *p);
   Nodo* copiar(Nodo *p);
   bool comparar(Nodo *p, Nodo *q);
   void destruir(Nodo *p);
   void cortarNodo(Nodo *p, Nodo *q);

};

#endif /* ARBOLBINARIO_H */


Código (cpp) [Seleccionar] Expandir

#include "ArbolBinario.h"
#include <queue>
#include <stack>

ArbolBinario::ArbolBinario() {
   
   this->raiz = NULL;
   
}

ArbolBinario::~ArbolBinario() {
   
   cout << "\n\nEliminando arbol binario.\n\n";
   destruir();
   
}

void ArbolBinario::insertarRecursivo(int d){
   
   this->raiz = insertarRecursivo(d,raiz);
   
}

Nodo* ArbolBinario::insertarRecursivo(int d, Nodo *p){
   
   if(p == NULL){
       
       p = new Nodo(d);
       return p;
       
   }else{
       
       if(p->dato == d){
           
           return p;
           
       }
       
       if(d < p->dato){
           
           p->izquierdo = insertarRecursivo(d,p->izquierdo);
           
       }else{
           
           p->derecho = insertarRecursivo(d,p->derecho);
           
       }
       
       return p;
       
   }
   
}

void ArbolBinario::insertarIterativo(int d){
   
   if(raiz == NULL){
       
       this->raiz = new Nodo(d);
       
   }else{
       
       Nodo *actual;
       Nodo *detras;
       
       while(actual != NULL){
           
           if(actual->dato == d){
               
               return;
               
           }
           
           detras = actual;
           
           if(d < actual->dato){
               
               actual = actual->izquierdo;
               detras->izquierdo = actual;
               
           }else{
               
               actual = actual->derecho;
               detras->derecho = actual;
               
           }
           
       }
       
       actual = new Nodo(d);
       
   }
   
}

void ArbolBinario::eliminarRecursivo(int d){
   
   eliminarRecursivo(d,raiz,raiz);
   
}

void ArbolBinario::eliminarRecursivo(int d, Nodo *q, Nodo *p){
   
   if(p != NULL){
       
       if(p->dato == d){
           
           cortarNodo(q,p);

           
       }else{
           
           q = p;
           
           if(d < p->dato){
               
               p = p->izquierdo;
               eliminarRecursivo(d,q,p);
               
           }else{
               
               p = p->derecho;
               eliminarRecursivo(d,q,p);
               
           }
           
       }
       
   }
   
}

void ArbolBinario::cortarNodo(Nodo *q, Nodo *p){
   
   //Si el nodo a eliminar es una hoja, se borra sin problemas.  
   
   if(p->izquierdo == NULL && p->derecho == NULL){
       
       delete p;
       return;
       
   }
   
   //Si el nodo tiene solo un hijo izquierdo, se remplaza por su nieto.
   
   if(p->izquierdo != NULL && p->derecho == NULL){
       
       if(p->dato < q->dato){
           
           q->izquierdo = p->izquierdo;
           delete p;
           
       }else{
           
           q->derecho = p->izquierdo;
           delete p;
           
       }
       
       return;
       
   }
   
   //Si el nodo tiene un solo hijo derecho, se remplaza por su nieto.
   
   if(p->izquierdo == NULL && p->derecho != NULL){
       
       if(p->dato < q->dato){
           
           q->izquierdo = p->derecho;
           delete p;
           
       }else{
           
           q->derecho = p->derecho;
           delete p;
           
       }
       
       return;
       
   }
   
   //De lo contrario, se encuentra en lo profundo de las ramas. Remplazar por
   //el menor del subarbol derecho.
   
   Nodo *menor = buscarMenor(p->derecho);    
   p->dato = menor->dato;
   delete menor;
   return;
   
}


[DarkSorcerer]

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)

[eferion]

Un problema que tienes es que no actualizas el arbol al eliminar los nodos.

Por ejemplo:

Código (c) [Seleccionar] Expandir

void ArbolBinario::cortarNodo(Nodo *q, Nodo *p){

    //Si el nodo a eliminar es una hoja, se borra sin problemas.   

    if(p->izquierdo == NULL && p->derecho == NULL){

        delete p;
        return;

    }
    // ...
}

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 (c) [Seleccionar] Expandir

void ArbolBinario::cortarNodo(Nodo *q, Nodo **p){

    //Si el nodo a eliminar es una hoja, se borra sin problemas.   

    if((*p)->izquierdo == NULL && (*p)->derecho == NULL){

        delete *p;
        *p = NULL;
        return;

    }
    // ...
}

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 (cpp) [Seleccionar] Expandir


        Nodo *actual;
        Nodo *detras;

        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.

[amchacon]

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...

[eferion]

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.

[DarkSorcerer]

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 (cpp) [Seleccionar] Expandir

void ArbolBinario::eliminarRecursivo(int d){
   
   this->raiz = eliminarRecursivo(d,raiz);
   
}

Código (cpp) [Seleccionar] Expandir

Nodo* ArbolBinario::eliminarRecursivo(int d, Nodo *p){
   
   if(p == NULL){
       
       return p;
       
   }else{
       
       if(p->dato == d){
           
           p = podarNodo(p);
           return p;
           
       }
       
       if(d < p->dato){
           
           p->izquierdo = eliminarRecursivo(d,p->izquierdo);
           
       }else{
           
           p->derecho = eliminarRecursivo(d,p->derecho);
           
       }
       
       return p;
       
   }
   
}

Código (cpp) [Seleccionar] Expandir

Nodo* ArbolBinario::podarNodo(Nodo *p){
   
   //Si el nodo es una hoja
   
   if(p->izquierdo == NULL && p->derecho == NULL){
       
       delete p;
       return NULL;
       
   }
   
   //Si el nodo tiene solo un hijo (el izquierdo)
   
   if(p->izquierdo != NULL && p->derecho == NULL){
       
       Nodo *q = p->izquierdo;
       delete p;
       return q;
       
   }
   
   //Si el nodo tiene solo un hijo (el derecho))
   
   if(p->izquierdo == NULL && p->derecho != NULL){
       
       Nodo *q = p->derecho;
       delete p;
       return q;
       
   }
   
   Nodo *q = nodoMenor(p->derecho);
   p->dato = q->dato;
   delete q;
   return p;
   
}

                       

[eferion]

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 (c) [Seleccionar] Expandir

q->Padre->izquierdo = NULL;

obviamente no es algo tan directo porque desde un nodo no tienes acceso al padre...

[DarkSorcerer]

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 (c) [Seleccionar] Expandir

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

Saludos