ABR Completo

#include <iostream>
using namespace std;
class Nodo
{
    private:
        int key;
        Nodo *parent;
        Nodo *left;
        Nodo *right;
//        T data;

    public:
        Nodo(int key/*, T data*/):parent{nullptr}, left{nullptr},right{nullptr} {this->key=key;/*this->data=data;*/}
        Nodo(Nodo *x){
        setKey(x->getKey());
        setParent(x->getParent());
        setLeft(x->getLeft());
        setRight(x->getRight());
        }
        void setKey(int tmp){key=tmp;};
        int getKey(){return key;}
        void setParent(Nodo *p){parent=p;}
        Nodo *getParent(){return parent;}
        void setLeft(Nodo *l){left=l;}
        Nodo *getLeft(){return left;}
        void setRight(Nodo *r){right=r;}
        Nodo *getRight(){return right;}
        ///T& getData(){return data;}
        /*Nodo& operator=(Nodo *b){
        this->setParent(b->getParent());
        this->setLeft(b->getLeft());
        this->setRight(b->getRight());
        this->setKey(b->getKey());
        return *this;
        };*/
        void Copy(Nodo *b);
        virtual ~Nodo() {}

};
void Nodo::Copy(Nodo *b){
if(b){
parent=b->getParent();
left=b->getLeft();
right=b->getRight();
key=b->getKey();
}
}
class BinarySearchTree
{
    private:
        Nodo *root;

    public:
        BinarySearchTree(){root=nullptr;}
        virtual ~BinarySearchTree();  //TODO

        Nodo *getRoot(){return root;}
        void setRoot(Nodo *x){root=x;};
        void insertNodo(int key);
        void delNodo(int key);  //TODO
        void transplant(Nodo *a,Nodo *b);
        void inorder(Nodo *x);//simmetrica
        void preorder(Nodo *x);//anticipata
        void postorder(Nodo *x);//differita

        Nodo *minimum(Nodo *x);
        Nodo *maximum(Nodo *x);

        Nodo *searchNodo(int key);
        Nodo *predecessor(Nodo *x);
        Nodo *predecessor(int x);
        Nodo *successor(Nodo *x);
        Nodo *successor(int x);
        void DeleteDouble(Nodo *x);
};
void BinarySearchTree::DeleteDouble(Nodo *x){
if(x!=nullptr){
DeleteDouble(x->getLeft());
DeleteDouble(x->getRight());
if(successor(x)!=nullptr && successor(x)->getKey()==x->getKey())
  delNodo(x->getKey());
}
}
void BinarySearchTree::transplant(Nodo *a,Nodo *b){
if(a){
if(!a->getParent())
  this->setRoot(b);
else if(a==a->getParent()->getLeft())
  a->getParent()->setLeft(b);
else
  a->getParent()->setRight(b);
if(b)//se non mi hai passato un nodo vuoto, imposta come Parent di b il Parent di a.
  b->setParent(a->getParent());
}
}
void BinarySearchTree::delNodo(int key){
Nodo *a=this->searchNodo(key);
if(!a->getLeft())
  transplant(a,a->getRight());
else if(!a->getRight())
  transplant(a,a->getLeft());
else{
  Nodo *suc(this->minimum(a->getRight()));
  if(suc->getParent()!=a){
  transplant(suc,suc->getRight());
  suc->setRight(a->getRight());
  suc->getRight()->setParent(suc);
  }
  transplant(a,suc);
  suc->setLeft(a->getLeft());
  suc->getLeft()->setParent(suc);
}
}
void BinarySearchTree::insertNodo(int key){
    Nodo *z=new Nodo(key);
    Nodo *y=nullptr;
    Nodo *x=root;
    while(x!=nullptr){
        y=x;
        if(z->getKey()<x->getKey())
            x=x->getLeft();
        else
            x=x->getRight();
    }
    z->setParent(y);
    if(y==nullptr)
        root=z;
    else if(z->getKey()<y->getKey())
        y->setLeft(z);
    else
        y->setRight(z);
}

void BinarySearchTree::inorder(Nodo *x){
    if(x!=nullptr){
        inorder(x->getLeft());
        cout<<x->getKey()<<" ";
        inorder(x->getRight());
    }
}

void BinarySearchTree::preorder(Nodo *x){
    if(x!=nullptr){
        cout<<x->getKey()<<" ";
        inorder(x->getLeft());
        inorder(x->getRight());
    }
}

void BinarySearchTree::postorder(Nodo *x){
    if(x!=nullptr){
        inorder(x->getLeft());
        inorder(x->getRight());
        cout<<x->getKey()<<" ";
    }
}

Nodo *BinarySearchTree::minimum(Nodo *x){
    while(x->getLeft()!= nullptr)
        x=x->getLeft();
    return x;
}

