/* 
 * This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 * (with slight alterations by Y. Kohayakawa)
 */
#include <stdio.h>
#include <stdlib.h>

char *a; int i;
typedef struct Tnode* link;
struct Tnode { char token; link l, r; };

link NEW(char token, link l, link r)
  { link x = malloc(sizeof *x); 
    x->token = token; x->l = l; x->r = r;
    return x;
  }

link parse()
  { char t; link x;

    while ((t = a[i++])==' ') ;
    x = NEW(t, NULL, NULL);
    if ((t == '+') || (t == '*'))
      { x->l = parse(); x->r = parse(); }
    return x;
  }

void in_order(link h)
{
  if (h) {
    if ((h->token=='*')||(h->token=='+')) printf("( ");
    in_order(h->l);
    printf("%c ", h->token);
    in_order(h->r);
    if ((h->token=='*')||(h->token=='+')) printf(") "); 
  }
}

void post_order(link h)
{ if (h)
    { post_order(h->l); post_order(h->r); printf("%c ", h->token); }
}

void printnode(char c, int h)
  { int i;
    for (i = 0; i < h; i++) printf("  ");
    printf("%c\n", c);
  }

void show_in(link x, int h)
  { 
    if (x == NULL) { printnode('N', h); return; }
    show_in(x->r, h+1);    
    printnode(x->token, h);
    show_in(x->l, h+1);    
  }

void show_pre(link x, int h)
  { 
    if (x == NULL) { printnode('N', h); return; }
    printnode(x->token, h);
    show_pre(x->r, h+1);    
    show_pre(x->l, h+1);    
  }

main(int argc, char **argv)
{
  link h;

  a=argv[1]; h=parse();

  in_order(h); printf("\n");
  post_order(h); printf("\n");

  printf("A arvore em pre-ordem:\n");  show_pre(h, 0);
  printf("A arvore em in-ordem:\n");  show_in(h, 0);
}