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

typedef struct element
{
   int value;
   struct element* next;
   struct element* left;
   struct element* right;
}Element;


typedef Element* List;
typedef Element* Tree;


void printList(List);
Tree makeTree(List*, int);


int main()
{
   List L = NULL,
        Lapp;
   Tree T;
   int nodes = 0;
   int value = 0;
   
   while(value != -1)
   {
      printf("Valore: ");
      scanf("%d",&value);
      
      if(value == -1)
         break;

   /* lista vuota */
      if(L == NULL)
      {
         L = (List) malloc(sizeof(Element));

         if(L == NULL)
            exit(1);

         L->value = value;
         L->next = NULL;
         L->left = NULL;
         L->right = NULL;
      }
      else
      {
      /* lista non vuota */
         Lapp = L;

         while(Lapp != NULL)
            Lapp = Lapp->next;

         Lapp = (List) malloc(sizeof(Element));

         if(Lapp == NULL)
            exit(1);

      /* inizializzo i valori del nuovo nodo */
         Lapp->value = value;
         Lapp->next = NULL;
         Lapp->left = NULL;
         Lapp->right = NULL;
      }
      
      nodes++;
      
      printf("\nSizeLista: %d\n",nodes);
      printf("\nLista: ");
      printList(L);
      printf("\n");
      system("PAUSE");
   }

   T = makeTree(&L, nodes);

   /* pre\in\post order */

   return 0;
}



void printList(List L)
{
   while(L != NULL)
   {
      printf("%d ",L->value);
      L = L->next;
   }
}



/* costruisce un albero bilanciato partendo da una lista lunga n */
Tree makeTree(List* L, int n)
{
   Tree root;
   int l = (n - 1) / 2;
   int r = n - 1 - l;
   
   if(n == 0)
      return NULL;
      
   root = (*L);
   (*L) = (*L)->next;
   
   root->left = makeTree(L, l);
   root->right = makeTree(L, r);
   
   return root;
}