Задачи по C/С++ - [605] :: Прикладное программирование

Код:

#define TAMVECTOR 100
#include <stdio.h>
#include <conio.h>
#include <IOSTREAM.H>
#include <stdlib.h>

//Se define la estructura de arbol
typedef struct Arbol{ //para crear nombres para tipos mas complejos como struct
int Dato;
Arbol *Izq;
Arbol *Der;
} Arbol;

/*******************************************/
// DEFINICION DE UNA ESTRUCTURA DE PILA para el PREORDEN
typedef struct{
Arbol* vector[TAMVECTOR];
int nelem;
} tPila;

void crearPila(tPila *pila){
    pila->nelem = 0;
}

void push(tPila *pila,Arbol *put){
    pila->vector[pila->nelem] = put;
    pila->nelem++;
}

Arbol* pop(tPila *pila){
    pila->nelem--;
    return pila->vector[pila->nelem];

}

int pilavacia(tPila *pila){
    if (pila->nelem == 0) return 1;
    else return 0;
}
/*********************************************/
/*******************************************/
// DEFINICION DE UNA ESTRUCTURA DE COLA para INORDEN, POSTORDEN Y NIVELES
typedef struct{
Arbol* vector[TAMVECTOR];
int ind_izq;
int ind_der;
} tCola;

void crearCola(tCola *cola){
    cola->ind_izq = 0;
    cola->ind_der = -1;
}

void encolar(tCola *cola,Arbol *put){
    cola->ind_der++;
    cola->vector[cola->ind_der] = put;
}

Arbol* desencolar(tCola *cola){
    cola->ind_izq++;
    return cola->vector[cola->ind_izq-1];
}

int colavacia(tCola *cola){
    if (cola->ind_der < cola->ind_izq) return 1;
    else return 0;
}
/*********************************/

void Menu(void)
{
printf("\nEscoja su opcion:\n\n");
printf("1. Insertar.\n");
printf("2. Eliminar.\n");
printf("3. Buscar.\n");
printf("4. Inorden.\n");
printf("5. PostOrden.\n");
printf("6. Preorden.\n");
printf("7. niveles.\n");

printf("9. Free.\n");

printf("8. Salir.\n");
printf("-> ");
}

void PreOrden(struct Arbol *a){
tPila pila;
Arbol *aux;

if (a != NULL) {
     crearPila(&pila);
     push(&pila, a);
     while (pilavacia(&pila) == 0) {
        aux = pop(&pila);
        printf("%d\n",aux->Dato);
        if (aux->Der != NULL) push(&pila, aux->Der);
        if (aux->Izq!= NULL) push(&pila, aux->Izq);
     }
    }
}

void PostOrden(struct Arbol *a){

// Esta implementacion es valido cuando los valores del arbol son todos positivos!
    tPila pila;
    Arbol *temp;

    if (a == NULL)return;

    temp = a;
    crearPila(&pila);
    push(&pila,NULL);

    int salir = 0;

    while (salir == 0){
        while (temp != NULL){
            push(&pila, temp);
            if (temp->Der != NULL){
                temp->Der->Dato = -temp->Der->Dato;
                push(&pila, temp->Der);
            }
            temp = temp->Izq;
        }
        temp = pop(&pila);
        while (temp->Dato >= 0){
            printf("%d\n",temp->Dato);
            if (temp->Dato == a->Dato) return;
            temp = pop(&pila);
        }
        if (temp->Dato < 0)    temp->Dato = -temp->Dato;
        else salir = 1;
    }
}

void InOrden(struct Arbol *a){

// Esta implementacion es valido cuando los valores del arbol son todos positivos!
    tPila pila;
    Arbol *temp;

    if (a == NULL)return;

    temp = a;
    crearPila(&pila);
    push(&pila,NULL);

    int salir = 0;

    while (salir == 0){
        while (temp != NULL){
            push(&pila, temp);
            temp = temp->Izq;
        }
        temp = pop(&pila);
        int sal = 0;
        while ((temp != NULL) && (sal == 0)){
            printf("%d\n",temp->Dato);
            if (temp->Der != NULL){
                temp = temp->Der;
                sal = 1;
            } else
                temp = pop(&pila);
        }
        if (sal == 0) salir = 1;
    }

}

void Niveles(struct Arbol * a){
tCola cola;
Arbol *aux;

if (a != NULL) {
     crearCola(&cola);
     encolar(&cola, a);
     while (colavacia(&cola) == 0) {
        aux = desencolar(&cola);
        printf("%d\n",aux->Dato);
        if (aux->Izq != NULL) encolar(&cola, aux->Izq );
        if (aux->Der!= NULL) encolar(&cola, aux->Der);
     }
}

}

void InsertarNodo(struct Arbol **Raiz,int valor)
{
if(*Raiz == NULL){

    *Raiz = new(Arbol);
    if(*Raiz!=NULL){
    (*Raiz)->Dato=valor;
    (*Raiz)->Izq=NULL;
    (*Raiz)->Der=NULL;
    }
    else{
        printf("%c no insertado.\n",valor);
    }
}
else if(valor<(*Raiz)->Dato)
InsertarNodo(&((*Raiz)->Izq),valor);
else if(valor>(*Raiz)->Dato)
InsertarNodo(&((*Raiz)->Der),valor);
else printf("Dato duplicado.\n");
}

Arbol *Buscar(struct Arbol *Raiz,int clave){
if(!Raiz) return Raiz;
while(Raiz->Dato!=clave){
if(clave<Raiz->Dato) Raiz=Raiz->Izq;
else Raiz=Raiz->Der;
if(Raiz==NULL) break;
}
return Raiz;
}

Arbol *Borrar(struct Arbol *Raiz,int clave){
struct Arbol *p,*p2;
if(!Raiz){
    printf("%d elemento no encontrado.\n",clave);
    return Raiz;
}
if(Raiz->Dato==clave){
    if(Raiz->Izq==Raiz->Der){
     delete Raiz;
     return NULL;
    }
    else if(Raiz->Izq==NULL){
     p=Raiz->Der;
     delete Raiz;
     return p;
    }
    else if(Raiz->Der==NULL){
     p=Raiz->Izq;
     delete Raiz;
     return p;
    }
    else{
     p2=Raiz->Der;
     p=Raiz->Der;
     while(p->Izq) p=p->Izq;
     p->Izq=Raiz->Izq;
    delete Raiz;
     return p2;
    }
}
if(Raiz->Dato < clave)
    Raiz->Der=Borrar(Raiz->Der,clave);
else
    Raiz->Izq=Borrar(Raiz->Izq,clave);

return Raiz;
}

/* void Free(struct Arbol *m)
{

    if(m!=NULL) {

     m=m->Izq;
     m=m->Der;
        //Free(m->Izq);
        //Free(m->Der);
        Free(m);
        delete m;
        //m=NULL;

}

} */

//////////////////////////////

int main(void){
int dato;
int opcion;
struct Arbol *Raiz=NULL;
struct Arbol *aux ;
struct Arbol *m=NULL;

/*
EL ARBOL ES EL SIGUIENTE, HA DE SER BINARIO
                5
        2                9
    1        3        8        11

*/

Raiz = new (Arbol);
Raiz->Dato = 5;
Raiz->Izq = new (Arbol);
Raiz->Izq = new (Arbol);

aux = Raiz->Izq;
aux->Dato = 2;
aux->Izq = new (Arbol);
aux->Izq->Dato = 1;
aux->Izq->Izq = NULL;
aux->Izq->Der = NULL;
aux->Der = new (Arbol);
aux->Der->Dato = 3;
aux->Der->Izq = NULL;
aux->Der->Der = NULL;

Raiz->Der = new (Arbol);
aux = Raiz->Der;
aux->Dato = 9;
aux->Izq = new (Arbol);
aux->Izq->Dato = 8;
aux->Izq->Izq = NULL;
aux->Izq->Der = NULL;
aux->Der = new (Arbol);
aux->Der->Dato = 11;
aux->Der->Izq = NULL;
aux->Der->Der = NULL;

Menu();
cin >> opcion;
//scanf("%d",&opcion);
while(opcion!=8){
switch(opcion){
    case 1: printf("Introduce un numero: ");
                    cin >> dato;
                    InsertarNodo(&Raiz,dato);
                    break;
    case 2: printf("Introduce el numero a eliminar: ");
                    cin >> dato;
                    Raiz = Borrar(Raiz,dato);

                    break;
    case 3: printf("Introduzca el numero a buscar: ");
                    cin >> dato;
                    if(Buscar(Raiz,dato)) printf("Elemento encontrado.\n");
                    else printf("El elemento no se encontro en el arbol.\n");
                    break;
    case 4: printf("En Inorden es:\n");
                    InOrden(Raiz);
                    break;
    case 5:printf("En Postorden es:\n");
                    PostOrden(Raiz);
                    break;
    case 6: printf("En preorden es:\n");
                    PreOrden(Raiz);
                    break;
    case 7: printf("En niveles es:\n");
                    Niveles(Raiz);
                    break;

case 9: printf("borrar:\n");

                     Free(m);
                    break;

     default:
                    printf("Opcion Incorrecta.");
                    Menu();
                    break;
    }
    Menu();
    cin >> opcion;
}
return 0;
}

заранее спасибо

)))

Учимся использовать тег more

Модерирует : ShIvADeSt
Версия для печати • Подписаться • Добавить в закладки
На первую страницу • к этому сообщению • к последнему сообщению