Programma C++ - Albero Versione 2

Codice C++

#include <iostream.h>

#include <stdlib.h>

typedef struct nodo

{ int x;

struct nodo *ps;

struct nodo *pd;

}nodo;

class albero

{

int cancella_min(nodo* &s);

void distr(nodo* &p);

void print(nodo *p);

void print1(nodo *p);

void print2(nodo *p);

void copy(nodo* &n,nodo* v);

void ribalta(nodo* &n,nodo* &v);

void contf(nodo* &p,int &x);

void contn(nodo* &p,int &n);

int contaprof(nodo* p);

void bilforte(nodo* s,int &i);

void bilavl(nodo* s,int &i);

void verord(nodo *s,int &i);

public:

void cancella_nodo(nodo* &p,int x);

void cambia_radice(nodo* &t,nodo* &p);

int contafoglie();

int contanodi();

int contaprofondita();

void operator==(const albero ab);

albero operator=(const albero ab);

albero operator-();

nodo *first;

albero();

void verificaordine();

void verificaavl();

void conf_strutt(nodo* p,nodo* q,int & ris);

void insert(nodo* &p,int y);

void insert1(nodo* &p,int y);

void verbilforte();

~albero();

int max(nodo *s);

int min(nodo *s);

albero(const albero &al);

void stampa();

void push(int n);

friend albero operator+(int y,albero op1);

};

Metodo privato per verificare se l'albero è bilanciato forte

void albero::bilforte(nodo *s,int &i)

{int nodi_sx=0,nodi_dx=0;

if (s!=NULL)

{contn(s->ps,nodi_sx);

contn(s->pd,nodi_dx);

if (abs(nodi_sx-nodi_dx) <= 1)

{i=1;

bilforte(s->ps,i);

bilforte(s->pd,i);

}

else {i=0;

}

}

};

Metodo pubblico per verificare se un albero è bilanciato forte

void albero :: verbilforte()

{int a=0;

bilforte(first,a);

if(a==1)

{cout<<"\n l'albero bilanciato forte!"<<endl;

}

else

{cout<<"\n l'albero non bilanciato forte!"<<endl;

}

};

Cancellazione di un nodo

//cancella_nodo sostituisce il nodo da cancellare con il minimo del sottoalbero

alla destra del nodo

//cancella_min trova questo minimo; in generale cancella_min trova il minimo in

un albero

int albero::cancella_min (nodo* &p)

{ if (p->ps) cancella_min (p->ps);

else

{ nodo* q; //la funzione cerca il nodo + a sinistra

nell'albero senza figlio sx,

q=p; //lo sostituisce con il suo figlio destro,

p=p->pd; //restituendo il valore del nodo cancellato

return q->x;

}

}

void albero::cancella_nodo (nodo* &p,int x)

{ if (p)

{ if (x<p->x) cancella_nodo (p->ps,x);

if (x>p->x) cancella_nodo (p->pd,x);

if (x==p->x)

{ if (p->ps==NULL) p=p->pd; //in questa riga rientra il caso della foglia

else

{ if (p->pd==NULL) p=p->ps;

else

{ p->x=cancella_min(p->pd); //il nodo ha entrambi i figli

}

}

}

}

}

Inserimento e bilanciamento AVL

albero operator+(int y,albero op1)

{ albero temp(op1);

temp.insert(temp.first,y);

return(temp);

}