#include <cstdlib>
#include <iostream>
#include "Albero2.h"

using namespace std;
/*
Scrivere un programma che:
 - acquisisca un albero binario di elementi di tipo intero e lo stampi
 - per ogni nodo:
	- se e' un figlio destro, incrementi di 1 il valore dei figli
	- se e' un figlio sinistro, scambi i valori dei figli (se ci sono entrambi)
 - stampi l'albero risultante
*/

void visita (BinAlbero<int>& alb)
{    
   if (!alb.binAlberoVuoto())
   {
         Coda<BinAlbero<int>::Nodo> s;
         s.inCoda(alb.binRadice());
         while (!s.codaVuota()){
               BinAlbero<int>::Nodo nn=s.leggiCoda(); // visito un nodo ...
               s.fuoriCoda();
               BinAlbero<int>::Nodo padre = alb.binPadre(nn);
               if (padre!=NULL)
               {
                  if (alb.figlioDestro(padre) == nn)
                  {
                     int valore=alb.leggiNodo(alb.figlioSinistro(nn));
                     valore++;
                     alb.scriviNodo(alb.figlioSinistro(nn),valore);
                     valore=alb.leggiNodo(alb.figlioDestro(nn));
                     valore++;
                     alb.scriviNodo(alb.figlioDestro(nn),valore);
                  }
                  else
                  {
                        int sx=alb.leggiNodo(alb.figlioSinistro(nn));
                        int dx=alb.leggiNodo(alb.figlioDestro(nn));
                        alb.scriviNodo(alb.figlioDestro(nn),sx);
                        alb.scriviNodo(alb.figlioSinistro(nn),dx);
                  }
               }
               if (!alb.sinistroVuoto(nn)) s.inCoda(alb.figlioSinistro(nn)); // ... e accodo i figli
               if (!alb.destroVuoto(nn)) s.inCoda(alb.figlioDestro(nn));               
         }
   }  
}

BinAlbero<int> acquisisci()
{
    BinAlbero<int> tree;
    BinAlbero<int>::Nodo radice = new Cella<int>;
    tree.insBinRadice(radice);
    tree.scriviNodo(tree.binRadice(),1);
    tree.insFiglioSinistro(radice);
    tree.insFiglioDestro(radice);
    tree.scriviNodo(tree.figlioSinistro(tree.binRadice()),200);
    tree.scriviNodo(tree.figlioDestro(tree.binRadice()),300);
    radice = tree.figlioSinistro(radice);
    tree.insFiglioSinistro(radice);
    tree.insFiglioDestro(radice);
    tree.scriviNodo(tree.figlioSinistro(radice),4);
    tree.scriviNodo(tree.figlioDestro(radice),4400);    
    radice = tree.figlioDestro(radice);
    tree.insFiglioSinistro(radice);
    tree.insFiglioDestro(radice);
    tree.scriviNodo(tree.figlioSinistro(radice),125);
    tree.scriviNodo(tree.figlioDestro(radice),2);    
    radice=tree.binRadice();
    radice=tree.figlioDestro(radice);
    tree.insFiglioSinistro(radice);
    tree.insFiglioDestro(radice);
    tree.scriviNodo(tree.figlioSinistro(radice),13);
    tree.scriviNodo(tree.figlioDestro(radice),17);    
    return tree;             
}

int main(int argc, char *argv[])
{
    cout << "albero input" << endl;
    BinAlbero<int> tree = acquisisci();
    tree.stampa(tree.binRadice(),0);
    cout << "Processing..." << endl;
    visita(tree);
    cout << "albero output" << endl;
    tree.stampa(tree.binRadice(),0);
    
    system("PAUSE");
    return EXIT_SUCCESS;
}