Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ALGO_IT(T){
- ret=0;
- sx=0;
- dx=0;
- curr=T;
- last=NIL;
- stack_sx=NIL; //uso stack per salvare il sx
- stack_curr=NIL;
- stack_ret=NIL; //uso stack per ret dato che mi servirà alla fine delle
- while(curr!=NIL ||stack_curr!=NIL){ //chiamate ricorsive
- if(curr!=NIL){
- if(curr->key%2==1)
- ret=curr->key;
- push(stack_curr,curr); //prima di scendere salvo ret
- push(stack_ret,ret);
- curr=curr->sx;
- ret=0; //reinizializzo ret ad ogni discesa come nell'algo ric
- }else{
- curr=top(stack_curr);
- if(curr->dx!=NIL && curr->dx!=last){ //se scendo a destra salvo il sx=ret nello stack_sx
- sx=ret;
- push(stack_sx,sx);
- curr=curr->dx;
- ret=0; //reinizializzo ret ad ogni discesa come nell' algo ric
- }else{
- if(curr->dx!=NIL){ //se risalgo da destra allora sx lo trovo nello stack_sx
- sx=top(stack_sx); //mentre ret è l'ultimo valore ottenuto
- POP(stack_sx,sx);
- dx=ret;
- }else{ //se non ho il figlio destro allora il sx=ret mentre dx=0
- sx=ret; //cioè al valore di ret nella discesa a destra nell'algo
- dx=0; //ricorsivo
- }
- ret=top(stack_ret); //recupero ret dallo stack_ret
- POP(stack_ret);
- ret+=sx+dx; //operazioni dell'algo ric.
- last=curr;
- curr=NIL;
- POP(stack_curr);
- }
- }
- }
- return ret;
- }
Advertisement
Add Comment
Please, Sign In to add comment