Alberi - PostOrder Iterativo

// IMPLEMENTARE UNA PILA CON I METODI DELLO STACK

#include <iostream>
using namespace std;


template <class T> class Nodo{
    T* key;
    Nodo<T> *left, *right, *parent;
    int leftw, rightw; // peso dei sotto alberi

public:
    Nodo(T* key){
        this->key = new T(*key); // copia difensiva
        left = right = parent = NULL;
        leftw = rightw = 0;
    }

    Nodo<T>* getLeft(){ return left; }
    Nodo<T>* getRight(){ return right; }
    Nodo<T>* getParent(){ return parent; }

    int getLeftw(){ return leftw; }
    int getRightw(){ return rightw; }
    T* getKey(){ return new T(*key); } // restituisco la copia della chiave

    void incRightw(){ rightw++; }
    void incLeftw(){ leftw++; }

    void setLeft(Nodo<T>* left){ this->left = left; }
    void setRight(Nodo<T>* right){ this->right = right; }
    void setParent(Nodo<T>* parent){ this->parent = parent; }
    void setKey(T* key){
        if(key) this->key = new T(*key);
        else this->key = NULL;
    }
};

template < class T > class ArrayStack{
    T* q; // array
    int top, length; // top: testa dello stack - length: dimensione dell'array

public:
    ArrayStack(int length){
        q = new T[length];
        this->length = length;
        top = 0;
    }

    int isFull(){ return top == length; }
    int isEmpty(){ return top == 0; }
    int getSize(){ return top; }

    ArrayStack<T>* push(T x){
        if(!isFull())
            q[top++] = x;
        return this;
    }

    T* topItem(){
        return &q[top-1];
    }

    T* pop(){
        if(!isEmpty())
            return &q[--top];
        return NULL;
    }

    void print(){
        for(int i = top-1; i >= 0; i--)
            cout << q[i] << " ";
        cout << endl;
    }
};


template<class H> class SBinaryTree{
    int n;
    Nodo<H>* root; // radice dell'albero

    // stampo prima padri poi figli
    void _preOrder(Nodo<H>* x){
        if(x != NULL){
            cout << *(x->getKey()) << " ";
            _preOrder(x->getLeft());
            _preOrder(x->getRight());
        }
    }

    // stampo prima figli poi padri
    void _postOrder(Nodo<H>* x){
        if(x != NULL){
            _postOrder(x->getLeft());
            _postOrder(x->getRight());
            cout << *(x->getKey()) << " ";
        }
    }

    // stampa in ordine crescente (invertendo getLeft e getRight ordine dec)
    void _inOrder(Nodo<H>* x){
        if(x != NULL){
            _inOrder(x->getLeft());
            cout << *(x->getKey()) << " ";
            _inOrder(x->getRight());
        }
    }

    // questa funzione calcola ricorsivamente l'altezza dell'albero
    int _altezza(Nodo<H>* x, int h){
        if(!x) return h-1;
        int h1 = _altezza(x->getLeft(), h+1);
        int h2 = _altezza(x->getRight(), h+1);
        return h1 > h2 ? h1 : h2;
    }

    // ricerca ricorsiva di un valore nell'albero
    int _search(Nodo<H>* x, H e){
        if(!x) return 0;
        if(*x->getKey() == e) return 1;
        if(*x->getKey() > e) return _search(x->getLeft(), e);
        else return _search(x->getRight(), e);
    }

    /*// ricerca ricorsiva di un nodo nell'albero - aggiunta
    Nodo<H>* _search2(Nodo<H>* x, H e){
        if(!x) return NULL;
        if(*x->getKey() == e) return x;
        if(*x->getKey() > e) return _search2(x->getLeft(), e);
        else return _search2(x->getRight(), e);
    }*/

    Nodo<H>* _search2(H e){
        if(!root) return NULL;
        Nodo<H>* x = root;
        while(x && *x->getKey() != e){
            if(*x->getKey() > e) x = x->getLeft();
            else x = x->getRight();
        }
        return x;
    }

    // ricerca iterativa di un valore nell'albero
    int _searchIt(H e){
        if(!root) return e;
        Nodo<H>* x = root;
        while(x && *x->getKey() != e){
            if(*x->getKey() > e) x = x->getLeft();
            else x = x->getRight();
        }
        if(x) return 1;
        return 0;
    }

    // questa funzione calcola ricorsivamente la profondità di un elemento (se esiste) nell'albero
    int _prof(Nodo<H> *x, H e, int h){
        if(!x) return -1;
        if(*x->getKey() == e) return h;

        int h1 = _prof(x->getLeft(), e, h+1);
        int h2 = _prof(x->getRight(), e, h+1);

        return h1 > h2 ? h1 : h2;
    }

    // questa funzione restituisce il nodo contentente il valore più piccolo dell'albero
    Nodo<H>* _minimum(Nodo<H> *tmp){
        if(!tmp) return NULL;
        Nodo<H> *x = tmp;
        while(x->getLeft()) x = x->getLeft();
        return x;
    }

    // questa funzione restituisce il nodo contenente il valore più grande dell'albero
    Nodo<H>* _maximum(Nodo<H> *tmp){
        if(!tmp) return NULL;
        Nodo<H> *x = tmp;
        while(x->getRight()) x = x->getRight();
        return x;
    }

    // questa funzione restituisce il successore di un nodo
    Nodo<H>* _succ(Nodo<H> *tmp){
        if(!tmp) return NULL;
        if(*tmp->getKey() == *maximum()) return NULL;


        // se il nodo ha figli destri il successore è il figlio sinistro più profondo del primo figlio destro
        if(tmp->getRight()) return _minimum(tmp->getRight());

        // se non ha figli destri il successore è il padre del primo figlio sinistro
        Nodo<H> *x = tmp, *y = tmp->getParent();
        while(y && y->getRight() == x){
            x = y;
            y = y->getParent();
        }
        return y;
    }

    // qusta funzione restituisce il predecessore di un nodo
    Nodo<H>* _pred(Nodo<H> *tmp){
        if(!tmp) return NULL;
        if(*tmp->getKey() == *minimum()) return NULL;

        // se il nodo ha figli sinistri il predecessore è il figlio destro più profondo del primo figlio sinistro
        if(tmp->getLeft()) return _maximum(tmp->getLeft());

        // se non ha figli sinistri il predecessore è il padre del primo figlio destro
        Nodo<H> *x = tmp, *y = tmp->getParent();
        while(y && y->getLeft() == x){
            x = y;
            y = y->getParent();
        }
        return y;
    }

    SBinaryTree<H>* _del(H x, Nodo<H>* r){
        Nodo<H>* tmp = _search2(x);
        if(!tmp) return this;

        // primo caso - 0 figli
        if(!tmp->getLeft() && !tmp->getRight()){
            Nodo<H> *y = tmp->getParent();
            if(!y) root = NULL;
            else if(y->getLeft() == tmp) y->setLeft(NULL);
            else y->setRight(NULL);
            return this;
        }

        // terzo caso - 2 figli
        if(tmp->getLeft() && tmp->getRight()){
            H* s = succ(x);
            _del(*s, tmp->getRight());
            tmp->setKey(s);
            return this;
        }

        // secondo caso - 1 figlio
        Nodo<H> *y = tmp->getParent(),
                *z = tmp->getLeft();

        if(!z) z = tmp->getRight();
        if(!y) root = z;
        else{
            if(y->getLeft() == tmp) y->setLeft(z);
            else y->setRight(z);
        }
        z->setParent(y);
        return this;
    }


public:
    SBinaryTree() : root(NULL), n(0) {}

    void print_inOrder(){
        _inOrder(root);
        cout << endl;
    }

    void print_postOrder(){
        _postOrder(root);
        cout << endl;
    }

    void print_preOrder(){
        _preOrder(root);
        cout << endl;
    }

    // questa funzione inserisce un nodo nell'albero
    SBinaryTree<H>* ins(H x){
        Nodo<H> *nd = new Nodo<H>(&x);

        if(!root){
            root = nd;
            n++;
            return this;
        }

        Nodo<H> *tmp = root, *par = NULL;

        while(tmp){
            par = tmp;
            if(*tmp->getKey() >= x) tmp = tmp->getLeft();
            else tmp = tmp->getRight();
        }

        if(*par->getKey() >= x) par->setLeft(nd);
        else par->setRight(nd);

        nd->setParent(par);
        n++;
        return this;
    }

    int altezza(){
        return _altezza(root, 0);
    }

    int search(H e){
        return _search(root, e);
    }

    int searchIt(H e){
        return _searchIt(e);
    }

    int prof(H e){
        return _prof(root, e, 0);
    }

    H* minimum(){
        Nodo<H> *tmp = _minimum(root);
        if(tmp) return new H(*tmp->getKey());
        return NULL;
    }

    H* maximum(){
        Nodo<H> *tmp = _maximum(root);
        if(tmp) return new H(*tmp->getKey());
        return NULL;
    }

    H* succ(H x){
        Nodo<H>* tmp = _search2(x);
        if(tmp){
            Nodo<H>* z = _succ(tmp);
            if(z) return new H(*z->getKey());
            return NULL;
        }
        return new H(-1);
    }

    H* pred(H x){
        Nodo<H>* tmp = _search2(x);
        if(tmp){
            Nodo<H>* z = _pred(tmp);
            if(z) return new H(*z->getKey());
            return NULL;
        }
        return new H(-1);
    }


    void printInOrderIt(){
        H* tmp = minimum();
        while(tmp){
            cout << *tmp << " ";
            tmp = succ(*tmp);
        }
        cout << endl;
    }

    SBinaryTree<H>* del(H x){
        return _del(x, root);
    }

    void printPreOrderIt(){
        ArrayStack<Nodo<H>*> *S = new ArrayStack<Nodo<H>*>(100);
        S->push(root);
        while( !S->isEmpty() ){
            Nodo<H> *tmp = (*(S->pop()));
            cout << *(tmp->getKey()) << " ";
            if(tmp->getRight()) S->push(tmp->getRight());
            if(tmp->getLeft()) S->push(tmp->getLeft());
        }
        cout << endl;
    }

    void printPostOrderIt(){
        ArrayStack< Nodo<H>* > *S = new ArrayStack< Nodo<H>* >(100);

        Nodo<H>* tmp = root;
        do{
            while(tmp){
                if(tmp->getRight()) S->push(tmp->getRight());
                S->push(tmp);
                tmp = tmp->getLeft();
            }

            tmp = (*(S->pop()));

            if(tmp->getRight() && tmp->getRight() == (*(S->topItem()))){
                S->pop();
                S->push(tmp);
                tmp = tmp->getRight();
            }

            else{
                cout << *tmp->getKey() << " ";
                tmp = NULL;
            }

        }while(!S->isEmpty());
        cout << endl;
    }
};

int main(){
    SBinaryTree<int>* BT = new SBinaryTree<int>();
    BT->ins(9)->ins(14)->ins(7)->ins(5)->ins(8)->ins(13)->ins(18);

    BT->print_postOrder();
    //BT->print_inOrder();
    //BT->printPreOrderIt();
    //BT->print_preOrder();
    BT->printPostOrderIt();
    BT->print_inOrder();

    /*
    cout << *BT->succ(9) << endl;
    cout << *BT->succ(10) << endl;
    cout << *BT->pred(1) << endl;
    cout << *BT->pred(8) << endl;

    BT->ins(8);

    cout << *BT->succ(7) << endl;
    cout << *BT->pred(8) << endl;

    /*BT->print_preOrder();
    BT->print_postOrder();
    BT->print_inOrder();

    cout << BT->search(5) << endl;
    cout << BT->search(2) << endl;
    cout << BT->searchIt(5) << endl;
    cout << BT->searchIt(2) << endl;

    cout << *BT->minimum() << endl;
    cout << *BT->maximum() << endl;*/
}