Advertisement
Guest User

Untitled

a guest
Jun 23rd, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.22 KB | None | 0 0
  1. #include<iostream>
  2.  
  3. #include<fstream>
  4. using namespace std;
  5.  
  6.  
  7. struct nodo{int info; nodo* left,*right; nodo(int a=0, nodo* b=0, nodo*c=0){info=a; left=b;right=c;}};
  8.  
  9.  
  10. int conta(nodo*r){ //conta i nodi di un albero
  11. if(!r)
  12. return 0;
  13. return 1+conta(r->left)+conta(r->right);
  14. }
  15.  
  16. nodo* alberobil (nodo*r, int k){
  17. if(!r)
  18. return new nodo(k,0,0);
  19. if(conta(r->left) > conta(r->right)) //conto i nodi dei sotto-alberi sinistro e destro
  20. r->right=alberobil(r->right,k); //se ho più nodi a sinistra, allora devo bilanciare a destra
  21. else
  22. r->left=alberobil(r->left,k); //altrimenti vado a sinistra
  23. return r; //ritorno la radice
  24. }
  25.  
  26. nodo* buildtree(nodo* r, int n){
  27.  
  28. if(!n)
  29. return r;
  30. int c;
  31. cin>>c;
  32. r=alberobil(r,c);
  33. r=buildtree(r,n-1);
  34. return r;
  35.  
  36. }
  37.  
  38. void stampa_l(nodo*r){
  39. if(r){
  40. cout<<r->info<<"(";
  41. stampa_l(r->left);
  42. cout<<",";
  43. stampa_l(r->right);
  44. cout<<")";
  45. }
  46. else
  47. cout<<"_";
  48. }
  49.  
  50. void sc(int* C){
  51.  
  52. cout << C << " ";
  53. sc(C+1);
  54.  
  55.  
  56.  
  57. }
  58.  
  59. bool isLeaf(nodo* x) {
  60. return !x->left && !x->right;
  61. }
  62.  
  63.  
  64. bool cerca_cam(nodo*r, int k, int y, int*C){
  65.  
  66. if(!r) return false;
  67. if(k<0) return false;
  68. if(isLeaf(r)){
  69. if((k==0) && (r->info!=y))return true;
  70. else return false;
  71. }
  72. //fine casi base
  73. bool a=false;
  74. C[0]=r->info;
  75. if( r->info == y) a=cerca_cam(r->left ,k-1 ,y,C+1);
  76. else a=cerca_cam(r->left,k,y,C+1);
  77. bool b=false;
  78. if(!a){
  79. if( r->info == y) b=cerca_cam(r->right ,k-1 ,y,C+1);
  80. else b=cerca_cam(r->right,k,y,C+1);
  81. }
  82. if(a || b ) return true;
  83. else return false;
  84.  
  85. }
  86.  
  87.  
  88.  
  89. main()
  90. {
  91. int n, k,y;
  92. cin>>n;
  93. nodo* R=buildtree(0,n);//da esercizio 2
  94. cout<<"start"<<endl;
  95. stampa_l(R);
  96.  
  97. cin>>k>>y;
  98. int C[30];
  99. bool b=cerca_cam(R,k,y,C); //da fare
  100. cout<<endl;
  101. if(b)
  102. {cout<<"trovato cammino= "; sc(C);} //sc da fare
  103. else
  104. cout<<"nessun cammino con "<<k<<" valori="<<y<<endl;
  105. cout<<"end";
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement