Borrar
La operación de borrado no es tan sencilla como las de búsqueda e inserción. Existen varios casos a tener en consideración:
* Borrar un nodo sin hijos o nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.
* Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.
* Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho).
Ejemplo
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
struct Nodo{
int dato;
Nodo *der;
Nodo *izq;
Nodo *padre;
};
//Prototipos
void menu();
Nodo *crearNodo(int,Nodo *);
void insertarNodo(Nodo *&,int,Nodo *);
void mostrarArbol(Nodo *,int);
bool busqueda(Nodo *,int);
void preOrden(Nodo *);
void inOrden(Nodo *);
void postOrden(Nodo *);
void borrar(Nodo *,int);
void borrarNodo(Nodo *);
Nodo *minimo(Nodo *);
void reemplazar(Nodo *,Nodo *);
void destruirNodo(Nodo *);
Nodo *arbol = NULL;
int main(){
menu();
getch();
return 0;
}
//Funcion de menu
void menu(){
int dato,opcion,contador=0;
do{
cout<<"\t.:MENU:."<<endl;
cout<<"1. Insertar un nuevo nodo"<<endl;
cout<<"2. Mostrar el arbol completo"<<endl;
cout<<"3. Buscar un elemento en el arbol"<<endl;
cout<<"4. Recorrer el arbol en PreOrden"<<endl;
cout<<"5. Recorrer el arbol en InOrden"<<endl;
cout<<"6. Recorrer el arbol en PostOrden"<<endl;
cout<<"7. Borrar un nodo del arbol"<<endl;
cout<<"8. Salir"<<endl;
cout<<"Opcion: ";
cin>>opcion;
switch(opcion){
case 1: cout<<"\nDigite un numero: ";
cin>>dato;
insertarNodo(arbol,dato,NULL); //Insertamos un nuevo nodo
cout<<"\n";
system("pause");
break;
case 2: cout<<"\nMostrando el arbol completo:\n\n";
mostrarArbol(arbol,contador);
cout<<"\n";
system("pause");
break;
case 3: cout<<"\nDigite el elemento a buscar: ";
cin>>dato;
if(busqueda(arbol,dato) == true){
cout<<"Elemento "<<dato<<" a sido encontrado en el arbol\n";
}
else{
cout<<"\nElemento no encontrado \n";
}
cout<<"\n";
system("pause");
break;
case 4: cout<<"\nRecorrido en preOrden: ";
preOrden(arbol);
cout<<"\n\n";
system("pause");
break;
case 5: cout<<"\nRecorrido en InOrden: ";
inOrden(arbol);
cout<<"\n\n";
system("pause");
break;
case 6: cout<<"\nRecorrido en PostOrden: ";
postOrden(arbol);
cout<<"\n\n";
system("pause");
break;
case 7: cout<<"\nDigite el numero a borrar: ";
cin>>dato;
borrar(arbol,dato);
cout<<"\n";
system("pause");
break;
}
system("cls");
}while(opcion != 8);
}
//Funcion para crear un nuevo nodo
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;
return nuevo_nodo;
}
//Funcion para insertar elementos en el arbol
void insertarNodo(Nodo *&arbol,int n,Nodo *padre){
if(arbol == NULL){ //Si el arbol esta vacio
Nodo *nuevo_nodo = crearNodo(n,padre);
arbol = nuevo_nodo;
}
else{ //Si el arbol tiene un nodo o mas
int valorRaiz = arbol->dato; //Obtenemos el valor de la raiz
if(n < valorRaiz){ //Si ele elemento es menor a la raiz, insertamos en izq
insertarNodo(arbol->izq,n,arbol);
}
else{//Si el elemento es mayor a la raiz, insertamos en der
insertarNodo(arbol->der,n,arbol);
}
}
}
//Funcion para mostrar el arbol completo
void mostrarArbol(Nodo *arbol,int cont){
if(arbol == NULL){ //Si el arbol esta vacio
return;
}
else{
mostrarArbol(arbol->der,cont+1);
for(int i=0;i<cont;i++){
cout<<" ";
}
cout<<arbol->dato<<endl;
mostrarArbol(arbol->izq,cont+1);
}
}
//Funcion para buscar un elemento en el arbol
bool busqueda(Nodo *arbol,int n){
if(arbol == NULL){ //Si el arbol esta vacio
return false;
}
else if(arbol->dato == n){//Si el nodo es igual al elemento
return true;
}
else if(n < arbol ->dato){
return busqueda(arbol->izq,n);
}
else{
return busqueda(arbol->der,n);
}
}
//Funcion para recorrido en profundidad - PreOrden
void preOrden(Nodo *arbol){
if(arbol == NULL){ //Si el arbol esta vacio
return;
}
else{
cout<<arbol->dato<<" - ";
preOrden(arbol->izq);
preOrden(arbol->der);
}
}
//Funcion para recorrido en profundidad - InOrden
void inOrden(Nodo *arbol){
if(arbol == NULL){
return;
}
else{
inOrden(arbol->izq);
cout<<arbol->dato<<" - ";
inOrden(arbol->der);
}
}
//Funcion para recorrido en profundidad - PostOrden
void postOrden(Nodo *arbol){
if(arbol == NULL){//Si el arbol esta vacio
return;
}
else{
postOrden(arbol->izq);
postOrden(arbol->der);
cout<<arbol->dato<<" - ";
}
}
//borrar un nodo del arbol
void borrar(Nodo *arbol,int n){
if(arbol == NULL){//Si el arbol esta vacio
return;
}
else if(n < arbol->dato){//Si el valor es menor
borrar(arbol->izq,n);
}
else if(n > arbol->dato){//Si el valor es mayor
borrar(arbol->der,n);
}
else{//Si ya encontraste el valor
borrarNodo(arbol);
}
}
//Funcion para determinar el nodo mas izq posible
Nodo* minimo(Nodo *arbol){
if(arbol == NULL){//Si el arbol esta vacio
return NULL;
}
if(arbol->izq){//Si tiene hijo izq
return minimo(arbol->izq);//buscamos la parte mas izq posible
}
else{//Si no tiene hijo izq
return arbol;//retornamos el mismo nodo
}
}
//Funcion para reemplazar dos nodos
void reemplazar(Nodo *arbol,Nodo *nuevoNodo){
if(arbol->padre){
//arbol->padre hay que asignarle su nuevo hijo
if(arbol->dato == arbol->padre->izq->dato){
arbol->padre->izq = nuevoNodo;
}
else if(arbol->dato == arbol->padre->der->dato){
arbol->padre->der = nuevoNodo;
}
}
if(nuevoNodo){
//Procedemos a asignarle su nuevo padre
nuevoNodo->padre = arbol->padre;
}
}
//Funcion para destruir un nodo
void destruirNodo(Nodo *nodo){
nodo->izq = NULL;
nodo->der = NULL;
delete nodo;
}
//Funcion para borrar el nodo encontrado
void borrarNodo(Nodo *nodoBorrar){
if(nodoBorrar->izq && nodoBorrar->der){//Si el nodo tiene hijo izq y der
Nodo *menor = minimo(nodoBorrar->der);
nodoBorrar->dato = menor->dato;
borrarNodo(menor);
}
else if(nodoBorrar->izq){//Si tiene hijo izq
reemplazar(nodoBorrar,nodoBorrar->izq);
destruirNodo(nodoBorrar);
}
else if(nodoBorrar->der){
reemplazar(nodoBorrar,nodoBorrar->der);
destruirNodo(nodoBorrar);
}
else{//No tiene hijos
reemplazar(nodoBorrar,NULL);
destruirNodo(nodoBorrar);
}
}
Video
https://youtu.be/scnuZa-baYw
No hay comentarios.:
Publicar un comentario