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

typedef struct cell {
  int val;
  struct cell *un,*deux;
} *Tree;

Tree cons_cell(int val, Tree un,Tree deux)
{
  Tree r;

  r = (Tree )malloc(sizeof(struct cell));
  if ( r == NULL) {
    fprintf(stderr,"Plus de memoire\n");
    exit(-1);
  }
  r->val = val;
  r->un = un;
  r->deux = deux;
  return r;
}


Tree gen(int n1,int n2,int r)
{
  if (r < 0)
    return NULL;
  else
    return cons_cell(n1,gen(n2,n1+1,r-1),gen(n2,n1+2,r-2));
}

void affiche(Tree t)
{
  if (t == NULL)
    return;
  printf("%d ",t->val);
  affiche(t->un);
  affiche(t->deux);
}

int gain(Tree t)
{
  if (t == NULL)
    return 0;
  if (t->un == NULL && t->deux == NULL)
    return t->val;
  return -(gain(t->un)+gain(t->deux));
}

void main(void)
{
  Tree t;
  int i;

  for (i = 0 ; i < 16 ; i++) {
    printf("%d : ",i);
    t = gen(0,0,i);
    affiche(t);
    putchar('\n');
    printf("%d\n\n",gain(t));
  }
}