// ------------------------------------------------------------------------------------------------
// Secao 10.4 do Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein)
// Implementacao de Arvores enraizadas (BINARIA)
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <math.h>
using namespace std;

int cont;
typedef struct node {
	int valor;
	struct node* pai;// node pai
	struct node* fesq;// filho esquerdo
	struct node* fdir;// filho direito
} node;


node* tree_create(int N);
void tree_delete(node* raiz);

void pos_ordem(node* raiz);
void pre_ordem(node* raiz);
void em_ordem(node* raiz);

int main() {
    cont = 1;
    //int h = 5; int N = pow(2,h)-1; // N = 2^h - 1

    int N = 31;
    node* raiz = tree_create(N);


    //cout<<"Arvore binaria completa com "<<h<<" niveis preenchida em Pre-Ordem";
    cout<<"Arvore binaria com "<<N<<" elementos preenchida por niveis";

    cout<<"\n\n\n Pre-Ordem:   ";
    pre_ordem(raiz);

    cout<<"\n\n\n Pos-Ordem:   ";
    pos_ordem(raiz);

    cout<<"\n\n\n Em-Ordem:   ";
    em_ordem(raiz);

    tree_delete(raiz);
    raiz = NULL;
    cout<<"\n\n\n";
    return 0;
}



// ------------------------------------------------------------------------------------------------
// ---- Algoritmos de ARVORES ---------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------

node* tree_create(int N) {
    if (N<=0) return NULL;

    node** vet = new node*[N+1];
    vet[0] = NULL;
    for (int i=1; i<=N; i++) {
        vet[i] = new node;
        vet[i]->valor = i;
        vet[i]->pai = vet[i/2];
        vet[i]->fesq = NULL;
        vet[i]->fdir = NULL;
        if (i==1) continue;
        if (i%2==0)
             vet[i]->pai->fesq = vet[i];
        else vet[i]->pai->fdir = vet[i];
    }
    node* raiz = vet[1];
    delete[] vet;
    return raiz;
}

// Lista os elementos em PRE-Ordem
void pre_ordem(node* raiz) {
    if (raiz==NULL) return;
    cout << raiz->valor << " ";
    pre_ordem(raiz->fesq);
    pre_ordem(raiz->fdir);
}

// Lista os elementos em POS-Ordem
void pos_ordem(node* raiz) {
    if (raiz==NULL) return;
    pos_ordem(raiz->fesq);
    pos_ordem(raiz->fdir);
    cout << raiz->valor << " ";
}

// Lista os elementos em EM-Ordem
void em_ordem(node* raiz) {
    if (raiz==NULL) return;
    em_ordem(raiz->fesq);
    cout << raiz->valor << " ";
    em_ordem(raiz->fdir);
}




// Deleta a arvore da memoria
void tree_delete(node* raiz) {
    if (raiz==NULL) return;

    tree_delete(raiz->fesq);
    raiz->fesq = NULL;

    tree_delete(raiz->fdir);
    raiz->fdir = NULL;

    delete raiz;
}






// Cria uma arvore binaria com N elementos (raiz jah deve estar alocado)
/*void tree_create(node* raiz, int N) {
    if (N==0) return;
    if (raiz==NULL) return;
    raiz->valor = cont++;
    if (N<3) return;

    raiz->fesq = new node;
    raiz->fesq->pai = raiz;
    raiz->fesq->fesq = NULL;
    raiz->fesq->fdir = NULL;
    tree_create(raiz->fesq,(N-1)/2);

    raiz->fdir = new node;
    raiz->fdir->pai = raiz;
    raiz->fdir->fesq = NULL;
    raiz->fdir->fdir = NULL;
    tree_create(raiz->fdir,(N-1)/2);
}*/