Arbol Binario C++ eliminar Nodos

De nuevo ¡Que tal! este es un algoritmo donde elimina nodos de un árbol binario, hecho c++, si tienes algún problema no dudes en postear, aun no he tratado la eliminación de Nodo Padre.

#include <iostream>
#include <cstdlib>

using namespace std;

class ArbolBinario
{
private:
struct NodoArbol
{
NodoArbol* izquierda;
NodoArbol* derecho;
int Dato;
};
NodoArbol* Raiz;

public:
ArbolBinario()
{
Raiz = NULL;
}

bool VacioAB() const { return Raiz==NULL; }
void MostrarInOrden();
void InOrden(NodoArbol*);
void MostrarPreOrden();
void PreOrden(NodoArbol*);
void MostrarPostOrden();
void PostOrden(NodoArbol*);
void Ingresar(int);
void EliminarHi(int);
};
// d es el elemento que ingresamos
// Elemntos menores a la izquierda
// Elemntos grandes a la derecha
void ArbolBinario::Ingresar(int d)
{
NodoArbol* t = new NodoArbol;
NodoArbol* PadreAB;
t->Dato = d;
t->izquierda = NULL;
t->derecho = NULL;
PadreAB = NULL;

//nuevo arbol
if(VacioAB()) Raiz = t;
else
{
//Todo lo que Ingresaramos son nodos de la hoja.
NodoArbol* NoHo;
NoHo = Raiz;
// Encuentra los padres de cada hoja, en este caso si se elimina un padre probocara un
// error ya que no se puede eliminar un padre hasta eliminar el hijo.
while(NoHo)
{
PadreAB = NoHo;
if(t->Dato > NoHo->Dato) NoHo = NoHo->derecho;
else NoHo = NoHo->izquierda;
}

if(t->Dato < PadreAB->Dato)
PadreAB->izquierda = t;
else
PadreAB->derecho = t;
}
}

void ArbolBinario::EliminarHi(int d)
{
//Buscamos el elemento(numero)
bool SiEncontro = false;
if(VacioAB())
{
cout<<«El Arbol Binario Esta limpio! «<<endl;
return;
}

NodoArbol* NoHo;
NodoArbol* PadreAB;
NoHo = Raiz;

while(NoHo != NULL)
{
if(NoHo->Dato == d)
{
SiEncontro = true;
break;
}
else
{
PadreAB = NoHo;
if(d>NoHo->Dato) NoHo = NoHo->derecho;
else NoHo = NoHo->izquierda;
}
}
if(!SiEncontro)
{
cout<<«Dato no se encontro»<<endl;
return;
}

// casos:
// 1. Estamos eliminando un nodo hoja
// 2. Estamos eliminando un nodo con un solo hijo
// 3. estamos eliminando un nodo con 2 hijos
// Nodo con uno de los hijos

if((NoHo->izquierda == NULL && NoHo->derecho != NULL)|| (NoHo->izquierda != NULL && NoHo->derecho == NULL))
{
if(NoHo->izquierda == NULL && NoHo->derecho != NULL)
{
if(PadreAB->izquierda == NoHo)
{
PadreAB->izquierda = NoHo->derecho;
delete NoHo;
}
else
{
PadreAB->derecho = NoHo->derecho;
delete NoHo;
}
}
else //Izquierda hijo esté presente, no hay hijo derecho.
{
if(PadreAB->izquierda == NoHo)
{
PadreAB->izquierda = NoHo->izquierda;
delete NoHo;
}
else
{
PadreAB->derecho = NoHo->izquierda;
delete NoHo;
}
}
return;
}

//Nodo u hoja
if( NoHo->izquierda == NULL && NoHo->derecho == NULL)
{
if(PadreAB->izquierda == NoHo) PadreAB->izquierda = NULL;
else PadreAB->derecho = NULL;
delete NoHo;
return;
}

//Nodo con 2 hijos
// reemplazar el nodo con menor valor en el subárbol derecho
if (NoHo->izquierda != NULL && NoHo->derecho != NULL)
{
NodoArbol* chkr;
chkr = NoHo->derecho;
if((chkr->izquierda == NULL) && (chkr->derecho == NULL))
{
NoHo = chkr;
delete chkr;
NoHo->derecho = NULL;
}
else // Si hijo derecho tiene hijos
{
//si es hijo derecho del nodo tiene un hijo izquierdo
//Mover todo el camino a la izquierda para localizar elemento más pequeño

if((NoHo->derecho)->izquierda != NULL)
{
NodoArbol* lNoHo;
NodoArbol* lNoHop;
lNoHop = NoHo->derecho;
lNoHo = (NoHo->derecho)->izquierda;
while(lNoHo->izquierda != NULL)
{
lNoHop = lNoHo;
lNoHo = lNoHo->izquierda;
}
NoHo->Dato = lNoHo->Dato;
delete lNoHo;
lNoHop->izquierda = NULL;
}
else
{
NodoArbol* Temporal;
Temporal = NoHo->derecho;
NoHo->Dato = Temporal->Dato;
NoHo->derecho =Temporal->derecho;
delete Temporal;
}

}
return;
}

}

void ArbolBinario::MostrarInOrden()
{
InOrden(Raiz);
}

void ArbolBinario::InOrden(NodoArbol* p)
{
if(p != NULL)
{
if(p->izquierda) InOrden(p->izquierda);
cout<<» «<<p->Dato<<» «;
if(p->derecho) InOrden(p->derecho);
}
else return;
}

void ArbolBinario::MostrarPreOrden()
{
PreOrden(Raiz);
}

void ArbolBinario::PreOrden(NodoArbol* p)
{
if(p != NULL)
{
cout<<» «<<p->Dato<<» «;
if(p->izquierda) PreOrden(p->izquierda);
if(p->derecho) PreOrden(p->derecho);
}
else return;
}

void ArbolBinario::MostrarPostOrden()
{
PostOrden(Raiz);
}

void ArbolBinario::PostOrden(NodoArbol* p)
{
if(p != NULL)
{
if(p->izquierda) PostOrden(p->izquierda);
if(p->derecho) PostOrden(p->derecho);
cout<<» «<<p->Dato<<» «;
}
else return;
}

int main()
{
//Creamos y accedemos al clase ArbolBinario
ArbolBinario ChocCac;
int menu;
int ingresardato,eliminarhijo;
while(1)
{
cout<<endl<<endl;
cout<<» Arbol Binario «<<endl;
cout<<» —————————– «<<endl;
cout<<» 1. Ingresarar/crear «<<endl;
cout<<» 2. Recorrido In-Orden»<<endl;
cout<<» 3. Recorrido Pre-Orden»<<endl;
cout<<» 4. Recorrido Post-Orden»<<endl;
cout<<» 5. Eliminar Hijo (elimina todo) «<<endl;
cout<<» 6. Salir «<<endl;
cout<<«Que desea Hacer? : «;
cin>>menu;
switch(menu)
{
case 1 : cout<<«Numero que desea Ingresarar: «;
cin>>ingresardato;
ChocCac.Ingresar(ingresardato);
break;
case 2 : cout<<endl;
cout<<» Recorrido In-Orden»<<endl;
cout<<» ——————-«<<endl;
ChocCac.MostrarInOrden();
break;
case 3 : cout<<endl;
cout<<» Recorrido Pre-Orden»<<endl;
cout<<» ——————-«<<endl;
ChocCac.MostrarPreOrden();
break;
case 4 : cout<<endl;
cout<<» Recorrido Post-Orden»<<endl;
cout<<» ——————–«<<endl;
ChocCac.MostrarPostOrden();
break;
case 5 : cout<<«Escribe el hijo que desea eliminar \nSi pone un padre terminar el programa\nSi pone un hijo empezara con el vaciado del arbol\nPrevio e haberlo llennado\nIngrese el Hijo a Eliminar: «;
cin>>eliminarhijo;
ChocCac.EliminarHi(eliminarhijo);
break;
case 6 :
return 0;

}
}
}

• Tweet
• Pin It