III_Tempo_AlberoBil

#include<iostream>
using namespace std;
struct nodo{int info; nodo* left,*right; nodo(int a=0, nodo* b=0, nodo*c=0){info=a; left=b;right=c;}};

//PRE= (albero(r) è corretto e bilanciato
int countN(nodo * r) {

    if(!r)
        return 0;
    else
        return 1 + countN(r->left) + countN(r->right);


}//count
//POST=  La funzione restituisce il numero di nodi presenti nell'albero passato

//PRE=(albero(r) è corretto e bilanciato nel senso spiegato nell’Esempio 1, valbero(r)=albero(r))
nodo* alberobil (nodo*r, int k) {

    if(!r)//Albero vuoto
    return new nodo(k,0,0);
    else{

        if(countN(r->left) > countN(r->right)){

            r->right= alberobil(r->right,k);

        }//Devo inserire a destra
        else
            r->left = alberobil(r->left,k);

        return r;

    }//albero non vuoto

}//alberobil
//POST=(albero(r) è corretto e ancora bilanciato ed è ottenuto da valbero(r) aggiungendogli  una nuova foglia  con info=k)
/* PROVA INDUTTIVA */
/* --- CASO BASE ---
1) if(!r)
            Sono in presenza di un albero vuoto--> ritorno il nuovo nodo dove ho inserito il campo k
    --- CASO INDUTTIVO ---
1)if(countN(r->left)> countN(r->right))

    r->right= alberobil(r->right,k);
//PRE_ric=(albero(r->right) è corretto e bilanciato nel senso spiegato nell’Esempio 1, valbero(r->right)=albero(r->right))

    Inserisco quindi il nuovo nodo nel sottoalbero(r) destro, in quanto #nodidx < #nodisx, che è corretto

    PRE_ric --> POST_ric

//POST_ric=(albero(r->right) è corretto e ancora bilanciato ed è ottenuto da valbero(r->right) aggiungendogli  una nuova foglia  con info=k)

 2)if(countN(r->left)<= countN(r->right))

    r->left= alberobil(r->left,k);
//PRE_ric=(albero(r->left) è corretto e bilanciato nel senso spiegato nell’Esempio 1, valbero(r->left)=albero(r->left))

    Inserisco quindi il nuovo nodo nel sottoalbero(r) sinistro, in quanto #nodisx <= #nodidx, che è corretto
    PRE_ric --> POST_ric
//POST_ric=(albero(r->left) è corretto e ancora bilanciato ed è ottenuto da valbero(r->left) aggiungendogli  una nuova foglia  con info=k)





--- FINE PROVA INDUTTIVA */

//PRE=(albero(r) è corretto e bilanciato, n>=0, valbero(r)=albero(r))
nodo* buildtree(nodo* r, int n){

    if(n){
        int k; cin>>k;

    r = alberobil(r,k);
    return  buildtree(r,n-1);

    }//Ho nodi da aggiungere all'albero
    else
        return r;



}//buildtree
//POST=(restituisce valbero(r) con n nodi aggiuntivi inseriti in modo da conservare il bilanciamento)

/* PROVA INDUTTIVA */
/* ----- CASO BASE -----
/*
1) if(!n) Non ho più nodi da aggiungere all'albero, quindi ritorno r che è l'albero costruito

--- CASO INDUTTIVO --
1)n>0 --> Ho ancora dei nodi da inserire nell'albero

//PRE_ric = Albero(r) è bilanciato e n-1 >=0 , valbero(r) = albero(r)

Pre ric vale dato che n>0 --> posso assumere post_ric

//POST_ric = (restituisce valbero(r) con n-1 nodi aggiuntivi inseriti in modo da conservare il bilanciamento

Che è corretto dato che ho costruito l'albero con 1 nodo, albero(r) sarà valbero(r) con n-1 nodi inseriti.

 --- FINE PROVA INDUTTIVA */

void stampa_l(nodo* R){

if(R){
cout<<R->info<<"(";
stampa_l(R->left);
cout<<",";
stampa_l(R->right);
cout<<")";

}else
    cout<<"_";


}//stampa_L
main()
{
  int n;
  cin>>n;
  nodo* R=buildtree(0,n);//da fare
  cout<<"start"<<endl;
  stampa_l(R); //da fare, vista in classe

  cout<<endl<<"end";
}