Implementaciones Basicas en un Arbol Binario ....

[ANTÓN RAMIREZ]

 Arbol Binario Balanceado implementado con el pseudocodigo del libro de Estructura de Datos de Osvaldo Cairo. Les recomiendo ese libro .
Es interesante este algoritmo para los ordenamientos en arboles y busquedas.


ATTE : ANTON RAMIREZ , LEONARDO VLADIMIR  (ALUMNO UNI)

Código [Seleccionar] Expandir

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;
}[/color]