/* Albero

   Programma a cura di Vincenzo Capuano. 
   I diritti sul programma sono riservati all'autore.
   Per informazioni: enzocap@interfree.it - www.sitoserio.it/cpp
*/


#include<iostream.h>
#include<stdio.h>

struct nodo{
     int x;
     nodo* sx;
     nodo* dx;
     };

class tree{
   void deltree(nodo* &p);
   void print(nodo* &p);
   void insert(nodo* &p,int x);
   void copia(nodo* p,nodo* &punt);
   void add(nodo* &p,int x);
   void visitaord(nodo* p);
   void visitapostord(nodo* p);
   void visitapreord(nodo* p);
   public:
   nodo* testa;
   tree();
   ~tree();
   tree(const tree &ob);
   void inserisci(int x);
   void visual();
   void cancella();
   void operator=(const tree &ob);
   tree operator++();
   tree operator+(int x);
   void visita(int x);
   friend int conta(nodo* p);
   friend void contafoglie(tree &ob);
};

tree::tree()
{
 testa=NULL;
}

tree::~tree()
{
 if(!testa)
  delete testa;
 deltree(testa);
}

tree::tree(const tree &ob)
{
 copia(ob.testa,testa);
}

void tree::copia(nodo* p,nodo* &punt)
{
 if(p)
 {
  punt=new nodo;
  punt->x=p->x;
  copia(p->sx,punt->sx);
  copia(p->dx,punt->dx);
 }
 else
  punt=NULL;
}

void tree::inserisci(int x)
{
 insert(testa,x);
}

void tree::insert(nodo* &p,int x)
{
 if(!p)
 {
  p=new nodo;
  p->x=x;
  p->sx=NULL;
  p->dx=NULL;
 }
 else
  if(x<=p->x)
   insert(p->sx,x);
  else
   insert(p->dx,x);
}

void tree::visual()
{
 print(testa);
}

void tree::print(nodo* &p)
{
 if(!p)
  cout<<"\n L'albero e' vuoto";
 else
 {
  print(p->sx);
  print(p->dx);
  cout<<p->x<<endl;
 }
}

void tree::cancella()
{
 deltree(testa);
 testa=NULL;
}

void tree::deltree(nodo* &p)
{
 if(p)
 {
  deltree(p->sx);
  deltree(p->dx);
  delete p;
 }
}

void tree::operator=(const tree &ob)
{
 deltree(testa);
 copia(ob.testa,testa);
}

tree tree::operator++()
{
 add(testa,1);
 return *this;
}

void tree::add(nodo* &p,int x)
{
 if(p)
 {
  p->x=p->x+x;
  add(p->sx,x);
  add(p->dx,x);
 }
}

tree tree::operator+(int x)
{
 tree temp;
 copia(temp.testa,testa);
 temp.inserisci(x);
 return temp;
}

void tree::visita(int x)
{
 if(x==1) visitaord(testa);
 if(x==2) visitapostord(testa);
 if(x==3) visitapreord(testa);
}

void tree::visitaord(nodo* p)
{
 if(p)
 {
  visitaord(p->sx);
  cout<<"\n l'elemento e': "<<p->x<<endl;
  visitaord(p->dx);
 }
}

void tree::visitapostord(nodo* p)
{
 if(p)
 {
  visitapostord(p->sx);
  visitapostord(p->dx);
  cout<<"\n l'elemento e': "<<p->x<<endl;
 }
}

void tree::visitapreord(nodo* p)
{
 if(p)
 {
  cout<<"\n l'elemento e': "<<p->x<<endl;
  visitapreord(p->sx);
  visitapreord(p->dx);
 }
}


int conta(nodo* p)
{
 if(p)
  return(1+conta(p->sx)+conta(p->dx));
 else
  return 0;
}

void contafoglie(tree &ob)
{
 int n;
 n=conta(ob.testa);
 if(n)
  cout<<"\n Il numero di foglie e' "<<n<<endl;
 else
  cout<<"\n Non ci sono nodi nell'albero!"<<endl;
}


void main()
{
 tree albero;
 int elemento,scelta,scelta2,cont,val;
 cont = 1;
 while(cont)
  {
   cout<<"\n                ***TREE 1.0 by Enzo***\n";
   cout<<"\n                       -OPTIONS- ";
   cout<<"\n             1. Inserisci elemento";
   cout<<"\n             2. Visualizza l'albero";
   cout<<"\n             3. Costr. copy";
   cout<<"\n             4. Somma di un elemento all'albero";
   cout<<"\n             5. Cancella albero";
   cout<<"\n             6. Conta numero foglie";
   cout<<"\n             7. Visita albero";
   cout<<"\n             6. Esci dal programma";

   cout<<"\n\nInserisci la tua scelta: ";
   cin >> scelta;
   if(scelta==1)
    {
     cout<<"\nDai l'elemento da inserire: ";
     cin>>elemento;  cout<<"\n Grazie!";
     albero.inserisci(elemento);
    }
    if(scelta==2)
     albero.visual();
    if(scelta==3)
    {
     cout<<"\nUtilizzo costruttore copy...";
     tree albero2 = albero;
     albero2.visual();
     cout<<"\nCostruttore copy utilizzato!";
    }
    if(scelta==4)
    {
     cout<<"\nInserisci l'elemento da sommare: ";
     cin>>val;
     albero=albero+val;
     cout<<"\nOverloading somma effettuata!";
    }
    if(scelta==5)
     albero.cancella();
    if(scelta==6)
     contafoglie(albero);
    if(scelta==7)
     {
      cout<<"\n           -VISITA-";
      cout<<"\n digita 1 per visita in ordine";
      cout<<"\n digita 2 per visita in postordine";
      cout<<"\n digita 3 per visita in preordine";
      cout<<"\n\n digita scelta: ";
      cin>>scelta2;
      if(scelta2==1)
       albero.visita(1);
      if(scelta2==2)
       albero.visita(2);
      if(scelta2==3)
       albero.visita(3);
     }
    if(scelta==8)
     cont = 0;
  }
}