Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- struct nodo{int info; nodo*left,*right; nodo(int a=0, nodo*b1=0,nodo*b2=0){info=a; left=b1; right=b2;}};
- struct nodoEx{nodo* info; int liv; nodoEx*next; nodoEx(nodo*a=0,int b=0, nodoEx*c=0){info=a; liv=b;next=c;}};
- struct coda{nodoEx* inizio, * fine; coda(nodoEx*a=0, nodoEx*b=0) {inizio=a; fine=b;}};
- //PRE=(x è una coda che gestisce una lista di nodoEx ben formata e a punta ad un nodoEx)
- coda push_end(coda x, nodoEx*a)
- {
- a->next=0;
- if(x.inizio)
- {
- x.fine->next=a;
- x.fine=a;
- }
- else
- x.inizio=x.fine=a;
- return x;
- }
- //POST=(restituisce la coda x che gestisce la lista originale con il nodoEx a aggiunto alla fine della lista)
- //PRE=(C.inizio non è 0)
- nodoEx* pop(coda & C)
- {
- nodoEx* x=C.inizio;
- C.inizio=C.inizio->next;
- if(C.inizio==0)
- C.fine=0;
- return x;
- }
- //POST=(modifica C eliminando il suo primo nodoEx e restituendolo col return )
- void build_BST(nodo*&r, int x)
- {
- if(!r)
- r=new nodo(x);
- else
- {
- nodo*q=r;
- bool continua=true;
- while (r && continua)
- {
- if(r->info >=x)
- if(r->left)
- r=r->left;
- else
- {r->left=new nodo(x); continua=false;}
- else
- if(r->right)
- r=r->right;
- else
- {r->right=new nodo(x); continua=false;}
- }
- r=q;
- }
- }
- void stampa_lin(nodo*r)
- {
- if(r)
- {
- cout <<'['<<r->info<<']'<<'(';
- stampa_lin(r->left);
- cout<<',';
- stampa_lin(r->right);
- cout<<')';
- }
- else
- cout<<'_';
- }
- /*struct nodo{int info; nodo*left,*right; nodo(int a=0, nodo*b1=0,nodo*b2=0){info=a; left=b1; right=b2;}};
- struct nodoEx{nodo* info; int liv; nodoEx*next; nodoEx(nodo*a=0,int b=0, nodoEx*c=0){info=a; liv=b;next=c;}};
- struct coda{nodoEx* inizio, * fine; coda(nodoEx*a=0, nodoEx*b=0) {inizio=a; fine=b;}};*/
- //PRE=(x è una coda che gestisce una lista di nodoEx ben formata e a punta ad un nodoEx)
- /*coda push_end(coda x, nodoEx*a)
- {
- a->next=0;
- if(x.inizio)
- {
- x.fine->next=a;
- x.fine=a;
- }
- else
- x.inizio=x.fine=a;
- return x;
- }*/
- //POST=(restituisce la coda x che gestisce la lista originale con il nodoEx a aggiunto alla fine della lista)
- //PRE=(C.inizio non è 0)
- /*nodoEx* pop(coda & C)
- {
- nodoEx* x=C.inizio;
- C.inizio=C.inizio->next;
- if(C.inizio==0)
- C.fine=0;
- return x;
- }*/
- //PRE=(albero(R) è un albero binario ben formato, Xe Tcontengonoun numero di posizioni pari al numero deinodi di albero(R))
- void scanliv(nodo*R, int& nliv, int*X, int*T)
- {
- coda albero=coda();
- nodoEx* radice=new nodoEx(R);
- int numele=0;
- albero=push_end(albero,radice);
- /*PRE:R e' un abero binario ben formato,nliv e' il numero di livelli del'albero , X e' l'array che contiene il numero di nodi in ogni livello
- e T e' l'array che contiene il campo info dei nodi dell'albero.Albero e' una coda che contiene i puntatori ai vari nodi dell'albero , radice e' il puntatore
- alla radice dell'albero ,num e' un contatore per il numero di elementi per livello.*/
- while(albero.inizio)
- {
- /*R: R e' un albero binario ben formato , nliv>=0 , X puo' essere vuoto o contenere il numero di nodi dei vari livelli
- nelle varie posizioni al suo interno ,T puo' essere vuoto o contenere il campo info dei nodi dell'albero visto in larghezza da destra a sinistra
- nelle varie posizioni al suo interno, albero puo' essere vuota o contenere un certo numero di puntatori ai nodi dell'albero , numele>=0*/
- nodoEx* attuale=pop(albero);
- if(attuale->info->right)
- {
- nodoEx* right=new nodoEx(attuale->info->right,attuale->liv+1);
- albero=push_end(albero,right);
- }
- if(attuale->info->left)
- {
- nodoEx* left=new nodoEx(attuale->info->left,attuale->liv+1);
- albero=push_end(albero,left);
- }
- if (attuale->liv>nliv)
- {
- *X=numele;
- X=X+1;
- numele=0;
- nliv++;
- }
- numele++;
- *T=attuale->info->info;
- T=T+1;
- if(!albero.inizio)
- {
- *X=numele;
- nliv++;
- }
- }
- }
- //POST=(nlivè è il numero di livelli di albero(R) e X e T contengono i valori descritti nell’Esempio 1, ovviamente per l’albero(R) in input)
- /*PUNTO 1:(Pre->R) Prima del while R e' effettivaente un albero ben formato , liv==0 perche' non e' iniziata la funzione quindi non ho ancora iniziato a
- contare i livelli quindi ok , X e T sono ancora vuoti perche' la funzione non e' ancora iniziata quindi ok,albero contiene il puntatore alla radice quindi ok
- numele==0 perche' non e' iniziata la funzione quindi non ho iniziato a contare gli elementi quindi ok
- PUNTO 2:(R&&COND->R) Durante il while R continuera' ad essere un albero be formato quindi ok nliv >=0 quindi ok , X all'inizio sara' vuoto ma poi si riempira'
- man mano del numero di elementi presenti in ogni livello quindi ok , T all'inizio sara' vuoto ma poi si riempira' man mano dei campi info dei nodi dell'albero
- visto in larghezza da destra a sinistra quindi ok albero verra' riempita e svuotata man mano dei vari nodi dell'albero visto in larghezza da destra a sinistra tramite
- le funzioni pop e push per arrivare poi alla fine ad essere vuota quindi ok , numele >=0 quindi ok
- PUNTO 3:(R&&!COND->POST) Alla fine del while albero.inizio sara' 0 quindi la coda sara' vuota quindi non ci sarano piu' elementi da analizzare che rispetta r e
- -> POSTquindi ok X e T conterranno rispettivamnete il numero di elementi per ogni livello e il campo info dei nodi dell'albero visto in larghezza
- da destra e sinistra ->POST quindi ok numele > 0 nliv > 0 quindi ok*/
- main()
- {
- cout<<"start"<<endl;
- int n, nnodi=0;
- nodo*R=0;
- cin >>n;
- while (n !=-1)
- {
- build_BST(R,n);
- nnodi++;
- cin>>n;
- }
- stampa_lin(R);
- cout<<endl;
- int*X=new int[nnodi],liv=0,*T=new int[nnodi];
- scanliv(R,liv,X,T);
- //DA FARE
- int nt=0;
- for(int i=0; i<liv;i++)
- {
- cout<<" Liv="<<i<<") ";
- for(int j=0; j<X[i]; j++)
- {cout<<T[nt+j]<<' ';}
- cout<<endl;
- nt=nt+X[i];
- }
- cout<<"end"<<endl;
- }
- /*void scanliv(nodo*R, int& nliv, int*X, int*T)
- {
- coda albero=coda();
- nodoEx* radice=new nodoEx(R);
- int liv=0;
- int numele=0;
- albero=push_end(albero,radice);
- while(albero.inizio)
- {
- nodoEx* attuale=pop(albero);
- if(attuale->info->right)
- {
- nodoEx* right=new nodoEx(attuale->info->right,attuale->liv+1);
- albero=push_end(albero,right);
- }
- if(attuale->info->left)
- {
- nodoEx* left=new nodoEx(attuale->info->left,attuale->liv+1);
- albero=push_end(albero,left);
- }
- if (attuale->liv>liv)
- {
- liv++;
- *X=numele;
- X=X+1;
- numele=0;
- nliv++;
- }
- numele++;
- *T=attuale->info->info;
- T=T+1;
- if(!albero.inizio)
- {
- *X=numele;
- }
- }
- }*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement