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

struct _ArvBin {
    int info ;
    struct _ArvBin * esq ;
    struct _ArvBin * dir ;
} ;

typedef struct _ArvBin ArvBin ;

ArvBin* cria_arv_bin(int info, ArvBin* p_esq, ArvBin* p_dir) {
    ArvBin* p_a = (ArvBin*) malloc(sizeof(ArvBin)) ;
    assert(p_a) ;
    p_a->info = info ;
    p_a->esq = p_esq ;
    p_a->dir = p_dir ;
    return p_a ;       
}

int vazia(ArvBin* p_a) {
    assert(p_a) ;
    return (p_a->info == -1) && (p_a->esq == NULL) && (p_a->dir == NULL) ;
}

enum _Ordem { pre, sim, pos } ;

typedef enum _Ordem Ordem ;

/* Ex. 1.: Escreva uma função que dada uma árvore e uma ordem imrima o conteúdo dos elementos da
árvore segundo a ordem de caminhamento dada. */
void imprime_ordem(ArvBin* p_a, Ordem o){
    if(!vazia(p_a)){
        // ...
    }
    else 
        printf("Árvore vazia!") ;
}

/* Ex. 2.: Escreva uma função que calcule a altura de uma árvore. */
int altura(ArvBin* p_a){
    int h1, h2 ; 
    // ...
    return 1 + (h1 > h2 ? h1 : h2) ;
}

/* Ex. 3.: Escreva uma função que retorne o pai do elemento cujo conteúdo é igual ao dado. */
ArvBin* pai(ArvBin* p_a, int info){
    if (p_a) {
        // ...
    }
    return NULL ;
}

/* Ex. 4.: O percurso em nível de uma árvore binária T é aquele em que os nós são dispostos em ordem 
não decrescente de seus níveis. Escrever um algoritmo para efetuar o percurso em nível da árvore T.
Sugestão: utilizar uma fila.
*/    
void imprime_nivel(ArvBin* p_a) {
// ...
}

/* Ex. 5.: Escrever um algoritmo não recursivo para o percurso em pré-ordem de uma árvore binária.
Sugestão: utilizar uma pilha. */
void imprime_preordem_iter(ArvBin* p_a) {
// ...
}

/* Ex. 6.: Utilizando a representação de uma expressão aritmética através de uma árvore binária, 
escrever um algoritmo simples para determinar a notação polonesa da expressão aritmética. */
void imprime_polonesa(char* exp) {
// ...
}

int main(void){
    ArvBin* p_raiz = 
        cria_arv_bin(0, 
            cria_arv_bin(1, 
                cria_arv_bin(11, NULL, NULL),
                cria_arv_bin(12, NULL, NULL)), 
            cria_arv_bin(2,
                cria_arv_bin(21, NULL, NULL),
                cria_arv_bin(22, NULL, NULL))) ;
    assert(p_raiz) ;
    printf("Pré-ordem\n") ;
    imprime_ordem(p_raiz, pre) ;
    printf("\nSimétrica\n") ;
    imprime_ordem(p_raiz, sim) ;
    printf("\nPós-ordem\n") ;
    imprime_ordem(p_raiz, pos) ;
    printf("\nAltura\n") ;
    printf("%d", altura(p_raiz)) ;
    printf("\nPai\n") ;
    ArvBin* p_pai = pai(p_raiz, 22) ;
    if (p_pai)
        printf("%d", p_pai->info) ;
    else
        printf("Não achei o pai de 22") ; 
    printf("\nNível\n") ;
    imprime_nivel(p_raiz) ;
    printf("\nPré-ordem iterativa\n") ;
    imprime_preordem_iter(p_raiz) ;
    printf("\nPolonesa\n") ;
    imprime_polonesa("(1 + (3 - 4)) * 5") ;
}