Programma C++: Albero (2)

#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;

}

};

//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

}

}

}

}

}

albero operator+(int y,albero op1)

{ albero temp(op1);

temp.insert(temp.first,y);

return(temp);

}

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

{

int profsx=0,profdx=0;

if(s!=NULL)

{

profsx=contaprof(s->ps);

profdx=contaprof(s->pd);

if((abs(profsx-profdx))<=1)

{ i=1;

bilavl(s->ps,i);

bilavl(s->pd,i);

}

else i=0;

}

};

void albero:: verificaavl()

{int i;

bilavl(first,i);

if(i==1) cout<<"Albero bilanciato avl "<<endl;

else cout<<"Albero non bilanciato avl "<<endl;

};

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

{ if(s!=NULL)

{ if( s->x>max(s->ps) && s->x<min(s->pd) )

{

i=1;

verord(s->ps,i);

verord(s->pd,i);

}

else i=0;

}

};

void albero::verificaordine()

{

int i;

verord(first,i); �

if(i==1) cout<<"L'albero ordinato "<<endl;

�

else cout<<"L'albero non ordinato "<<endl;

};

int albero::max(nodo *s)

{

if(s!=NULL)

{ int massimo,temp;

massimo=s->x;

temp=max(s->ps);

if(temp>massimo) massimo=temp;

temp=max(s->pd);

if(temp>massimo) massimo=temp;

return massimo;

}

else return(-1000);

};

int albero::min(nodo *s)

{

if(s!=NULL)

{ int minimo,temp;

minimo=s->x;

temp=min(s->ps);

if(temp<minimo) minimo=temp;

temp=min(s->pd);

if(temp<minimo) minimo=temp;

return minimo;

}

else return(1000);

}

albero albero:: operator=(const albero ab)

{

if(ab.first!=NULL)

{ distr(first);

copy(first,ab.first);

return *this;

}

else {

first=NULL;

return *this;

}

};

void albero::operator==(const albero ab)

{ int ris=0;

conf_strutt(first,ab.first,ris);

if(ris) cout<<"Gli alberi sono strutturalmente identici.";

else cout<<"Gli alberi non sono strutturalmente identici.";

};

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

{ if(p==NULL && q==NULL) ris=1;

else

{ if (p!=NULL && q!=NULL)

{ conf_strutt(p->ps,q->ps,ris);

conf_strutt(p->pd,q->pd,ris);

}

else ris=0;

}

};

int albero::contaprofondita()

{ return (contaprof(first)-1);

};

int albero::contaprof(nodo* p)

{ int als,ald;

if (p!=NULL)

{ als=1+contaprof(p->ps);

ald=1+contaprof(p->pd);

if (als>=ald) return als;

else return ald;

}

else return 0;

};

int albero::contanodi()

{

int x=0;

contn(first,x);

return x;

};

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

{

if(p!=NULL)

{ x++;

contn(p->ps,x);

contn(p->pd,x);

}

};

int albero::contafoglie()

{ int x=0;

contf(first,x);

return x;

};

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

{ if(p!=NULL)

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

contf(p->ps,x);

contf(p->pd,x);

}

};

albero albero::operator-()

{ albero temp;

ribalta(temp.first,first);

return temp;

};

void albero::ribalta(nodo* &n,nodo* &v)

{ if(v!=NULL)

{ n=new nodo;

n->x=v->x;

ribalta(n->ps,v->pd);

ribalta(n->pd,v->ps);

}

};

void albero::insert(nodo* &p,int y)

{

if(p==NULL)

{ p=new nodo;

p->x=y;

p->ps=NULL;

p->pd=NULL;

}

else { if(y<p->x) insert(p->ps,y);

else insert(p->pd,y);

}

};

void albero::insert1(nodo* &p,int y)

{ int z;

if(p==NULL)

{ p=new nodo;

p->x=y;

p->ps=NULL;

p->pd=NULL;

}

else {

z=y/2;

if(y==(z*2)) insert1(p->ps,y);

else insert1(p->pd,y);

}

};

albero::albero(const albero &al)

{

if(al.first!=NULL)

copy(first,al.first);

else first=NULL;

};

void albero::copy(nodo* &n,nodo* v)

{

if(v!=NULL)

{

n=new nodo;

n->x=v->x;

copy(n->ps,v->ps);

copy(n->pd,v->pd);

}

else n=NULL;

};

albero::albero()

{ first=new nodo;

first=NULL;

cout<<"Albero inizializzato!!!"<<endl;

};

albero::~albero()

{ distr(first);

cout<<"Albero distrutto "<<endl;

};

void albero::distr(nodo* &p)

{ if(p)

{

distr(p->ps);

distr(p->pd);

delete p;

}

};

void albero::stampa()

{

int x;

cout<<"Inserisci il metodo di visita dell'albero: "<<endl;

cout<<"Visita in pre-ordine 1"<<endl;

cout<<"Visita in in-ordine 2"<<endl;

cout<<"Visita in post-ordine 3"<<endl;

cin>>x;

cout<<"STAMPA DELL'ALBERO "<<endl;

if (x==1) print(first);

if (x==2) print1(first);

if (x==3) print2(first);

};

void albero::print(nodo* p)