Arboles binarios en C++

   1: #include 

   2: #include 

   3: #include 

   4: #include 

   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<>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->datodato)

 122:      {

 123:      while(Aux->izq!=NULL&&Nuevo->datodato)

 124:         { Aux=Aux->izq;}

 125:        if(Nuevo->datodato&&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->datodato&&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(ddato)

 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->datodato)

 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->datodato)

 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->datodato)

 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<<" "<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<<" "<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<<" "<dato;

 305:   }

 306: }

 307: