At the moment of executing it, it adds and deletes me well except when I want to delete a node without children, I do not understand why I get an error and the program goes bankrupt I would like to know if someone could help me giving me a tip, thanks in advance. here is the complete code
#include <iostream>
#include <conio2.h>
#include <stdlib.h>
using namespace std;
struct Nodo{
int dato;
Nodo *der;
Nodo *izq;
Nodo *padre; ///USARE ESTE PTR EN EL MOMENTO DE ELIMINAR UN ELEMENTO DEL ARBOL
};
void menu();
Nodo *crearNodo(int,Nodo*);
void insertarNodo(Nodo *&,int, Nodo *);
void mostrarArbol(Nodo *,int);
void eliminar(Nodo *,int);
void eliminarNodo(Nodo *);
Nodo *minimo(Nodo *);
void reemplazar(Nodo *,Nodo *);
void destruirNodo(Nodo *);
Nodo *arbol = NULL;
int main()
{
menu();
getch();
return 0;
}
void menu(){
int dato,opcion,contador=0;
do{
cout<<" MENU DEL ARBOL "<<endl;
cout<<"1-insertar nodo"<<endl;
cout<<"2-mostrar todo el arbol"<<endl;
cout<<"3-eliminar nodo"<<endl;
cout<<"4-salir"<<endl;
cout<<"OPCION: ";
cin>>opcion;
switch(opcion){
case 1:
{
cout<<"digite un numero: "<<endl;
cin>>dato;
insertarNodo(arbol,dato,NULL);
cout<<endl;
system("pause");
break;
}
case 2:
{
cout<<"MOSTRANDO EL ARBOL COMPLETO"<<endl;
mostrarArbol(arbol,contador);
cout<<endl;
system("pause");
break;
}
case 3:
{
cout<<"digite el numero a eliminar"<<endl;
cin>>dato;
eliminar(arbol,dato);
cout<<endl;
system("pause");
}
}
system("cls");
}while(opcion!=4);
}
Nodo *crearNodo(int n,Nodo *padre){
Nodo *nuevo_nodo = new Nodo();
nuevo_nodo->dato = n;
nuevo_nodo->der = NULL;
nuevo_nodo->izq = NULL;
nuevo_nodo->padre = padre; ///ojo, cuidado te confundis y pensas que el padre despues del igual
///es el mismo padre del campo nuevo_nodo LOL.
return nuevo_nodo;
}///CREAR UN NODO PARA INSERTAR EN EL ARBOL
void insertarNodo(Nodo *&arbol,int n,Nodo *padre){
if(arbol == NULL){
Nodo *nuevo_nodo = crearNodo(n,padre);///De esta manera comunicaremos al nodo hijo con su nodo antecesor
arbol = nuevo_nodo; ///EN LA PRIMERA CORRIDA SI EL ARBOL ESTA VACIO
}
else{
int valorRaiz = arbol->dato;
if(n < valorRaiz){
insertarNodo(arbol->izq,n,arbol); ///SI NO ESTA VACIO Y EL VALOR QUE INSERTEMOS
} ///ES MENOR A LA RAIZ POR EJEMPLO. Lo insertaremos
else{ ///En el lado iskierdo, ahora como es recursiva
insertarNodo(arbol->der,n,arbol); ///supondriamos que el parametro alla arriba
} ///ES arbol->der, mas el elemento y este lo evaluariamos
}
}
void mostrarArbol(Nodo *arbol,int cont){
if( arbol == NULL){ ///SI EL ARBOL ESTA VACIO LA FUNCION NO RETORNA NADA
return;
}
else{
mostrarArbol(arbol->der,cont+1);
for (int i=0; i<cont;i++){
cout<<" "; ///DEJA ESPACIO ENTRE LOS ELEMENTOS
}
cout<<arbol->dato<<endl;
mostrarArbol(arbol->izq,cont+1);
}
}
///eliminar elemento
void eliminar(Nodo *arbol,int n){
if(arbol == NULL){
return;
}
else if(n < arbol->dato){
eliminar(arbol->izq,n);
}else if(n > arbol->dato){
eliminar(arbol->der,n);
}
else{
///SI NO ES MAYOR EL VALOR
///NI TAMPOCO ES MENOR,NI VACIO
///EN ESE CASO EL ELEMENTO ES IGUAL
///ha sido encontrado
eliminarNodo(arbol);
///Esta funcion elimina el arbol una vez
///encontrado :T
}
}
void destruirNodo(Nodo *nodo){
nodo->izq = NULL;
nodo->der = NULL;
///DESVINCULAMOS AL NODO QUE SEPARAMOS DEL ARBOL DEL HIJO QUE TENIA
///este sea derecho o iskierdo
}
void eliminarNodo(Nodo *nodoEliminar){
///AQUI ES DONDE VALIDAREMOS SI EL NODO TIENE UN HIJO SOLO EN UNA DE LAS DIRECCIONES
///O SI TIENE DOS HIJOS O SI EL NODO ES HOJA, DEPENDIENDO DE ESTO ASI SERA LA ELIMINACION
///AUN SIGO PENSANDO QUE DE QUE MANERA ESTO SE RELACIONA CON UN GRAFO :V
///PERO BUENO XD.
///1-SI TIENE DOS SUB ARBOLES HIJOS DEBEMOS RECORRER LA PARTE DERECHA DE ESTE NODO
///QUE QUEREMOS MANDAR A LA GAVER, LUEGO DE ESTO TENEMOS QUE RECORRER LA PARTE ISKIERDA
///DE ESTA PARTE DERECHA, DEBEMOS RECORRER NUESTRO SUB ARBOL EN SUS TANTAS PARTES
///ISKIERDAS TENGA HASTA LA ULTIMA. LUEGO DEBEMOS REEMPLAZAR EL VALOR DE ESTA PARTE
///ISKIERDA POR EL VALOR DEL NODO QUE ELIMINEMOS. POR ULTIMO COMO AQUEL ISKIERDO
///QUE BUSCAMOS YA LO ESCRIBIMOS EN AQUEL NODO DE DONDE PARTIMOS, PROCEDEREMOS A BORRARLO
///PARA VALIDAR ESTA PRIMERA TEORIA VALIDAREMOS SI TIENE ISKIERDA Y DERECHA
if(nodoEliminar->izq && nodoEliminar->der){
Nodo *menor = minimo(nodoEliminar->der); ///y aqui invocamos a la funcion minimo
nodoEliminar->dato = menor->dato; ///REEMPLAZAMOS EL DATO DE LA PARTE MAS ISKIERDA QUE BUSCAMOS POR EL NODO
eliminarNodo(menor);
///AHORA BIEN PROCEDEREMOS A VALIDAR CUANDO TENGA UNO SOLO HIJO ISK O DER
}
else if(nodoEliminar->izq){
/// para eliminar un nodo que tiene un solo hijo iskierdo o derecho, necesi
///tamos que el nodo padre del nodo que eliminaremos apunte ahora al nodo hijo
///del nodo que queremos eliminar, y el nodo hijo apunte al nodo padre del nodo
///que eliminaremos de esta forma el nodo a eliminar quedaria sin referencia alguna y solo procedemos
///a suprimirlo
reemplazar(nodoEliminar,nodoEliminar->izq);
///ES AQUI LUEGO DE ESTA FUNCION, EN QUE EL NODO A ELIMINAR YA ESTA DESLIGADO TOTALMENTE
///AHORA AQUI LO QUE HAGO ES DESTRUIRLO CON LA SENTENCIA DELETE, PERO
///para eso creare una funcion.
destruirNodo(nodoEliminar);
}else if(nodoEliminar->der){
///EN CASO DE QUE TENGA HIJO DERECHO
reemplazar(nodoEliminar,nodoEliminar->der);
destruirNodo(nodoEliminar);
}else{
///SI UN NODO NO TIENE NINGUN HIJO
reemplazar(nodoEliminar,NULL);
destruirNodo(nodoEliminar);
}
}
///FUNCION QUE APLICO CUANDO EL NODO TIENE HIJO ISKIERDO Y DERECHO.
Nodo *minimo(Nodo *arbol){
if(arbol == NULL){
return NULL; ///SI ESTA VACIO RETORNAMOS NULL
}
if(arbol->izq){
return minimo(arbol->izq); ///NUEVAMENTE APLICAMOS RECURSIVIDAD PARA IR POR EL LADO MAS ISKIERDO POSIBLE
}
else{
return arbol; ///SI NO TIENE NODOS ISKIERDOS RETORNAMOS EL MISMO NODO QUE PASAMOS
}
}
void reemplazar(Nodo *arbol,Nodo *nuevonodo){
///FUNCION QUE INVOCO EN LA VALIDACION PARA ELIMINAR NODO CON UN SOLO HIJO
if(arbol->padre){
///El padre ahora apuntara al hijo del nodo que eliminaremos
///ahora asignaremos al nuevo hijo del padre.
if(arbol->dato == arbol->padre->izq->dato){
///DETERMINA SI EL NODO QUE TIENE UN SOLO HIJO ESTA EN LA PARTE ISKIERDA
arbol->padre->izq = nuevonodo;
}
else if(arbol->dato == arbol->padre->der->dato){
arbol->padre->der = nuevonodo;
}
}
if(nuevonodo){
///ASIGNAMOS AL NODO OSEA AL HIJO DEL NODO QUE QUEREMOS ELIMINAR
///SU NUEVO PADRE LEL
nuevonodo->padre = arbol->padre;
}
}