elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Implementaciones Basicas en un Arbol Binario ....
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Implementaciones Basicas en un Arbol Binario ....  (Leído 2,488 veces)
ANTÓN RAMIREZ

Desconectado Desconectado

Mensajes: 10


Ver Perfil
Implementaciones Basicas en un Arbol Binario ....
« en: 14 Diciembre 2010, 22:11 pm »

 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:
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]


« Última modificación: 7 Enero 2011, 17:09 pm por ANTÓN RAMIREZ » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Altura de arbol binario
Java
l337* 4 33,602 Último mensaje 5 Diciembre 2009, 13:08 pm
por imnohacker
Arbol binario Ejemplo
.NET (C#, VB.NET, ASP)
S1dD3xt35 0 6,352 Último mensaje 21 Abril 2010, 07:18 am
por S1dD3xt35
arbol binario
Programación C/C++
karmi 2 3,048 Último mensaje 14 Diciembre 2010, 22:08 pm
por ANTÓN RAMIREZ
Python y sus diferentes implementaciones
Scripting
DISCIPULUS 1 1,697 Último mensaje 29 Mayo 2017, 18:44 pm
por LaThortilla (Effort)
Malas implementaciones del estándar RCS están abriendo la puerta a grandes ...
Noticias
wolfbcn 0 236 Último mensaje 30 Noviembre 2019, 00:58 am
por wolfbcn
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines