Etiquetas

Arboles binarios en C++


Les dejo un viejo apunte de la universidad

Para descargar de clic en descargar

DESCARGAR
 
ARBOLES.CPP
 
   1: #include <stdio.h>
   2: #include <iostream.h>
   3: #include <conio.h>
   4: #include <stdlib.h>
   5:  
   6: typedef int tipodatoarbol;
   7: typedef struct nodo {
   8:    tipodatoarbol dato;
   9:    struct nodo *izq;
  10:     struct nodo *der;
  11: } tipoNodo;
  12: typedef tipoNodo *pNodo;
  13:  
  14: void insertar(pNodo *l,tipodatoarbol Dato);
  15: void inicializar(pNodo *l);
  16: void eliminar(pNodo *l, tipodatoarbol d);
  17: void preorden(pNodo *l);
  18: void inorden(pNodo *l);
  19: void postorden(pNodo *l);
  20:  void menu(pNodo *l);
  21: void inicio(pNodo *l);
  22: void agregar(pNodo *l);
  23: void quitar(pNodo *l);
  24:  
  25: void main()
  26: {
  27:   pNodo arbol;
  28:   menu(&arbol);
  29: }
  30:  
  31: void menu(pNodo *l)
  32: {  int op;
  33:    clrscr();
  34:    gotoxy(33,7);cout<<"ARBOL BINARIO";
  35:    gotoxy(32,9);cout<<"1) Inicializar";
  36:    gotoxy(32,11);cout<<"2) Insertar";
  37:    gotoxy(32,13);cout<<"3) Eliminar";
  38:    gotoxy(32,15);cout<<"4) Imprimir";
  39:    gotoxy(32,17);cout<<"5) Salir";
  40:    do{
  41:      gotoxy(33,19);cout<<"Opcion [ ] ";
  42:      gotoxy(41,19);cin>>op;
  43:    }while (op>5 || op<1);
  44:  
  45:    switch(op)
  46:    {
  47:      case 1:
  48:       inicio(l);
  49:       break;
  50:      case 2:
  51:       agregar(l);
  52:       break;
  53:      case 3:
  54:       quitar(l);
  55:       break;
  56:      case 4:
  57:       clrscr();
  58:       gotoxy(10,16);cout<<" Inorden: ";inorden(l);
  59:       gotoxy(10,17);cout<<" Preorden: ";preorden(l);
  60:       gotoxy(10,18);cout<<" Postorden: ";postorden(l);
  61:       getch();
  62:       menu(l);
  63:       break;
  64:      case 5:
  65:       exit(0);
  66:    }
  67:    getch();
  68: }
  69:  
  70: void inicio(pNodo *l)
  71: { clrscr();
  72:   inicializar(l);
  73:   menu(l);
  74: }
  75:  
  76: void agregar(pNodo *l)
  77: { clrscr();
  78:   int D;
  79:   //char opc='s';
  80:   gotoxy(30,20);cout<<"Insertar numero: "; cin>>D;
  81:     insertar(l,D);
  82:    // cout<<"Desea Insertar otro dato (S/N): "; cin>>opc;
  83:  // }while(opc=='s' ||opc=='S');
  84:   menu(l);
  85: }
  86: void quitar(pNodo *l)
  87: { clrscr();
  88:   int D;
  89:   //char opc='s';
  90:   //do{
  91:     gotoxy(30,20);cout<<"Numero a eliminar: "; cin>>D;
  92:     eliminar(l,D);
  93:     //gotoxy(12,8);cprintf("\nDesea Eliminar otro dato (S/N): "); cin>>opc;
  94:   //}while(opc=='s' ||opc=='S');
  95:   menu(l);
  96: }
  97:  
  98: // FUNCIONES BASICAS
  99: void inicializar(pNodo *l)
 100: {
 101:  *l=NULL;
 102: }
 103:  
 104: //insertar
 105: void insertar(pNodo *l,tipodatoarbol Dato){
 106:     pNodo Nuevo, Aux;
 107:     int b;
 108:     Nuevo=(pNodo)malloc(sizeof(tipoNodo));
 109:     Nuevo->dato= Dato;
 110:     Nuevo->der=NULL;
 111:     Nuevo->izq=NULL;
 112:     Aux=*l;
 113:      if (*l==NULL){
 114:      *l=Nuevo;
 115:     }
 116:     else if (*l!=NULL)
 117:     {
 118:      b=0;
 119:      while(b==0)
 120:     {
 121:     if(Nuevo->dato<=Aux->dato)
 122:      {
 123:      while(Aux->izq!=NULL&&Nuevo->dato<=Aux->dato)
 124:         { Aux=Aux->izq;}
 125:        if(Nuevo->dato<=Aux->dato&&Aux->izq==NULL)
 126:         {Aux->izq=Nuevo;
 127:         b=1;
 128:         }
 129:       else {if(Nuevo->dato>Aux->dato&&Aux->der==NULL)
 130:       {Aux->der=Nuevo;
 131:       b=1;
 132:         } }
 133:      }
 134:      else
 135:        if(Nuevo->dato>Aux->dato)
 136:      {
 137:  
 138:      while(Aux->der!=NULL&&Nuevo->dato>Aux->dato)
 139:         { Aux=Aux->der;}
 140:        if(Nuevo->dato<=Aux->dato&&Aux->izq==NULL)
 141:         {Aux->izq=Nuevo;
 142:         b=1;
 143:         }
 144:       else if(Nuevo->dato>Aux->dato&&Aux->der==NULL)
 145:       {Aux->der=Nuevo;
 146:       b=1;
 147:          }
 148:      } }
 149:       }
 150:  
 151: }
 152:  
 153: void eliminar(pNodo *l,tipodatoarbol d)
 154: {
 155:  if(*l==NULL)
 156:  {
 157:   gotoxy(30,20);cout<<"Arbol vacio";
 158:   getch();
 159:  }
 160:  else
 161:  {
 162:   pNodo aux,ant;
 163:   aux=*l;
 164:    while(aux->dato!=d&&(aux->izq!=NULL||aux->der!=NULL))
 165:    {
 166:    if(d<=aux->dato)
 167:    {
 168:     ant=aux;
 169:     aux=aux->izq;
 170:    }
 171:    else
 172:    {
 173:     ant=aux;
 174:     aux=aux->der;
 175:    }
 176:   }
 177:   if(aux->dato==d)
 178:   {
 179:    if(aux==*l&&aux->izq==NULL&&aux->der==NULL)
 180:    {
 181:     inicializar(l);
 182:    }
 183:    else
 184:    {
 185:     if(aux->izq!=NULL&&aux->der!=NULL)
 186:     {
 187:      ant=aux;
 188:      aux=aux->izq;
 189:      if(aux->der==NULL)
 190:      {
 191:       ant->dato=aux->dato;
 192:       ant->izq=aux->izq;
 193:      }
 194:      else
 195:      {
 196:       pNodo ant2;
 197:       while(aux->der!=NULL)
 198:       {
 199:        ant2=aux;
 200:        aux=aux->der;
 201:       }
 202:       ant->dato=aux->dato;
 203:       if(aux->izq==NULL)
 204:       {
 205:        ant2->der=NULL;
 206:       }
 207:       else
 208:       {
 209:        ant2->der=aux->izq;
 210:       }
 211:      }
 212:     free(aux);
 213:    }
 214:    else
 215:     if(aux->izq!=NULL||aux->der!=NULL)
 216:     {
 217:      if(aux->izq!=NULL)
 218:      {
 219:       if(aux->dato<=ant->dato)
 220:       {
 221:        if(aux==*l)
 222:     *l=aux->izq;
 223:        else
 224:     ant->izq=aux->izq;
 225:       }
 226:       else
 227:       {
 228:        if(aux==*l)
 229:     *l=aux->izq;
 230:        else
 231:        ant->der=aux->izq;
 232:       }
 233:      }
 234:      else
 235:      {
 236:       if(aux->dato<=ant->dato)
 237:       {
 238:        if(aux==*l)
 239:     *l=aux->der;
 240:        else
 241:     ant->izq=aux->der;
 242:       }
 243:       else
 244:       {
 245:        if(aux==*l)
 246:     *l=aux->der;
 247:        else
 248:     ant->der=aux->der;
 249:       }
 250:      }
 251:      free(aux);
 252:     }
 253:     else
 254:      if(aux->izq==NULL&&aux->der==NULL)
 255:      {
 256:       if (aux->dato<=ant->dato)
 257:        ant->izq=NULL;
 258:       else
 259:        ant->der=NULL;
 260:       free(aux);
 261:      }
 262:     }
 263:    }
 264:    else
 265:    {
 266:     gotoxy(30,20);cout<<"Numero no existente";
 267:     getch();
 268:    }
 269:  }
 270: }
 271: void preorden(pNodo *l){
 272:   pNodo Aux,*l2;
 273:   Aux=*l;
 274:   if(*l!=NULL){
 275:     cout<<" "<<Aux->dato;
 276:     *l2=Aux->izq;
 277:     preorden(l2);
 278:     *l2=Aux->der;
 279:     preorden(l2);
 280:   }
 281: }
 282:  
 283:  
 284: void inorden(pNodo *l){
 285:   pNodo Aux,*l2;
 286:   Aux=*l;
 287:   if(*l!=NULL){
 288:     *l2=Aux->izq;
 289:     inorden(l2);
 290:     cout<<" "<<Aux->dato;
 291:     *l2=Aux->der;
 292:     inorden(l2);
 293:   }
 294: }
 295:  
 296: void postorden(pNodo *l){
 297:   pNodo Aux,*l2;
 298:   Aux=*l;
 299:   if(*l!=NULL){
 300:     *l2=Aux->izq;
 301:     postorden(l2);
 302:     *l2=Aux->der;
 303:     postorden(l2);
 304:     cout<<" "<<Aux->dato;
 305:   }
 306: }
 307: 


Etiquetas:

Comentarios

Publicar un comentario

Entradas populares