Advertisement
Guest User

Untitled

a guest
Sep 17th, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.05 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct nodo{int info; nodo*left,*right; nodo(int a=0, nodo*b1=0,nodo*b2=0){info=a; left=b1; right=b2;}};
  5. struct nodoEx{nodo* info; int liv; nodoEx*next; nodoEx(nodo*a=0,int b=0, nodoEx*c=0){info=a; liv=b;next=c;}};
  6. struct coda{nodoEx* inizio, * fine; coda(nodoEx*a=0, nodoEx*b=0) {inizio=a; fine=b;}};
  7. //PRE=(x è una coda che gestisce una lista di nodoEx ben formata e a punta ad un nodoEx)
  8. coda push_end(coda x, nodoEx*a)
  9. {
  10. a->next=0;
  11. if(x.inizio)
  12. {
  13. x.fine->next=a;
  14. x.fine=a;
  15. }
  16. else
  17. x.inizio=x.fine=a;
  18.  
  19. return x;
  20. }
  21. //POST=(restituisce la coda x che gestisce la lista originale con il nodoEx a aggiunto alla fine della lista)
  22. //PRE=(C.inizio non è 0)
  23. nodoEx* pop(coda & C)
  24. {
  25. nodoEx* x=C.inizio;
  26. C.inizio=C.inizio->next;
  27. if(C.inizio==0)
  28. C.fine=0;
  29. return x;
  30. }
  31. //POST=(modifica C eliminando il suo primo nodoEx e restituendolo col return )
  32. void build_BST(nodo*&r, int x)
  33. {
  34. if(!r)
  35. r=new nodo(x);
  36. else
  37. {
  38. nodo*q=r;
  39. bool continua=true;
  40. while (r && continua)
  41. {
  42.  
  43. if(r->info >=x)
  44. if(r->left)
  45. r=r->left;
  46. else
  47. {r->left=new nodo(x); continua=false;}
  48. else
  49. if(r->right)
  50. r=r->right;
  51. else
  52. {r->right=new nodo(x); continua=false;}
  53.  
  54. }
  55.  
  56. r=q;
  57.  
  58. }
  59. }
  60. void stampa_lin(nodo*r)
  61. {
  62. if(r)
  63. {
  64. cout <<'['<<r->info<<']'<<'(';
  65. stampa_lin(r->left);
  66. cout<<',';
  67. stampa_lin(r->right);
  68. cout<<')';
  69. }
  70. else
  71. cout<<'_';
  72. }
  73. /*struct nodo{int info; nodo*left,*right; nodo(int a=0, nodo*b1=0,nodo*b2=0){info=a; left=b1; right=b2;}};
  74. struct nodoEx{nodo* info; int liv; nodoEx*next; nodoEx(nodo*a=0,int b=0, nodoEx*c=0){info=a; liv=b;next=c;}};
  75. struct coda{nodoEx* inizio, * fine; coda(nodoEx*a=0, nodoEx*b=0) {inizio=a; fine=b;}};*/
  76. //PRE=(x è una coda che gestisce una lista di nodoEx ben formata e a punta ad un nodoEx)
  77. /*coda push_end(coda x, nodoEx*a)
  78. {
  79. a->next=0;
  80. if(x.inizio)
  81. {
  82. x.fine->next=a;
  83. x.fine=a;
  84. }
  85. else
  86. x.inizio=x.fine=a;
  87.  
  88. return x;
  89. }*/
  90. //POST=(restituisce la coda x che gestisce la lista originale con il nodoEx a aggiunto alla fine della lista)
  91. //PRE=(C.inizio non è 0)
  92. /*nodoEx* pop(coda & C)
  93. {
  94. nodoEx* x=C.inizio;
  95. C.inizio=C.inizio->next;
  96. if(C.inizio==0)
  97. C.fine=0;
  98. return x;
  99. }*/
  100. //PRE=(albero(R) è un albero binario ben formato, Xe Tcontengonoun numero di posizioni pari al numero deinodi di albero(R))
  101. void scanliv(nodo*R, int& nliv, int*X, int*T)
  102. {
  103. coda albero=coda();
  104. nodoEx* radice=new nodoEx(R);
  105. int numele=0;
  106. albero=push_end(albero,radice);
  107. /*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
  108. 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
  109. alla radice dell'albero ,num e' un contatore per il numero di elementi per livello.*/
  110. while(albero.inizio)
  111. {
  112. /*R: R e' un albero binario ben formato , nliv>=0 , X puo' essere vuoto o contenere il numero di nodi dei vari livelli
  113. 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
  114. nelle varie posizioni al suo interno, albero puo' essere vuota o contenere un certo numero di puntatori ai nodi dell'albero , numele>=0*/
  115. nodoEx* attuale=pop(albero);
  116. if(attuale->info->right)
  117. {
  118. nodoEx* right=new nodoEx(attuale->info->right,attuale->liv+1);
  119. albero=push_end(albero,right);
  120. }
  121. if(attuale->info->left)
  122. {
  123. nodoEx* left=new nodoEx(attuale->info->left,attuale->liv+1);
  124. albero=push_end(albero,left);
  125. }
  126. if (attuale->liv>nliv)
  127. {
  128. *X=numele;
  129. X=X+1;
  130. numele=0;
  131. nliv++;
  132. }
  133. numele++;
  134. *T=attuale->info->info;
  135. T=T+1;
  136. if(!albero.inizio)
  137. {
  138. *X=numele;
  139. nliv++;
  140. }
  141. }
  142. }
  143. //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)
  144. /*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
  145. 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
  146. numele==0 perche' non e' iniziata la funzione quindi non ho iniziato a contare gli elementi quindi ok
  147. 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'
  148. 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
  149. 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
  150. le funzioni pop e push per arrivare poi alla fine ad essere vuota quindi ok , numele >=0 quindi ok
  151. 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
  152. -> 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
  153. da destra e sinistra ->POST quindi ok numele > 0 nliv > 0 quindi ok*/
  154.  
  155. main()
  156. {
  157. cout<<"start"<<endl;
  158. int n, nnodi=0;
  159. nodo*R=0;
  160. cin >>n;
  161. while (n !=-1)
  162. {
  163. build_BST(R,n);
  164. nnodi++;
  165. cin>>n;
  166. }
  167. stampa_lin(R);
  168. cout<<endl;
  169. int*X=new int[nnodi],liv=0,*T=new int[nnodi];
  170. scanliv(R,liv,X,T);
  171. //DA FARE
  172. int nt=0;
  173. for(int i=0; i<liv;i++)
  174. {
  175. cout<<" Liv="<<i<<") ";
  176. for(int j=0; j<X[i]; j++)
  177. {cout<<T[nt+j]<<' ';}
  178. cout<<endl;
  179. nt=nt+X[i];
  180. }
  181. cout<<"end"<<endl;
  182. }
  183. /*void scanliv(nodo*R, int& nliv, int*X, int*T)
  184. {
  185. coda albero=coda();
  186. nodoEx* radice=new nodoEx(R);
  187. int liv=0;
  188. int numele=0;
  189. albero=push_end(albero,radice);
  190. while(albero.inizio)
  191. {
  192. nodoEx* attuale=pop(albero);
  193. if(attuale->info->right)
  194. {
  195. nodoEx* right=new nodoEx(attuale->info->right,attuale->liv+1);
  196. albero=push_end(albero,right);
  197. }
  198. if(attuale->info->left)
  199. {
  200. nodoEx* left=new nodoEx(attuale->info->left,attuale->liv+1);
  201. albero=push_end(albero,left);
  202. }
  203. if (attuale->liv>liv)
  204. {
  205. liv++;
  206. *X=numele;
  207. X=X+1;
  208. numele=0;
  209. nliv++;
  210. }
  211. numele++;
  212. *T=attuale->info->info;
  213. T=T+1;
  214. if(!albero.inizio)
  215. {
  216. *X=numele;
  217. }
  218. }
  219. }*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement