#include <iostream>

using namespace std;
struct nodo{
    int key;
    nodo *figlio_sx;
    nodo *figlio_dx;
};
nodo* ricercaNodoRIC(nodo *root, int n);
nodo* ricercaNodoITR(nodo *root, int n);
nodo* treeMin(nodo *root);
nodo* treeMax(nodo *root);
void aggiungiNodoRic(nodo *root,int n);
void aggiungiNodo(nodo *root,int n);
void pre_order(nodo *root);
void symmetric_order(nodo *root);
void post_order(nodo *root);
bool is_empty_tree(nodo *root);
bool is_empty_node(nodo *node);
int campo_info(nodo *node);
nodo* link_sx(nodo *node);
nodo* link_dx(nodo *node);
struct nodo* deleteNode(struct nodo* root, int key);




int main(int argc, char** argv) {
    nodo *root = new nodo();
    cout<<"Is empty tree? \t\t\t\t"<<boolalpha<<is_empty_tree(root)<<endl;
    //          5
    //      2       7
    //   1    3   6   9
    root->key=5;
    aggiungiNodo(root, 7);
    aggiungiNodo(root, 2);
    aggiungiNodoRic(root, 3);
    aggiungiNodoRic(root, 1);
    aggiungiNodoRic(root, 6);

    aggiungiNodo(root, 9);
    aggiungiNodo(root, 10);

    cout<<"stampa 'pre order:'\t\t\t";pre_order(root);
    cout<<endl<<"stampa 'symmetric'\t\t\t";symmetric_order(root);
    cout<<endl<<"stampa 'post order'\t\t\t";post_order(root);

    cout<<endl<<"Is empty tree? \t\t\t\t"<<boolalpha<<is_empty_tree(root);

    cout<<endl<<"chiave di valore minimo: \t"<<treeMin(root)->key<<endl;
    cout<<"chiave di valore massimo: \t"<<treeMax(root)->key<<endl;

    //cancellando la root, si va a prendere il valore minore del suo sottoalbero destro,
    //in modo da mantentere l'ordine del BST.
    int el_da_elimin=2;
    deleteNode(root,el_da_elimin);
    cout<<"ho cancellato l'elemento "<<el_da_elimin<<":\t";
    pre_order(root);

    cout<<endl<<"ricerca di 1 (ricorsiva):  \t"<<ricercaNodoRIC(root,10);
    cout<<endl<<"ricerca di 1 (iterativa):  \t"<<ricercaNodoITR(root,10);
    cout<<endl<<"ricerca di un numero non presente (ricorsiva):  \t"<<ricercaNodoRIC(root,100);

    cout<<endl<<endl;
    //system("PAUSE");
    return 0;
}

//La funzione restituisce il puntatote al nodo cercato,
//oppure NULL se l'elemento non Ë presente
nodo* ricercaNodoRIC(nodo *root, int n){
    if(root==NULL || n == root->key){
        return root;
    }else if(n>root->key){
        return ricercaNodoRIC(root->figlio_dx,n);
    }else if(n<root->key){
        return ricercaNodoRIC(root->figlio_sx,n);
    }
    return NULL;
}
nodo* ricercaNodoITR(nodo *root, int n){
    while(n<root->key && root->figlio_sx!=NULL){
        root = root->figlio_sx;
    }
    while(n>root->key && root->figlio_dx!=NULL){
        root = root->figlio_dx;
    }
    if(root==NULL || n == root->key){
        return root;
    }
    return NULL;
}
//Il valore minimo Ë il nodo foglia del sottoalbero pi˘ a sinista
//ossia prima foglia che incontra l'inorder
nodo* treeMin(nodo *root){
    if(root==NULL){
        return root; //albero vuoto
    }else{
        if(root->figlio_sx==NULL){
            return root;
        }else{
            return treeMin(root->figlio_sx);
        }
    }
}
nodo* treeMax(nodo *root){
    if(root==NULL){
        return root; //albero vuoto
    }else{
        if(root->figlio_dx==NULL){
            return root;
        }else{
            return treeMax(root->figlio_dx);
        }
    }
}


