Pages: [1]   Go Down
Print
Author Topic: esercizio di ieri (senza templates)  (Read 942 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Dario Catalano
docente
Apprendista Forumista
****
Offline Offline

Posts: 153


« on: 12-06-2015, 09:02:55 »

#include<iostream>
/*
Corso di Programmazione II - Prof. Dario Catalano.
Soluzione della prova d'esame del 24/06/2014.
Il compito è svolto senza fare uso di templates
*/

using namespace std;

class BST   {
public:
   virtual BST* insert(int* x) =0;
   virtual BST* del(int* x) =0;
   virtual int search(int* x) =0;
   virtual void naturalFill(int* v)=0;
   virtual void postorderPrint()=0;
   virtual void printLevel(int l)=0;
};

class Nodo   {
private:
   Nodo* padre, *left, *right;
   int* chiave;
   int depth;
public:
   Nodo(int* val) {   //Costruttore
      chiave=val;
      padre=left=right=NULL;
      depth=0; }
   int* getChiave() {return chiave;}   
   int getDepth() {return depth;}
   void setDepth(int p) {depth=p;}
   void setPadre(Nodo* p) {padre=p;}
   Nodo* getPadre() {return padre;}
   Nodo* getDestro() {return right;}
   void setDestro(Nodo* p) {right=p;}
   Nodo* getSinistro() {return left;}
   void setSinistro(Nodo* p) {left=p;}
   void setChiave(int* p) {chiave=p;}
};

class albero : public BST {
private:
   Nodo* radice;
   int size; //Numero totale di nodi dell'albero
public:
   albero() {radice=NULL; size=0;}
   Nodo* getRoot() {return radice;}
   int getSize() {return size;}
   void setRoot(Nodo* p) {radice=p;}
   void setSize(int p)   {size=p;}
   BST* insert(int* x);
   void postorder(Nodo* p, int level);
   void postorderPrint();
   Nodo* searchPointer (int* p); // restituisce il nodo
                          // dove si trova p
   int search (int* p); 
   Nodo* searchInt(int p); // come searchPointer
         // ma prende in input un intero piuttosto
         // che un puntatore. Usata nel main per testare la
         // procedura del
   void Trapianta(Nodo* u, Nodo* v);
   Nodo* Minimo(Nodo* p);
   BST* del(int* p);
   void printLevel(int l);
   void naturalFill(int* v);
   Nodo* successore(Nodo* p);
};

BST* albero :: insert (int* key)   
{   
   Nodo *x=radice, *y=NULL;
   
   while (x!=NULL) {
      y=x;
      if (*key < *(x->getChiave())) x=x->getSinistro();
      else x=x->getDestro();
      }
   Nodo* nuovo=new Nodo(key);
   nuovo->setPadre(y);
   if (y==NULL) {
      radice=nuovo;
      nuovo->setDepth(0);
      }
   else if (*key < *(y->getChiave())) y->setSinistro(nuovo);
   else y->setDestro(nuovo);
   size++;
   if (y!=NULL)
      nuovo->setDepth((nuovo->getPadre()->getDepth())+1);
   return this;
}


void albero :: postorderPrint ()
{
    cout << endl;
   postorder(radice,-1);
   cout << endl;
      
}

void albero :: postorder (Nodo* p, int level) {
/* La postorder quando level=-1 si limita a scrivere
il contenuto di tutti i nodi che visita. Se level=k
(k!=-1) scrive il contenuto solo dei nodi che si
trovano a livello k */
   if (p!=NULL) {
       postorder(p->getSinistro(),level);
       postorder(p->getDestro(),level);
       if ((level==-1) || (p->getDepth()==level))
          cout << *(p->getChiave()) << "\t"; 
    }
}

int albero:: search (int* p) {
   Nodo *temp=radice;
   
   while ((temp!=NULL) && (*(temp->getChiave())!=*p))
      if  (*(temp->getChiave()) >= *p) temp=temp->getSinistro();
      else temp=temp->getDestro();
   if (temp!=NULL) return 1;
   else return 0;
}

Nodo* albero:: searchInt (int p) {
   Nodo *temp=radice;
   
   while ((temp!=NULL) && (*(temp->getChiave())!=p))
      if  (*(temp->getChiave()) >= p) temp=temp->getSinistro();
      else temp=temp->getDestro();
   return temp;
}

Nodo* albero:: searchPointer (int* p) {
   Nodo *temp=radice;
   
   while ((temp!=NULL) && (*(temp->getChiave())!=*p))
      if  (*(temp->getChiave()) >= *p) temp=temp->getSinistro();
      else temp=temp->getDestro();
   return temp;
}

void albero:: Trapianta(Nodo* u, Nodo* v)   {
   if (u->getPadre()==NULL) radice=v;          
   else if (u==u->getPadre()->getSinistro())          
       u->getPadre()->setSinistro(v);
   else 
      u->getPadre()->setDestro(v);
   if (v!=NULL)                   
       v->setPadre(u->getPadre());
}

Nodo* albero::Minimo(Nodo* x)   {
   Nodo* min=x;
   
   while(min->getSinistro() != NULL) min=min->getSinistro();
   return min;
}

BST* albero :: del (int *p) {
   Nodo* y;
      
   Nodo* z=searchPointer(p);
   if (z->getSinistro()==NULL) Trapianta(z, z->getDestro());
   else if (z->getDestro()==NULL)
      Trapianta(z, z->getSinistro());
   else {
      y=Minimo(z->getDestro());
      if (y->getPadre()!=z)   {
         Trapianta(y,y->getDestro());
         y->setDestro(z->getDestro());
         y->getDestro()->setPadre(y);
         }
      Trapianta(z,y);
      y->setSinistro(z->getSinistro());
      y->getSinistro()->setPadre(y);    
   }
   delete z;
   size--;
   return this;
}

void albero::printLevel(int l)   {
   cout << endl;
   postorder(radice,l);
   cout << endl;       
}

Nodo* albero:: successore(Nodo* x)   {
   if (x==NULL) return NULL;
   if (x->getDestro()!=NULL) return Minimo(x->getDestro());
   Nodo* y=x->getPadre();
   while ((y!=NULL) && (*(y->getChiave()) < *(x->getChiave())) )
      y=y->getPadre();
   return y;
}

void albero::naturalFill(int* v)
{   Nodo* current=Minimo(radice);
   Nodo* temp;
   
   for (int i=0; i<size; i++) {
      if (current!=NULL)
         current->setChiave(v+i);
      current=successore(current);
      }
}


int main()
{   
   albero Tree;
   int vettore[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
   int input[]={23,4,6,8,12,21,5,9,7,3,16,2,24};

   for(int i=0; i<13; i++)
      Tree.insert(input+i);   
   Tree.postorderPrint();
   Tree.printLevel(3);
   /*
   Nodo* elemento=Tree.searchInt(21);
   if (elemento!=NULL)
      Tree.del(elemento->getChiave());
   Tree.postorderPrint();    
   */
   Tree.naturalFill(vettore);
   
   Tree.postorderPrint();
   Tree.printLevel(3);
   
   return 0;   
}
Logged
Pages: [1]   Go Up
Print
Jump to: