alberiEsempioVinc.cpp

#include <iostream>

using namespace std;

template <typename H> class Node{
    private:
        H key;
        Node<H> *parent, *left, *right;
    public:
        Node(H key){
        this->key = key;
        parent = left = right = NULL;
        }
        H getKey(){ return key; }
        Node<H>* getParent(){ return parent; }
        Node<H>* getLeft(){ return left; }
        Node<H>* getRight(){ return right; }
        void setParent(Node<H>* parent){ this->parent = parent; }
        void setLeft(Node<H>* left){ this->left = left; }
        void setRight(Node<H>* right){ this->right = right; }
        void setKey(H key) { this->key = key; }
        bool isLeaf(){
            if(left==NULL && right==NULL)
                return 1;
            return 0;
        }
};

template <typename H> class Tree{
    private:
        Node<H>* root;
    public:
        Tree(){ root = NULL; }
        Node<H>* getRoot() { return root; }
        bool isEmpty(){
            if(root==NULL)
                return 1;
            return 0;
        }
        Tree<H>* ins(H x){
            Node<H>* temp = new Node<H>(x);
            if(root==NULL){
                root = temp;
                return this;
            }

            Node<H>* t = root;
            Node<H>* p = NULL;
            while(t){
                p = t;
                if( t->getKey() > x ) t = t->getLeft();
                else t = t->getRight();
            }
            if( p->getKey() > x ){
              p->setLeft(temp);
              temp->setParent(p);
              return this;
            }
            p->setRight(temp);
            temp->setParent(p);
            return this;
        /*METODO NOSTRO
            Node<H>* temp = new Node<H>(x);
            if(isEmpty()){
                root = temp;
                return this;
            }
            Node<H>* n = root;
            while(1){
                if(n->isLeaf()){
                    if(temp->getKey() < n->getKey()){
                        n->setLeft(temp);
                        temp->setParent(n);
                        return this;
                    }
                    n->setRight(temp);
                    temp->setParent(n);
                    return this;
                }
                if(temp->getKey() < n->getKey()){
                    if(!n->getLeft()){
                        n->setLeft(temp);
                        temp->setParent(n);
                        return this;
                    }
                    n = n->getLeft();
                }
                else{
                    if(!n->getRight()){
                        n->setRight(temp);
                        temp->setParent(n);
                        return this;
                    }
                    n = n->getRight();
                }
            }*/
        }
        Node<H>* getNext(Node<H> *x){
            if(getMax(root)->getKey() == x->getKey()) return NULL;
            if(x->getRight()) return getMin(x->getRight());
            while(x->getParent()->getKey() <= x->getKey()) x=x->getParent();
            return x->getParent();
        }
        void del(H x){
            if(!search(x)){
                cout << "Elemento inesistente" << endl;
                return;
            }
            Node<H> *temp = _search(x);
            if(temp->isLeaf()){
                Node<H> *par = temp->getParent();
                if(!par){
                    root = NULL;
                    delete(temp);
                    return;
                }
                if(par->getLeft() == temp){
                    par->setLeft(NULL);
                    delete(temp);
                    return;
                }
                par->setRight(NULL);
                delete(temp);
                return;
            }
            if(!(temp->getLeft() && temp->getRight())){         //#1
                if(temp->getLeft()){                            //#2
                    if(temp->getParent()->getLeft() == temp){   //#3
                        temp->getParent()->setLeft(temp->getLeft());
                        temp->getLeft()->setParent(temp->getParent());
                        delete(temp);
                        return;
                    }                                           //!#3
                    if(temp->getParent()->getRight() == temp){  //#3
                        temp->getParent()->setRight(temp->getLeft());
                        temp->getLeft()->setParent(temp->getParent());
                        delete(temp);
                        return;
                    }                                           //!#3
                }                                               //!#2
                if(temp->getParent()->getLeft() == temp){       //#2
                        temp->getParent()->setLeft(temp->getRight());
                        temp->getRight()->setParent(temp->getParent());
                        delete(temp);
                        return;
                }                                               //!#2
                temp->getParent()->setRight(temp->getRight());
                temp->getRight()->setParent(temp->getParent());
                delete(temp);
                return;
            }                                                   //!#1
            Node<H> *sup = getNext(temp);
            H p = sup->getKey();
            sup->setKey(temp->getKey());
            temp->setKey(p);
            del(sup->getKey());
            return;
        }
        int search(H x){
            if(_search(x)) return 1;
            return 0;
        }
        Node<H>* _search(H x){
            if(isEmpty())
                return NULL;
            Node<H> *temp = root;
            while(temp!=NULL){
                if(temp->getKey() == x) return temp;
                if(temp->getKey()>x)
                    temp = temp->getLeft();
                else temp = temp->getRight();
            }
            return NULL;
        }
        Node<H>* getMin(Node<H>* r){
            if( r == NULL ) return NULL;
            while(r->getLeft()) r = r->getLeft();
            cout << r->getKey();
            return r;
        }
        Node<H>* getMax(Node<H>* r){
            if( r == NULL ) return NULL;
            while(r->getRight()) r = r->getRight();
            cout << r->getKey();
            return r;
        }
        void rec_inorder(Node<H>* r){
            if(!r) return;
            rec_inorder(r->getLeft());
            cout << r->getKey() << " ";
            rec_inorder(r->getRight());
        }
        void rec_postorder(Node<H>* r){
            if(!r) return;
            rec_inorder(r->getLeft());
            rec_inorder(r->getRight());
            cout << r->getKey() << " ";
        }
        void rec_preorder(Node<H>* r){
            if(!r) return;
            cout << r->getKey() << " ";
            rec_inorder(r->getLeft());
            rec_inorder(r->getRight());
        }
};

int main(){
    Tree<int> *T = new Tree<int>();
    T->ins(5)->ins(56)->ins(67);//->ins(2)->ins(20)->ins(1)->ins(4)->ins(6)->ins(7)->ins(8)->ins(9)->ins(10);
    T->rec_inorder(T->getRoot()); cout << endl ;
    T->rec_postorder(T->getRoot()); cout << endl ;
    T->rec_preorder(T->getRoot()); cout << endl ;
    cout << endl << "Massimo " ;
    T->getMax(T->getRoot());
    cout << endl << "Minimo " ;
    T->getMin(T->getRoot());
    cout << endl ;
    T->del(5);
    T->rec_inorder(T->getRoot()); cout << endl ;
    /*T->del(4);
    T->rec_inorder(T->getRoot()); cout << endl ;
    T->del(6);
    T->rec_inorder(T->getRoot()); cout << endl ;
    T->del(5);
    T->rec_inorder(T->getRoot()); cout << endl ;
    /*T->del(1);
    T->rec_inorder(T->getRoot()); cout << endl ;
    T->del(10);
    T->rec_inorder(T->getRoot()); cout << endl ;
    T->del(5);
    T->rec_inorder(T->getRoot()); cout << endl ;*/
 return 0;
}