void aggiungiNodoRic(nodo *root,int n){
    nodo *newNode = new nodo();
    newNode->key=n;
    newNode->figlio_dx=NULL;
    newNode->figlio_sx=NULL;

    if(n>root->key){ //le chiavi sono uniche, non esiste caso di uguaglianza
        if(root->figlio_dx==NULL){
            root->figlio_dx=newNode;
        }else{
            aggiungiNodoRic(root->figlio_dx, n);
        }
    }else if(n<root->key){
        if(root->figlio_sx==NULL){
            root->figlio_sx=newNode;
        }else{
            aggiungiNodoRic(root->figlio_sx, n);
        }
    }
}

void aggiungiNodo(nodo *root,int n){
    nodo *newNode = new nodo();
    newNode->key=n;
    newNode->figlio_dx=NULL;
    newNode->figlio_sx=NULL;
    while(n<root->key && root->figlio_sx!=NULL){
        root = root->figlio_sx;
    }
    while(n>=root->key && root->figlio_dx!=NULL){
        root = root->figlio_dx;
    }
    if(n>root->key){ //le chiavi sono uniche, non esiste caso di uguaglianza
        root->figlio_dx=newNode;
    }else if(n<root->key){
        root->figlio_sx=newNode;
    }

}

// STAMPE
void pre_order(nodo *root) {
    if(root!=NULL){
        cout << root->key << " ";
        pre_order(root->figlio_sx);
        pre_order(root->figlio_dx);
    }

}

void symmetric_order(nodo *root){
    if(root!=NULL){
        symmetric_order(root->figlio_sx);
        cout << root->key << " ";
        symmetric_order(root->figlio_dx);
    }
}

void post_order(nodo *root){
    if(root!=NULL){
        post_order(root->figlio_sx);
        post_order(root->figlio_dx);
        cout << root->key << " ";
    }
}

bool is_empty_tree(nodo *root){
    if(root->figlio_dx== NULL
       && root->figlio_sx==NULL
       && root->key==NULL){
        return true;
    }else{
        return false;
    }
}

bool is_empty_node(nodo *node){
    if(node->figlio_dx== NULL
       && node->figlio_sx==NULL
       && node->key==NULL){
        return true;
    }else{
        return false;
    }
}

int campo_info(nodo *node){
    return node->key;
}

nodo* link_sx(nodo *node){
    return node->figlio_sx;
}

nodo* link_dx(nodo *node){
    return node->figlio_dx;
}


struct nodo* deleteNode(struct nodo* root, int key){
    if (root == NULL){return root;}
    /**
     * RICERCA DEL NODO DA ELIMINARE
     **/
    // Se la key da eliminare è più piccola della key di root
    // allora essa si trova nel sottoalbero sinistro
    if (key < root->key){
        root->figlio_sx = deleteNode(root->figlio_sx, key);
        //Se è più grande si trova a destra.
    }else if (key > root->key){
        root->figlio_dx = deleteNode(root->figlio_dx, key);

        /**
         * NODO TROVATO
         **/
        // se la key è la stessa della root allora questo è il nodo da eliminare
    }else{
        // se il nodo ha un figlio, esso prende il posto di questo nodo
        if (root->figlio_sx == NULL){
            struct nodo *temp = root->figlio_dx;
            root->figlio_sx=NULL;
            root->figlio_dx=NULL;
            root->key=NULL;
            return temp;
        }else if (root->figlio_dx == NULL){
            cout<<"ho cancellato: "<<root->key<<endl;
            struct nodo *temp = root->figlio_sx;
            root->figlio_sx=NULL;
            root->figlio_dx=NULL;
            root->key=NULL;
            return temp;
        }

        // Se il nodo ha più di due figli, bisogna prendere il minore del suo sottoalbero destro
        // Quindi mi salvo questo minore in un nodo temporaneo
        struct nodo* temp = treeMin(root->figlio_dx);
        root->key = temp->key;
        root->figlio_dx = deleteNode(root->figlio_dx, temp->key);
    }
    return root;
}