/*
 * Árvores binárias
 */


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

typedef struct no {
  char c; /* info */
  struct no *esq, *dir;
} No;


No* copia(No* p) {
  if (p == NULL)
    return NULL;
  No *n = malloc(sizeof(No));
  n->c = p->c;
  n->esq = copia(p->esq);
  n->dir = copia(p->dir);
  return n;
}

void libera(No* p) {
  if (p != NULL) {
    libera(p->esq);
    libera(p->dir);
    free(p);
  }
}


int altura (No* p) {
  if (p == NULL)
    return 0;
  int hesq = altura(p->esq);
  int hdir = altura(p->dir);
  if (hesq > hdir)
    return 1 + hesq;
  else
    return 1 + hdir;
}

int iguais(No* arv1, No* arv2) {
  if (arv1==NULL && arv2 == NULL)
    return 1;  
  if (arv1==NULL || arv2 == NULL)
    return 0;
  if (arv1->c == arv2->c) 
    return iguais (arv1->esq, arv2->esq) &&
      iguais(arv1->dir, arv2->dir);
  return 0;
}

No *arv(char c, No* esq, No* dir) {
  No* n = (No*) malloc (sizeof (No));
  n->c = c;
  n->esq = esq;
  n->dir = dir;
  return n;
}

/* Cria a árvore           a
                          / \
			 b   c
			    /
			   d
          
*/
No* exemplo() {
  return arv('a',arv('b',NULL,NULL),arv('c',arv('d',NULL,NULL),NULL));
}

/********** Percursos **********/

void preorder(No* p) {
  if (p != NULL) {
    printf("%c",p->c);
    preorder(p->esq);
    preorder(p->dir);
  }
}

void inorder(No* p) {
  if (p != NULL) {
    inorder(p->esq);
    printf("%c",p->c);
    inorder(p->dir);
  }
}

void postorder(No* p) {
  if (p != NULL) {
    postorder(p->esq);
    postorder(p->dir);
    printf("%c",p->c);
  }
}

/* Monta uma árvore de expressão a partir de uma expressão na forma
   pré-fixa */
No* monta_arv_expr () {
  No* n = (No*) malloc (sizeof (No));
  char c;
  scanf("%c", &c);
  n->c = c;

  if (c >= 'a' && c <= 'z') {
    n->esq = NULL;
    n->dir = NULL;
  } else {
    n->esq = monta_arv_expr();
    n->dir = monta_arv_expr();
  }

  return n;
}
		
void largura(No* p) {
}

int main() {
  No *arv = monta_arv_expr();
  printf("Pre: ");
  preorder(arv);
  printf("\nPos: ");
  postorder(arv);
  printf("\n");
  return 0;
}