Borrar nodo de un arbol

[karmi]

ayuda por favor, necesit borrar nodo de mi arbol...agradeceria me ayudasen, posteo mi codigo

Código (c) [Seleccionar] Expandir


#include <iostream.h>
#include <windows.h>


struct Nodo
{
Nodo *izq;
int dato;
Nodo *der;
};

class arbolbinario
{
private:
Nodo *raiz;
public:
arbolbinario()
{
raiz=NULL;
}
void insertar(int d)
{
Nodo *nuevo;
nuevo = new Nodo();
nuevo->izq= NULL;
nuevo->dato=d;
nuevo->der=NULL;

if (raiz==NULL)
{
raiz=nuevo;
}
else
{
Nodo *temp, *a;
int b=0;
temp = raiz;
a = NULL;
while(temp!=NULL)
{
a = temp;
if(nuevo->dato<temp->dato)
{
temp = temp->izq;
b=1;
}
else if (nuevo->dato>temp->dato)
{
temp = temp->der;
b=2;
}
}
if (b==1)
{
a->izq=nuevo;
}
else if (b==2)
{
a->der=nuevo;
}
}

}

void MostrarIn()
{
Nodo *temp;
temp = raiz;
MostrarInorden (temp);
}
void MostrarInorden(Nodo *T)
{
if (T!=NULL)
{
MostrarInorden(T->izq);
cout << T->dato << endl;
MostrarInorden(T->der);
}
}
void MostrarPr()
{
Nodo *temp;
temp = raiz;
MostrarPreorden (temp);
}
void MostrarPreorden(Nodo *T)
{
if (T!=NULL)
{
cout << T->dato << endl;
MostrarPreorden(T->izq);
MostrarPreorden(T->der);
}
}
void mostrarpost()
{
Nodo *temp;
temp=raiz;
mostrarpostorden(temp);

}
void mostrarpostorden(Nodo *T)
{
if (T!=NULL)
{
cout<<T->dato<<endl;
mostrarpostorden(T->der);
mostrarpostorden(T->izq);
}
}

};

int eliminar(int n)
*****ayuda

void main (void)
{
arbolbinario numeros;
int op, n;
do
{

cout << "A R B O L B I N A R I O" << endl<<endl;
cout << "1.- Insertar nodo"<< endl;
cout << "2.- Mostrar inorden"<< endl;
cout << "3.- Mostrar preorden"<< endl;
cout << "4.- Mostrar postorden"<< endl;
cout << "5.- eliminar numero"<< endl;
cout << "6.- Salir"<< endl << endl;

cout << "Elige una opcion-> ";
cin >> op;


switch(op)
{
case 1:
cout << "Introduce el numero: ";
cin >> n;
numeros.insertar(n);
break;
case 2:
cout << "Inorden"<<endl;
numeros.MostrarIn();
break;
case 3:
cout << "Preorden"<<endl;
numeros.MostrarPr();
break;
case 4:
cout << "Postorden"<<endl;
numeros.mostrarpost();

break;
case 5:
cout<<"introduce el numero a eliminar: "<<endl;
numeros.eliminar();
cout<<"numero eliminado"<<endl;

case 6:
default:


cout << "Bye!!!"<<endl;
}

}while(1);

}



[Bhrentox]

La verdad no he checado tu codigo pero espero te sirva este que hice hace ya bastante tiempo ytambien tiene la opcion de eliminar espero te sirva porque la verdad no recuerdo mucho de estas cosas pero espero te sirva de algo

Código (c) [Seleccionar] Expandir

#include<conio.h>
#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#include<dos.h>
struct nodo
{
int valor;
struct nodo*sig;
}*cab;
void insertar(int num);
void mostrar(void);
void BorrarTodo(void);
void Eliminar(int num);
void insertord(int num);


void main (void)
{
int op, num;
cab=NULL;
while(1)
{
clrscr();
printf("1.-Insertar un nodo.\n2.-Eliminar un nodo.\n3.-Mostrar\n4.-Insettar nodos en orden\n0.-Salir\n");
printf("\nElige una opcion: ");
scanf("%d",&op);
switch(op)
{
case 1:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertar(num);
break;
case 2:
printf("Dame el valor del nodo a eliminar: ");
scanf("%d",&num);
Eliminar(num);
break;
case 3:
mostrar();
break;
case 4:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertord(num);
break;
case 0:
BorrarTodo();
exit(0);//para usar exit debes declarar stdlib.h
break;
default:
printf("ERROR Opcion incorrecta");
getch();



}
getch();
}
}
void insertar(int num)
{
nodo *aux,*nuevo;
aux=cab;
nuevo=new nodo;
nuevo->valor=num;
nuevo->sig=NULL;
if(cab==NULL)
cab=nuevo;

else
{
while(aux->sig!=NULL)
aux=aux->sig;
aux->sig=nuevo;

}
}
void mostrar()
{
nodo *aux; //Aux es un apuntador
aux=cab; //En esta line aux toma la direccion de cab
while(aux!=NULL)
{
printf("%d, ",aux->valor);
aux=aux->sig;
}
}
void BorrarTodo(void)
{
nodo *aux;
aux=cab;
while(aux!=NULL)
{
cab=aux->sig;
delete aux;
aux=cab;
}
}

void Eliminar(int num)
{
nodo *aux,*aux2, *prev;
int c=0;
aux=cab;

while(c!=1)
{
if(aux->valor==num)
{
c=1;
}
else{
prev=aux;
aux=aux->sig;
}
}

if(c==1)
{
if(prev->sig==NULL)
{
cab=cab->sig;
delete aux;
}
else
{
aux2 = aux->sig;
prev->sig = aux2;
delete aux;
}
}


}



void insertord(int num)
{
nodo *aux,*nuevo,*aux2,*prev;
int c=0;
aux2=cab;
nuevo=new nodo;
// nuevo->valor=num;
while(aux2!=NULL)
{
if(aux2->valor>=num)
{

prev->sig=nuevo;
nuevo->valor=num;
nuevo->sig=aux2;
cab=prev;
aux2=NULL;
c=1;
}
prev=aux2;
aux2=aux2->sig;
}
if(aux2==NULL)
if(c==0)
{
insertar(num);
}
else
{
delete aux2;
}
}

[do-while]

¡Buenas!

Para borrar un nodo, tienes que seguir los siguientes pasos.

1- Si es un nodo hoja, lo eliminas y pones a NULL el puntero del padre que aputaba a este.

2- Si es un nodo con un solo hijo, el hijo sera el nodo de reemplazo.

3- Si es un nodo con dos hijos, el nodo de reemplazo puede ser o bien el menor de los nodos mayores que el que quieres borrar (el nodo mas a la izquierda del subarbol derecho), ya que este sera mayor que los de la izquierda pero menor que cualquier otro de la derecha, o sino puedes utilizar el mayor de los nodos menores (el nodo mas a la derecha en el subarbol izquierdo) ya que este sera mayor que todos los menores que el nodo que quieres sustituir, pero menor que los mayores. 

3.1 - Si utilizas el menor de los nodos mayores, y este tiene un subarbol derecho (el subarbol de los valores mayores que el nodo de reemplazo), tendras que recorrerlo por la derecha hasta alcanzar el mayor valor. Al ser el mayor valor del arbol que tiene como raiz el nodo de reemplazo, este valor seguira siendo mayor que el valor que quieres reemplazar. Pero al partir del valor mas pequeño entre los valores mayores, sera menor que cualquier otro valor del subarbol derecho que sea mayor que el del nodo de reemplazo, por lo tanto tendras que colgar el subarbol derecho del nodo que quieres reemplazar como subarbol derecho del mayor nodo mayor que el menor de los nodos mayores. Como hemos cogido como referencia el menor de los nodos mayores, el subarbol izquierdo de dicho nodo sera nulo, y por lo tanto puedes colgar el subarbol izquierdo del nodo quieres eliminar del nodo izquierdo del menor de los nodos mayores que el que quieres eliminar. Ahora que ya tienes construido el arbol con raiz el nodo de reemplazo de forma correcta, ya puedes eliminar el nodo que querias eliminar, y el puntero del padre que señalaba al nodo que has eliminado deberas apuntarlo al nodo de reemplazo. Evidentemente, si quieres eliminar el nodo raiz, no tendras padre, pero esto no supone ningun problema, ya que el nodo de reemplazo, por como hemos hecho las operaciones de sustitucion del nodo que se quiere eliminar por el de reemplazo, cumple todas la propiedades para ser el nuevo nodo raiz.

3.2- Si eliges como nodo de reemplazo el mayor de los nodos menores, los pasos que tendras que seguir son los anteriores, cambiando mayor por menor y aplicando sentido comun.

Ya ves que explicado es cosa de  , pero en canto te pongas a traducirlo a codigo, lo veras mas claro y lo asimilaras mejor.

¡Saludos!