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

int cont;
typedef struct node {
	int valor;
	struct node* pai;// node pai
	struct node* filhoesq;// filho esquerdo
	struct node* irmaodir;// irmao direito
} node;


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

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

int main() {
    cont = 1;
    int K = 3;
    int h = 4;
    int N = (pow(K,h)-1)/(K-1); // N = (K^h - 1)/(K-1)

    node* raiz = tree_create(N,K);

    cout<<"Arvore "<<K<<"-aria completa com "<<h<<" niveis preenchida por niveis";

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

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

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



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

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

    node** vet = new node*[N+1];
    for (int i=1; i<=N; i++) {
        vet[i] = new node;
        vet[i]->valor = i;
        vet[i]->pai = NULL;
        vet[i]->filhoesq = NULL;
        vet[i]->irmaodir = NULL;
    }
    int pai = 1;
    int nfilhos=0;
    for (int i=2; i<=N; i++) {
        vet[i]->pai = vet[pai];
        if (nfilhos==0)
             vet[pai]->filhoesq = vet[i];
        else vet[i-1]->irmaodir = vet[i];
        nfilhos++;
        if (nfilhos>=K) {
            nfilhos=0; pai++;
        }
    }
    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 << " ";
    node* noh = raiz->filhoesq;
    while (noh!=NULL) {
        pre_ordem(noh);
        noh = noh->irmaodir;
    }
}

// Lista os elementos em Pos-Ordem
void pos_ordem(node* raiz) {
    if (raiz==NULL) return;
    node* noh = raiz->filhoesq;
    while (noh!=NULL) {
        pos_ordem(noh);
        noh = noh->irmaodir;
    }
    cout << raiz->valor << " ";
}




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

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

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

    delete raiz;
}




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

    raiz->filhoesq = new node;
    node* noh = raiz->filhoesq;

    for(int i=1; i<=K; i++) {
        noh->pai = raiz;
        noh->filhoesq = NULL;
        if (i==K) noh->irmaodir = NULL;
        else noh->irmaodir = new node;
        noh = noh->irmaodir;
    }

    noh = raiz->filhoesq;
    for(int i=1; i<=K; i++) {
        tree_create(noh,K,(N-1)/K);
        noh = noh->irmaodir;
    }
}*/