/*
 * Árvores de grau variável. Representação filho esquerdo-irmão
 * direito e com vetor. 
 */


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

typedef struct no {
  char c;
  struct no *fesq, *idir;
} No;

No *cria(char c, No* fesq, No* idir) {
  No* n = (No*) malloc (sizeof (No));
  n->c = c;
  n->fesq = fesq;
  n->idir = idir;
  return n;
}

/* Constrói a árvore
                   A               A
                 / |  \          /
                B  C   D        B - C - D
               /\  |  /|\      /    |  /
              E  F G H I J    E-F   G H-I-J
             /\      |       /      |
            K  L     M      K-L     M   
*/

No *f1() {
  return cria('A', 
	      cria('B', cria('E', cria('K', NULL, cria('L', NULL, NULL)),
			     cria('F', NULL, NULL)),
		   cria('C', cria('G', cria('M', NULL, NULL), NULL),
			cria ('D', cria('H', NULL, 
					cria('I', NULL,  
					     cria('J', NULL, NULL))), NULL))),
	      NULL);
} 

int grau(No* n) {
  int k = 0;
  No *aux = n->fesq;
  while(aux != NULL) {
    k++;
    aux = aux->idir;
  }
  return k;
}

int grau_max_ingenua(No* n) {
  No *aux = n->fesq;
  int k_max = grau(n);
  while (aux != NULL) {
    int k = grau_max_ingenua(aux);
    if (k_max < k)
      k_max = k;
    aux = aux->idir;
  }
  return k_max;
}


int grau_max(No* n) {
  No *aux = n->fesq;
  int k_max = 0;
  int k_raiz = 0;
  while (aux != NULL) {
    int k = grau_max(aux);
    if (k_max < k)
      k_max = k;
    aux = aux->idir;
    k_raiz++;
  }
  if (k_max < k_raiz)
      k_max = k_raiz;
  return k_max;
}

int altura(No* n) {
  No *aux = n->fesq;
  int h_max = 0;
  while (aux != NULL) {
    int h = altura(aux);
    if (h_max < h)
      h_max = h;
    aux = aux->idir;
  }
  return h_max + 1;
}

/*
 *  Escreve uma árvore no formato A(B(E(K,L),F),C(G(M)),D(H,I,J))
 */ 
void escreve(No* n) {
}

typedef struct novet {
  char c;
  int k;
  struct novet **vet;
} Novet;

Novet* No2Novet(No* n) {
  if (n == NULL)
    return NULL;
  Novet* nv = malloc(sizeof(Novet));
  nv->c = n->c;
  nv->k = grau(n);
  if (nv->k == 0) {
    nv->vet = NULL;
    return nv;
  }
  nv->vet = malloc(nv->k * sizeof(Novet*));
  No *aux = n->fesq;
  int i = 0;
  while (aux != NULL) {  
    nv->vet[i] = No2Novet(aux);
    aux = aux->idir;
    i++;
  }
  return nv;
}

No* Novet2No(No* n) {
  return NULL;
}

int main() {
  No* arv = f1();
  Novet* arv_vet = No2Novet(arv);
  return 0;
}