/*Thiago FC Oliveira
  148069
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct arvore {

    int chave;
    struct arvore *esquerda;
    struct arvore *direita;

} arvore;

typedef struct node {

    arvore *data;
    struct node *next;

} node;

typedef struct lista {

    int tamanho;
    struct node *head;

} lista;

/*Funcao de insercao: recebe como parametros a chave a ser inserida, "a", e o endereco de memoria da raiz. A funcao eh recursiva. */

void insercao(int a, arvore ** raiz)
{

    if (*raiz == NULL) {
    arvore *aux = malloc(sizeof(arvore));
    if (!aux) {
        printf("memoria insuficiente\n");
        return;

    }
    aux->direita = NULL;
    aux->esquerda = NULL;
    aux->chave = a;
    *raiz = aux;

    return;
    }

    if (a < (*raiz)->chave) {
    insercao(a, &(*raiz)->esquerda);
    return;
    }

    if (a > (*raiz)->chave) {
    insercao(a, &(*raiz)->direita);
    return;
    }
}

/*Funcao de busca: recebe como parametros a chave a ser encontrada, e a raiz. Retorna o no procurado ou NULL */

arvore *busca(int a, arvore * r)
{
    while (r != NULL && r->chave != a) {
    if (a < r->chave) {
        r = r->esquerda;
    } else {
        r = r->direita;
    }
    }
    return r;           //printf("%d", r->chave);
    // if(r == NULL) printf("nao pertence\n");
    //else printf("pertence");
}

/*As proximas duas funcoes retornam a funcao main o maximo e o minimo da arvore, ou seja, a extrema direita ou a extrema esquerda, respectivamente.*/

int minimo(arvore * r)
{
    while (r->esquerda != NULL) {
    r = r->esquerda;
    }
    return r->chave;
}

int maximo(arvore * r)
{
    while (r->direita != NULL) {
    r = r->direita;
    }
    return r->chave;
}

/*As proximas tres funcoes fazem impressoes em profundidade, em pos ordem, pre ordem e ordem*/

void posordem(arvore * r)
{
    if (r != NULL) {
    posordem(r->esquerda);
    posordem(r->direita);
    printf("%d ", r->chave);
    }
}

void preordem(arvore * r)
{
    if (r != NULL) {
    printf("%d ", r->chave);
    preordem(r->esquerda);
    preordem(r->direita);

    }
}

void ordem(arvore * r)
{
    if (r != NULL) {
    ordem(r->esquerda);
    printf("%d ", r->chave);
    ordem(r->direita);

    }
}

/*As proximas tres funcoes auxiliam na funcao de impressao em largura. Elas emfilam e desenfilam as chaves da arvore, e tambem libera a memoria atraves
de free_all*/

void enfila(lista * l, arvore * r)
{
    node *aux;
    node *novo = malloc(sizeof(node));
    novo->data = r;
    novo->next = NULL;

    aux = l->head;

    if (aux->next == NULL)
    (l->head)->next = novo;
    else {
    while (aux->next != NULL)
        aux = aux->next;
    aux->next = novo;
    }
}

arvore *desenfila(lista * l)
{
    node *lixo;
    node *aux = (l->head)->next;
    arvore *chave;

    (l->head)->next = aux->next;
    lixo = aux;
    chave = lixo->data;
    free(lixo);
    return chave;

}

void free_all(lista * L)
{

    node *aux, *aux2;

    aux = L->head->next;
    aux2 = L->head;
    while (aux != NULL) {

    L->head = aux->next;
    free(aux);
    aux = L->head;

    }
    L->head = aux2;
    aux2->next = NULL;
}

/*Funcao que faz impressao em largura na arvore*/

void largura(arvore * r)
{
    lista *f = malloc(sizeof(lista));
    f->tamanho = 0;
    f->head = malloc(sizeof(node));
    f->head->next = NULL;

    enfila(f, r);

    while (f->head->next != NULL) {
    r = desenfila(f);
    printf("%d ", r->chave);
    if (r->esquerda != NULL)
        enfila(f, r->esquerda);
    if (r->direita != NULL)
        enfila(f, r->direita);

    }
    free_all(f);
    return;
}




int main()
{

    arvore *a = NULL, *aux;
    char comando[30];
    int chave, i = 1;

    while (i != 0) {

    scanf("%s", comando);

    if (strcmp("inserir", comando) == 0) {
        scanf("%d", &chave);
        insercao(chave, &a);
    }

    if (strcmp("buscar", comando) == 0) {
        scanf("%d", &chave);
        aux = busca(chave, a);
        if (aux == NULL) {
        printf("nao pertence\n");
        } else {
        printf("pertence\n");
        }
    }
    if (strcmp("minimo", comando) == 0) {
        if (a == NULL)
        printf("vazia\n");
        else {
        printf("%d\n", minimo(a));
        }
    }
    if (strcmp("maximo", comando) == 0) {
        if (a == NULL)
        printf("vazia\n");
        else {
        printf("%d\n", maximo(a));
        }
    }
    if (strcmp("pos-ordem", comando) == 0) {
        if (a == NULL)
        printf("vazia\n");
        else {
        posordem(a);
        printf("\n");
        }
    }
    if (strcmp("em-ordem", comando) == 0) {
        if (a == NULL)
        printf("vazia\n");
        else {
        ordem(a);
        printf("\n");
        }
    }
    if (strcmp("pre-ordem", comando) == 0) {
        if (a == NULL)
        printf("vazia\n");
        else {
        preordem(a);
        printf("\n");
        }
    }
    if (strcmp("largura", comando) == 0) {
        if (a == NULL)
        printf("vazia\n");
        else {
        largura(a);
        printf("\n");
        }
    }
    if (strcmp("terminar", comando) == 0) {
        i = 0;
    }
    }
    return 0;
}