Es interesante este algoritmo para los ordenamientos en arboles y busquedas.
ATTE : ANTON RAMIREZ , LEONARDO VLADIMIR (ALUMNO UNI)
Código:
using namespace std;
struct NODO
{
NODO *izq;
int info;
NODO *der;
int FE;
};
void InsercionBalanceado(NODO **nodocabeza, bool *BO, int infor);
void Busqueda(NODO *nodo,int infor);
void Preorden(NODO *);
void Inorden(NODO *);
void Postorden(NODO *);
void Restructura1(NODO **nodocabeza, bool *BO);
void Restructura2(NODO **nodocabeza, bool *BO);
void Borra(NODO **aux1, NODO **otro1, bool *BO);
void EliminacionBalanceado(NODO **nodocabeza, bool *BO, int infor);
int Menu();
int main()
{
int Opcion;
int elemento;
NODO *borrado, *raiz;
raiz=NULL;
system("cls");
Opcion = Menu();
bool inicio;
while (Opcion)
{
system("cls");
switch(Opcion)
{
case 1:
cout<<"\nRUTINA DE INSERCION\n\n";
cout<<"\nIngrese elemento a insertar: ";
cin>>elemento;
inicio=false;
InsercionBalanceado(&raiz, &inicio, elemento);
break;
case 2:
cout<<"\nRUTINA DE BUSQUEDA\n\n";
cout<<"\nIngrese elemento a buscar: ";
cin>>elemento;
Busqueda(raiz, elemento);
break;
case 3:
printf("\nRECORRIDO PREORDEN\n\n");
printf("\nEl arbol es: \n\n");
Preorden(raiz);
printf("\n\n");
system("pause");
break;
case 4:
printf("\nRECORRIDO INORDEN\n\n");
printf("\nEl arbol es: \n\n");
Inorden(raiz);
printf("\n\n");
system("pause");
break;
case 5:
printf("\nRECORRIDO POSTORDEN\n\n");
printf("\nEl arbol es: \n\n");
Postorden(raiz);
printf("\n\n");
system("pause");
break;
case 6:
cout<<"\nRUTINA DE ELIMINACION\n\n";
cout<<"\nIngrese elemento a eliminar: ";
cin>>elemento;
inicio=false;
EliminacionBalanceado(&raiz, &inicio, elemento);
break;
case 0: exit(0);
}
Opcion = Menu();
}
system("pause");
return(0);
}
int Menu()
{
int Op;
do{
system("cls");
cout<<"\n\n\t ARBOL BINARIO BALANCEADO \n\n";
cout<<"\t1) Insertar\n";
cout<<"\t2) Buscar\n";
cout<<"\t3) PreOrden\n";
cout<<"\t4) InOrden\n";
cout<<"\t5) PostOrden\n";
cout<<"\t6) Eliminacion\n";
cout<<"\t0) Salir\n\n";
printf("Digite su opcion ---> ");
cin>>Op;
}while(Op<0 || Op>7);
return (Op);
}
void InsercionBalanceado(NODO **nodocabeza, bool *BO, int infor)
{
NODO *nodo, *nodo1, *nodo2;
nodo=*nodocabeza;
if(nodo!=NULL)
{
if( infor < nodo->info )
{
InsercionBalanceado(&(nodo->izq),BO,infor);
if( *BO == true )
{
switch(nodo->FE)
{
case 1: nodo->FE=0;
*BO=false;
break;
case 0: nodo->FE=-1;
break;
case -1: nodo1=nodo->izq;//reestructuracion del arbol
if (nodo1->FE<=0)
{ //Rotacion II
nodo->izq=nodo1->der;
nodo1->der=nodo;
nodo->FE=0;
nodo=nodo1;
}
else
{ //Rotacion ID
nodo2=nodo1->der;
nodo->izq=nodo2->der;
nodo2->der=nodo;
nodo1->der=nodo2->izq;
nodo2->izq=nodo1;
if (nodo2->FE==-1)
nodo->FE=1;
else
nodo->FE=0;
if (nodo2->FE==1)
nodo1->FE=-1;
else
nodo1->FE=0;
nodo=nodo2;
}
nodo->FE=0;
*BO=false;
break;
}
}
}
else
{
if( infor > nodo->info )
{
InsercionBalanceado(&(nodo->der),BO,infor);
if( *BO == true )
{
switch(nodo->FE)
{
case -1: nodo->FE=0;
*BO=false;
break;
case 0: nodo->FE=1;
break;
case 1: nodo1=nodo->der;//reestructuracion del arbol
if (nodo1->FE>=0)
{ //Rotacion DD
nodo->der=nodo1->izq;
nodo1->izq=nodo;
nodo->FE=0;
nodo=nodo1;
}
else
{ //Rotacion DI
nodo2=nodo1->izq;
nodo->der=nodo2->izq;
nodo2->izq=nodo;
nodo1->izq=nodo2->der;
nodo2->der=nodo1;
if (nodo2->FE==1)
nodo->FE=-1;
else
nodo->FE=0;
if (nodo2->FE==-1)
nodo1->FE=1;
else
nodo1->FE=0;
nodo=nodo2;
}
nodo->FE=0;
*BO=false;
break;
}
}
}
else
{
cout<<"\nEl nodo ya se encuentra en el arbol\n"<<endl;
system("pause");
}
}
}
else
{
//NODO *otro;
nodo = new(NODO);
nodo->izq=NULL;
nodo->der=NULL;
nodo->info=infor;
nodo->FE=0;
*BO=true;
}
*nodocabeza=nodo;
}
void Busqueda(NODO *nodo,int infor)
{
if(nodo!=NULL)
{
if( infor < nodo->info )
{
Busqueda(nodo->izq,infor);
}
else
{
if( infor > nodo->info )
{
Busqueda(nodo->der,infor);
}
else
{
cout<<"\nEl nodo SI se encuentra en el arbol\n"<<endl;
system("pause");
}
}
}
else
{
cout<<"\nEl nodo NO se encuentra en el arbol\n"<<endl;
system("pause");
}
}
void Preorden(NODO *nodo)
{
if (nodo!=NULL)
{
cout<<nodo->info<<"\t";
Preorden(nodo->izq);
Preorden(nodo->der);
}
}
void Inorden(NODO *nodo)
{
if (nodo!=NULL)
{
Inorden(nodo->izq);
cout<<nodo->info<<"\t";
Inorden(nodo->der);
}
}
void Postorden(NODO *nodo)
{
if (nodo!=NULL)
{
Postorden(nodo->izq);
Postorden(nodo->der);
cout<<nodo->info<<"\t";
}
}
/*void Eliminacion(NODO **nodocabeza, int infor)
{
NODO *nodo, *otro, *aux, *aux1;
nodo=*nodocabeza;
if(nodo!=NULL)
{
if( infor < nodo->info )
{
Eliminacion(&(nodo->izq),infor);
}
else
{
if( infor > nodo->info )
{
Eliminacion(&(nodo->der),infor);
}
else
{
otro=nodo;
if (otro->der==NULL)
{
nodo=otro->izq;
}
else
{
if (otro->izq==NULL)
{
nodo=otro->der;
}
else
{
aux=otro->izq;
aux1=aux;
while(aux->der!=NULL)
{
aux1=aux;
aux=aux->der;
}
otro->info=aux->info;
otro=aux;
aux1->der=aux->izq;
}
}
}
}
delete(otro);
}
else
{
cout<<"\nEl nodo NO se encuentra en el arbol\n"<<endl;
system("pause");
}
*nodocabeza=nodo;
}
*/
void Restructura1(NODO **nodocabeza, bool *BO)
{
NODO *nodo, *nodo1, *nodo2;
nodo=*nodocabeza;
if ( *BO==true )
{
switch(nodo->FE){
case -1: nodo->FE=0;
break;
case 0: nodo->FE=1;
*BO=false;
break;
case 1: //reestructuracion del arbol
nodo1=nodo->der;
if(nodo1->FE>=0){ //rotacion DD
nodo->der=nodo1->izq;
nodo1->izq=nodo;
switch (nodo1->FE){
case 0: nodo->FE=1;
nodo1->FE=-1;
*BO=false;
break;
case 1: nodo->FE=0;
nodo1->FE=0;
*BO=false;
break;
}
nodo=nodo1;
}
else
{ //Rotacion DI
nodo2=nodo1->izq;
nodo->der=nodo2->izq;
nodo2->izq=nodo;
nodo1->izq=nodo2->der;
nodo2->der=nodo1;
if (nodo2->FE==1)
nodo->FE=-1;
else
nodo->FE=0;
if (nodo2->FE==-1)
nodo1->FE=1;
else
nodo1->FE=0;
nodo=nodo2;
nodo2->FE=0;
}
break;
}
}
*nodocabeza=nodo;
}
void Restructura2(NODO **nodocabeza, bool *BO)
{
NODO *nodo, *nodo1, *nodo2;
nodo=*nodocabeza;
if ( *BO==true )
{
switch(nodo->FE)
{
case 1: nodo->FE=0;
break;
case 0: nodo->FE=-1;
*BO=false;
break;
case -1: //reestructuracion del arbol
nodo1=nodo->izq;
if(nodo1->FE<=0)
{ //rotacion II
nodo->izq=nodo1->der;
nodo1->der=nodo;
switch (nodo1->FE)
{
case 0: nodo->FE=-1;
nodo1->FE=1;
*BO=false;
break;
case -1: nodo->FE=0;
nodo1->FE=0;
*BO=false;
break;
}
nodo=nodo1;
}
else
{ //Rotacion ID
nodo2=nodo1->der;
nodo->izq=nodo2->der;
nodo2->der=nodo;
nodo1->der=nodo2->izq;
nodo2->izq=nodo1;
if (nodo2->FE==-1)
nodo->FE=1;
else
nodo->FE=0;
if (nodo2->FE==1)
nodo1->FE=-1;
else
nodo1->FE=0;
nodo=nodo2;
nodo2->FE=0;
}
break;
}
}
*nodocabeza=nodo;
}
void Borra(NODO **aux1, NODO **otro1, bool *BO)
{
NODO *nodo, *aux, *otro;
aux=*aux1;
otro=*otro1;
if ( aux->der!=NULL )
{
Borra(&(aux->der),&otro,BO);
Restructura2(&aux,BO);
}
else
{
otro->info=aux->info;
aux=aux->izq;
*BO=true;
}
*aux1=aux;
*otro1=otro;
}
void EliminacionBalanceado(NODO **nodocabeza, bool *BO, int infor)
{
NODO *nodo, *otro;
nodo=*nodocabeza;
if(nodo!=NULL)
{
if( infor < nodo->info )
{
EliminacionBalanceado(&(nodo->izq),BO,infor);
Restructura1(&nodo,BO);
}
else
{
if( infor > nodo->info )
{
EliminacionBalanceado(&(nodo->der),BO,infor);
Restructura2(&nodo,BO);
}
else
{
otro=nodo;
if (otro->der==NULL)
{
nodo=otro->izq;
*BO=true;
}
else
{
if (otro->izq==NULL)
{
nodo=otro->der;
*BO=true;
}
else
{
Borra(&(otro->izq),&otro,BO);
Restructura1(&nodo,BO);
delete(otro);
}
}
}
}
}
else
{
cout<<"\nEl nodo NO se encuentra en el arbol\n"<<endl;
system("pause");
}
*nodocabeza=nodo;
}