Nodo *BinarySearchTree::maximum(Nodo *x){
    while(x->getRight()!= nullptr)
        x=x->getRight();
    return x;
}
Nodo *BinarySearchTree::predecessor(Nodo *x){
   if(x->getLeft())
     return this->maximum(x->getLeft());
    Nodo *y=x->getParent();
    while(y && x==y->getLeft()){
    x=y;
    y=y->getParent();
}
return y;
}
Nodo *BinarySearchTree::predecessor(int x){
Nodo *tmp=searchNodo(x);
if(tmp)
   return predecessor(tmp);
return tmp;
}
Nodo *BinarySearchTree::successor(Nodo *x){
if(x->getRight()!=NULL)
  return this->minimum(x->getRight());
Nodo *y=x->getParent();
while(y && x==y->getRight()){
     x=y;
     y=y->getParent();
}
return y;
}
Nodo *BinarySearchTree::successor(int x){
Nodo *tmp=searchNodo(x);
if(tmp)
   return successor(tmp);
return tmp;
}
Nodo *BinarySearchTree::searchNodo(int key){
Nodo *tmp=getRoot();
while(tmp && tmp->getKey()!=key){
    if(tmp->getKey()<key)
       tmp=tmp->getRight();
    else
       tmp=tmp->getLeft();
}
return tmp;

}
BinarySearchTree::~BinarySearchTree()
{
    //dtor
};
int main()
{
    BinarySearchTree bt;
    Nodo *n;
    int tmp;
    short choice;
    bt.insertNodo(16);
    bt.insertNodo(13);
    bt.insertNodo(17);
    bt.insertNodo(15);
    bt.insertNodo(12);
    bt.insertNodo(11);
    bt.insertNodo(10);
    bt.insertNodo(9);
    while(1){
    cout<<"1)PreOrder\n2)InOrder\n3)PostOrder\n4)Insert\n5)Ricerca\n6)Cancella\n7)Cerca predeccessore\n8)Cerca successore\n9)Trova minimo\n10)Trova massimo\n11)Ricava famiglia\n12)Elimina doppioni\n13)Uscire\n";
    cin>>choice;
    switch(choice){
    case 1:
    cout<<"Pre Order visit: "<<endl;
    bt.preorder(bt.getRoot());
    break;
    case 2:
    cout<<endl<<"In Order visit: "<<endl;
    bt.inorder(bt.getRoot());
    break;
    case 3:
    cout<<endl<<"Post Order visit: "<<endl;
    bt.postorder(bt.getRoot());
    cout<<endl;
    break;
    case 4:
    cout<<"Inserire il valore dell'elemento da aggiungere: "<<endl;
    cin>>tmp;
    bt.insertNodo(tmp);
    break;
    case 6:
    cout<<"Inserire il valore dell'elemento da eliminare: "<<endl;
    cin>>tmp;
    bt.delNodo(tmp);
    break;
    case 5:
    cout<<"Inserire valore della chiave del nodo da ricercare: ";
    cin>>tmp;
    if(bt.searchNodo(tmp))
       cout<<"Il nodo e' stato trovato"<<endl;
    else
       cout<<"Il nodo non e' stato trovato"<<endl;
    break;
    case 7:
    cout<<"Inserire elemento di cui vuoi calcolare il predecessore: ";
    cin>>tmp;
    if(n=bt.predecessor(tmp))
       cout<<n->getKey()<<endl;
    else
       cout<<"No data found"<<endl;
    break;
    case 8:
    cout<<"Inserire elemento di cui vuoi calcolare il successore: ";
    cin>>tmp;
    if(n=bt.successor(tmp))
       cout<<n->getKey()<<endl;
    else
       cout<<"No data found"<<endl;
    break;
    case 9:
    if(n=bt.minimum(bt.getRoot()))
       cout<<"Il minimo e': "<<n->getKey()<<endl;
    else
      cout<<"L'albero e' vuoto"<<endl;
    break;
    case 10:
    if(n=bt.maximum(bt.getRoot()))
       cout<<"Il massimo e': "<<n->getKey()<<endl;
    else
       cout<<"L'albero e' vuoto"<<endl;
    break;
    case 11:
    cout<<"Inserire valore della chiave del nodo di cui vuoi conoscere la famiglia: ";
    cin>>tmp;
    if(n=bt.searchNodo(tmp)){
    if(n->getParent())
      cout<<"Il padre e': "<<n->getParent()->getKey()<<endl;
    else
      cout<<"Il nodo e' radice"<<endl;
    if(n->getLeft())
      cout<<"Il figlio sinistro e': "<<n->getLeft()->getKey()<<endl;
    else
      cout<<"Il nodo non ha figlio sinistro"<<endl;
    if(n->getRight())
      cout<<"Il figlio destro e': "<<n->getRight()->getKey()<<endl;
    else
      cout<<"Il nodo non ha figlio destro"<<endl;
    }
    else
      cout<<"Il nodo non e' stato trovato\n";
    break;
    case 12:
       bt.DeleteDouble(bt.getRoot());
       break;
    case 13:
       exit(0);
    default:
       cout<<"Comando non riconosciuto, riprovare\n";
       break;
}
cout<<endl;
}
}