Advertisement
Guest User

Untitled

a guest
May 22nd, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.12 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. struct nodoA{int info; nodoA* left,*right; nodoA(int a=0, nodoA*b=0,nodoA*c=0){info=a; left=b; right=c;}};
  4. struct nodo{nodoA* info; nodo* next; nodo(nodoA* a=0, nodo*b=0){info=a; next=b;}};
  5.  
  6. void stampa_l(nodoA *r)
  7. {
  8. if(r)
  9. {
  10. cout<<r->info<<'(';
  11. stampa_l(r->left);
  12. cout<<',';
  13. stampa_l(r->right);
  14. cout<<')';
  15. }
  16. else
  17. cout<< '_';
  18. }
  19.  
  20. int conta_n(nodoA*r)
  21. {
  22. if(!r) return 0;
  23. else
  24. return conta_n(r->left)+conta_n(r->right)+1;
  25. }
  26.  
  27. nodoA* insert(nodoA*r, int y)
  28. {
  29. if(!r) return new nodoA(y);
  30.  
  31. if(conta_n(r->left)<=conta_n(r->right))
  32. r->left=insert(r->left,y);
  33. else
  34. r->right=insert(r->right,y);
  35. return r;
  36. }
  37.  
  38. nodoA* buildtree(nodoA*r, int dim)
  39. {
  40. if(dim)
  41. {
  42. int z;
  43. cin>>z;
  44. nodoA*x=insert(r,z);
  45. return buildtree(x,dim-1);
  46. }
  47. return r;
  48. }
  49.  
  50.  
  51. void riempi(int*P,int m)
  52. {
  53. if(m)
  54. {
  55. cin>>*P;
  56. riempi(P+1,m-1);
  57. }
  58. }
  59.  
  60. void stampaL(nodo*a)
  61. {
  62. if(a)
  63. {
  64. cout<<a->info->info<<' ';
  65. stampaL(a->next);
  66. }
  67. else
  68. cout<<endl;
  69. }
  70.  
  71. nodo * match(nodoA* r, int* P, int dimP){
  72. if(!r){
  73. return 0;
  74. }
  75. if(dimP==1 && r->info==*P){
  76. return new nodo(r,0);
  77. }
  78.  
  79. nodo * sinistro, *destro;
  80.  
  81. if(*P==r->info){
  82. sinistro=match(r->left, P+1, dimP-1);
  83. if(sinistro){
  84. return new nodo (r, sinistro);
  85. }
  86. destro=match(r->right, P+1, dimP-1);
  87. if(destro){
  88. return new nodo(r, destro);
  89. }
  90. }
  91. if(*P!=r->info){
  92. sinistro=match(r->left, P, dimP);
  93. if(sinistro){
  94. return sinistro;
  95. }
  96. destro=match(r->right, P, dimP);
  97. if(destro){
  98. return destro;
  99. }
  100. }
  101. return 0;
  102. }
  103.  
  104. main()
  105. {
  106. int n,m;
  107. cout<<"start"<<endl;
  108. cin>> n;
  109. nodoA*R=buildtree(0,n);
  110. stampa_l(R);
  111. cout<<endl;
  112. int P[50];
  113. cin>> m;
  114. riempi(P,m);
  115. nodo*a=match(R,P,m);
  116. if(a)
  117. stampaL(a);
  118. else
  119. cout<<"no match found"<<endl;
  120. cout<<"end"<<endl;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement