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

struct _nodo{
	int info;
   struct _nodo *l;
   struct _nodo *r;
   };
typedef struct _nodo nodo;
nodo *tp;

nodo* abpb(int n);
nodo* get();
void preorder(nodo *p);
void inorder(nodo *p);
void postorder(nodo *p);
nodo* inst(nodo *pa,int x);
void ext(nodo *pa,int x);
void main(void)
{
   char stream[6],sky[6];
	int numero,scelta,x;
   printf("inserire il numero di elementi: ");
   gets(stream);
   numero=atoi(stream);
	abpb(numero);
   do{
   	printf("\n[1]visita preorder\n[2]visita inorder\n[3]visita postorder\n[4]inserimento ordinato\n--> ");
   	gets(sky);
   	scelta=atoi(sky);
   	switch(scelta){
   		case 1:	preorder(tp);
      				break;
      	case 2: 	inorder(tp);
      				break;
      	case 3:  postorder(tp);
      				break;
         case 4:	printf("Inserisci il valore da inserire: ");
         			gets(sky);
                  x=atoi(sky);
         			inst(tp,x);
      	case 5:  printf("Inserisci il valore da eliminare: ");
         			gets(sky);
                  x=atoi(sky);
         			ext(tp,x);
         };
      }while(scelta!=0);

}

nodo* abpb(int n)
{
   nodo *p;
	if(n==0)
   	return(NULL);
   else
   {
   	p=get();
      if(tp==NULL)
      	tp=p;
      p->l=abpb(n/2);
      p->r=abpb(n-n/2-1);
      return(p);
   }
}

nodo* get()
{
   char stream[6];
   int elemento;
   nodo *p1;
   printf("insderisci l'elemento: ");
   gets(stream);
   elemento=atoi(stream);
   p1=(nodo*)calloc(1,sizeof(nodo));
   p1->info=elemento;
   return(p1);
   free(p1);
}
void preorder(nodo *p)
{
	if(p!=NULL)
   {
   	printf("%d",p->info);
      preorder(p->l);
      preorder(p->r);
   }
}
void inorder(nodo *p)
{
	if(p!=NULL)
   {
   	inorder(p->l);
      printf("%d",p->info);
      inorder(p->r);
   }
}
void postorder(nodo *p)
{
	if(p!=NULL)
   {
   	postorder(p->l);
      postorder(p->r);
      printf("%d",p->info);
   }
}

nodo* inst(nodo *pa,int x)
{
	nodo *q,*r,*s;
   q=NULL;
   r=pa;
   while(r!=NULL)
   	if(x==r->info)
      	return(r);
      else
      {
      	q=r;
         r=(x<r->info)? r->l : r->r;
      }
   s=(nodo*)calloc(1,sizeof(nodo));
   s->info=x;
   s->l=s->r=NULL;
   if(q==NULL)
   	pa=s;
   else(x<q->info)?(q->l=s) : (q->r=s);
   return(s);
}

void ext(nodo *pa,int x)
{
	nodo *e,*pe,*p;
   if(e!=NULL)

   	if(e->l==NULL)
      	p=e->r;
      else if(e->r==NULL)
      	p=e->l;
      if(pe==NULL)
      	pa=p;
      else if(e==pe->l)
      	pe->l=p;
         else
         pe->r=p;
}