Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<fstream>
- using namespace std;
- struct nodo{int info; nodo* left,*right; nodo(int a=0, nodo* b=0, nodo*c=0){info=a; left=b;right=c;}};
- int conta(nodo*r){ //conta i nodi di un albero
- if(!r)
- return 0;
- return 1+conta(r->left)+conta(r->right);
- }
- nodo* alberobil (nodo*r, int k){
- if(!r)
- return new nodo(k,0,0);
- if(conta(r->left) > conta(r->right)) //conto i nodi dei sotto-alberi sinistro e destro
- r->right=alberobil(r->right,k); //se ho più nodi a sinistra, allora devo bilanciare a destra
- else
- r->left=alberobil(r->left,k); //altrimenti vado a sinistra
- return r; //ritorno la radice
- }
- nodo* buildtree(nodo* r, int n){
- if(!n)
- return r;
- int c;
- cin>>c;
- r=alberobil(r,c);
- r=buildtree(r,n-1);
- return r;
- }
- void stampa_l(nodo*r){
- if(r){
- cout<<r->info<<"(";
- stampa_l(r->left);
- cout<<",";
- stampa_l(r->right);
- cout<<")";
- }
- else
- cout<<"_";
- }
- void sc(int* C){
- cout << C << " ";
- sc(C+1);
- }
- bool isLeaf(nodo* x) {
- return !x->left && !x->right;
- }
- bool cerca_cam(nodo*r, int k, int y, int*C){
- if(!r) return false;
- if(k<0) return false;
- if(isLeaf(r)){
- if((k==0) && (r->info!=y))return true;
- else return false;
- }
- //fine casi base
- bool a=false;
- C[0]=r->info;
- if( r->info == y) a=cerca_cam(r->left ,k-1 ,y,C+1);
- else a=cerca_cam(r->left,k,y,C+1);
- bool b=false;
- if(!a){
- if( r->info == y) b=cerca_cam(r->right ,k-1 ,y,C+1);
- else b=cerca_cam(r->right,k,y,C+1);
- }
- if(a || b ) return true;
- else return false;
- }
- main()
- {
- int n, k,y;
- cin>>n;
- nodo* R=buildtree(0,n);//da esercizio 2
- cout<<"start"<<endl;
- stampa_l(R);
- cin>>k>>y;
- int C[30];
- bool b=cerca_cam(R,k,y,C); //da fare
- cout<<endl;
- if(b)
- {cout<<"trovato cammino= "; sc(C);} //sc da fare
- else
- cout<<"nessun cammino con "<<k<<" valori="<<y<<endl;
- cout<<"end";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement