29-5-2018 alberi ricorsione prova di corr.

//29-05-2018
#include<iostream>
using namespace std;
struct nodoA{int info; nodoA* left,*right; nodoA(int a=0, nodoA*b=0,nodoA*c=0){info=a; left=b; right=c;}};
struct nodo{nodoA* info; nodo* next; nodo(nodoA* a=0, nodo*b=0){info=a; next=b;}};

void stampa_l(nodoA *r)
{
  if(r)
    {
      cout<<r->info<<'(';
      stampa_l(r->left);
      cout<<',';
      stampa_l(r->right);
      cout<<')';
    }
  else
    cout<< '_';
}
int conta_n(nodoA*r)
{
   if(!r) return 0;
     else
    return conta_n(r->left)+conta_n(r->right)+1;
}

nodoA* insert(nodoA*r, int y)
{
  if(!r) return new nodoA(y);

  if(conta_n(r->left)<=conta_n(r->right))
    r->left=insert(r->left,y);
   else
    r->right=insert(r->right,y);
  return r;
}

nodoA* buildtree(nodoA*r, int dim)
{
  if(dim)
   {
    int z;
    cin>>z;
    nodoA*x=insert(r,z);
    return buildtree(x,dim-1);
   }
  return r;
}


void riempi(int*P,int m)
{
  if(m)
    {
      cin>>*P;
      riempi(P+1,m-1);
    }
}
void stampaL(nodo*a)
{
  if(a)
    {
      cout<<a->info->info<<' ';
      stampaL(a->next);
    }
  else
    cout<<endl;
}


void concat(nodo*& L, nodo* daAggiungere){

    if(!L && !daAggiungere){
        return;
    }

    if(!L){
        L=daAggiungere;
        return;
    }
    if(!daAggiungere){
        return;
    }

    if(L->next != 0){
        concat(L->next, daAggiungere);
    }else{
        L->next = daAggiungere;
        return;
    }
}

nodo* match(nodoA*r, int*P, int dimP){
   nodo* n, *d, *s;
   n=0;
   d=0;
   s=0;

   if(!r){          //caso base #1
       return 0;
   }


   if(*P == r->info){               //match
       n = new nodo(r, 0);
       P=P+1;
       dimP=dimP-1;
   }

   if(r->left==0 && r->right==0){   //caso base #2
       if(dimP==0){
           return n;
       }else{
           return 0;
       }
   }

    if(dimP>0){
        s = match(r->left, P, dimP);    //ric #1

        if(s){
           dimP=dimP-1;
           P=P+1;
           concat(n,s);
        }


        d = match(r->right, P, dimP);   //ric #2

        if(d){
            dimP=dimP-1;
            P=P+1;
            concat(n,d);
        }

        if(!s && !d){       //caso base #3
           return 0;
        }
   }

   return n;
}

/*
    PROVA DI CORRETTEZZA di match

    Caso base #1 => POST
        r è un albero vuoto => non esistono cammini sui quali matchare e di conseguenza nessuna lista costruita dai nodi matchati è stata costruita => restituisce 0 (ovvero nessun match completo trovato)

    Caso base #2 => POST
        r è una foglia (ovvero i suoi cambi left e right puntano a nullptr) => se la dimP==0 allora ha trovato un match completo su quel cammino e dunque restituisce il nodo(r,0), altrimenti restituisco 0 (ovvero nessun match completo trovato)

    Caso base #3 => POST
        s e d sono contemporaneamente nullptr => la ricerca sul sottoalbero sinistro e destro non ha prodotto match completi sul/sui cammino/cammini => restituisco 0 (ovvero nessun match completo trovato)


    Calcolo:

    if(*P == r->info == true)   ho trovato un match,
                                creo un nuovo nodo* n(r,0)
                                decremento la dimensione dell'array P (dimP) e sposto di uno (in avanti) il puntatore all'array P

    if(dimP>0 == true)          il mio array P ha ancora elementi da matchare

                                s = match(r->left, P, dimP);
                                //passo induttivo, dimostro la PRE_ric #1

                                (1)albero r è un albero ben formato non essendo stato in alcun modo modificato => anche r->left è un albero ben formato
                                (2)P ha dimP elementi => avendo spostato P e decrementato dimP solo in caso di match => ancche P_ric ha dimP_elementi
                                (3)dimP>0 in quanto se fosse stata <=0 non avrebbe eseguito la chiamata ricorsiva => anche dimP_ric>0

                                essendo valida la PRE_ric assumo sia valida anche la POST_ric

                                if(s==true) se s non è un puntatore vuoto(ovvero la chiamata ricorsiva ha restituito un nodo non vuoto che dunque ha matchato)
                                            decremento la dimensione dell'array P (dimP) e sposto di uno (in avanti) il puntatore all'array P
                                            concat(n,s) faccio puntare l'ultimo nodo di n ad s


                                d = match(r->right, P, dimP);
                                //passo induttivo, dimostro la PRE_ric #1

                                (1)albero r è un albero ben formato non essendo stato in alcun modo modificato => anche r->right è un albero ben formato
                                (2)P ha dimP elementi => avendo spostato P e decrementato dimP solo in caso di match => ancche P_ric ha dimP_elementi
                                (3)dimP>0 in quanto se fosse stata <=0 non avrebbe eseguito la chiamata ricorsiva => anche dimP_ric>0

                                essendo valida la PRE_ric assumo sia valida anche la POST_ric

                                if(s==true) se s non è un puntatore vuoto(ovvero la chiamata ricorsiva ha restituito un nodo non vuoto che dunque ha matchato)
                                            decremento la dimensione dell'array P (dimP) e sposto di uno (in avanti) il puntatore all'array P
                                            concat(n,d) faccio puntare l'ultimo nodo di n ad d



                                => ha trovato un match completo sul cammino corrispondente => restituisce n, ovvero la lista i cui nodi puntano ai nodi matchati nel cammino

                                => POST
*/
main()
{
  int  n,m;
  cout<<"start"<<endl;
  cin>> n;
  nodoA*R=buildtree(0,n);
  stampa_l(R);
  cout<<endl;
  int P[50];
  cin>> m;
  riempi(P,m);
  nodo*a=match(R,P,m);
  if(a)
      stampaL(a);
    else
      cout<<"no match found"<<endl;
  cout<<"end"<<endl;
}