P1 23-5-18

//23-5-2018
#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) è ben formato, k>0, 1<=n<=k)

int contaNodi(nodo* r){

    if(!r){
        return 0;
    }

    return 1 + contaNodi(r->left)+contaNodi(r->right);
}


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

    if(!r){
        r = new nodo(k,0);
        //cout << r->info<<endl;
        return r;
    }

    if(contaNodi(r->left) <= contaNodi(r->right)){
        r->left = alberobil(r->left, k);
        return r;
    }else{
        r->right = alberobil(r->right, k);
        return r;
    }

    cout << r->info<<endl;
    return r;
}
//POST=(albero(r) è corretto e ancora bilanciato ed è ottenuto da valbero(r) aggiungendogli una nuova foglia con info=k)



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

    if(n>0){
        cin >> num;
        r = alberobil(r, num);
        return buildtree(r, n-1);
    }else{
        return r;
    }
}
//POST=(restituisce valbero(r) con n nodi aggiuntivi inseriti in modo da conservare il bilanciamento)

void stampa(nodo* r){
    if(r){
        cout << r->info;
        cout << "(";
        stampa(r->left);
        cout<<",";
        stampa(r->right);
        cout <<")";
    }else{
        cout<<"_";
    }
}

//PRE= (albero(r) è ben formato, k>0, 1<=n<=k)
int stampa_a_salti(nodo* r, int k, int n){

    if(!r){         //caso base (1)     r è un albero vuoto/nullptr
        return k;
    }

    if(n==1){
        cout << r->info << " ";
        n=k;
    }else{
        n=n-1;
    }



    if(!r->left && !r->right){  //caso base (2)
        return n;
    }


    if(r->left){
        n = stampa_a_salti(r->left, k, n);  //ric #1

    }

    if(r->right){
        n = stampa_a_salti(r->right, k, n); //ric #2

    }


    return n;
}
//POST=(stampa i campi info dei nodi di albero(r) in ordine prefisso nel modo seguente:
//salta i primi n-1, stampa il nodo n-esimo, poi ne salta k-1 stampa quello successivo
//e così via fino a visitare tutti i nodi) && (restituisce un intero m (1<=m<=k) che
//indica che si dovranno saltare m-1 nodi prima di stampare il prossimo)

/*
    CORRETTEZZA:

    (
        caso base (1) => POST
                        se r è vuoto non stampa nulla, restituisce k che è l'intero che rappresenta
                        il numero di salti-1 prima di stampare il prossimo (che ricordo in questo caso non esiste) => POST

        caso base (2) => POST
                        se il campo left e right di r puntano a 0/nullptr (ovvero sono in una foglia) restituisco
                        n che  esattamente il numero-1 di nodi da saltare prima di stampare il prossimo nodo
    )
    &&
    (
        if(n==1==true)  essendo arrivato al k-1esimo nodo, stampo il campo info del nodo r
                        imposto il valore di n come k, in quanto nella prossima ricorsione dovrò ripartire da k

        else(n!=1==true)decremento n di 1 in quanto nella prossima ricorsione dovrò controllare se n-1 nodo sia il k-1esimo


        if(r->left == true) il sottoalbero sinistro di r esiste, quindi lo visito
            dimostro la PRE_RIC di #1
                A-   r è ben formato, non essendo stato in alcun modo modificato => anche r->left è ben formato
                B-   k>0, non essendo mai stato modificato il valore di k => k_ric>0
                C-   1<=n<=k, essendo n al minimo 1 e al massimo k (vedi codice) => 1<=n_ric<=k
                A,B,C rispettano la PRE_ric e quindi assumo la POST_ric sia valida

        if(r->right == true) il sottoalbero sinistro di r esiste, quindi lo visito
            dimostro la PRE_RIC di #1
                A-   r è ben formato, non essendo stato in alcun modo modificato => anche r->right è ben formato
                B-   k>0, non essendo mai stato modificato il valore di k => k_ric>0
                C-   1<=n<=k, essendo n al minimo 1 e al massimo k (vedi codice) => 1<=n_ric<=k
                A,B,C rispettano la PRE_ric e quindi assumo la POST_ric sia valida

    )
    => POST

    restituisce il valore n che indica il numero di m-1 passi che mancano alla prossima stampa, saltando i primi n-1 nodi e ha stampato
    ogni k-1 nodi il campo info del nodo stesso
*/

main()
{
  int dim,k;
  cin>>dim;
  nodo* R=0;
  R=buildtree(R,dim);
  cout<<"start"<<endl;
  stampa(R);cout<<endl;
  cin>>k;
  int b=stampa_a_salti(R,k,k);
  cout<<endl<<"valore restituito="<<b<<endl;
  cout<<"end"<<endl;
}