GENERAZIONE DI ALBERI CASUALI NON ORDINATI
Per generare un albero con chiavi casuali e non ordinato è
sufficiente utilizzare una funzione rand() per ottenere chiavi
casuali e inserire queste chiavi una volta a destra e una volta
a sinistra nell’albero, come mostrato dal codice che segue.
GENERAZIONE DI ALBERI CASUALI NON ORDINATI
Tnodo AlberoCasuale(int n)
{
//Dato un intero n restituisce un albero di interi di altezza n NON ORDINATO
if (n==0)
return Insert(rand()%100 ,NULL,NULL);
else
return Insert(rand()%100,AlberoCasuale(n-1),AlberoCasuale(n-1));
}
Tnodo Insert(int info1, Tnodo As, Tnodo Ad) {
// PER INSERIRE UNA FOGLIA SI CHIAMA CON Insert(Numero,NULL,NULL)
Tnodo A2;
A2= new Tnodo;
A2->inf=info1;
A2->ps=As;
A2->ps=Ad;
return A2;
}
Allegato: alberi generale
Verificare se due alberi sono isomorfi
Due alberi binari ordinati si dicono isomorfi solo se sono
identici, cioè le radici sono uguali, i rispettivi sottoalberi sinistri
sono identici ed i rispettivi sottoalberi destri sono identici.
Per gli alberi non ordinati, è del tutto indifferente se una chiave
è presente nel sottoalbero destro o nel sottoalbero sinistro
della radice. Pertanto due alberi non ordinati sono isomorfi se
le loro radici contengono lo stesso elemento ed inoltre o
accade che i due sottoalberi sinistri ed i due sottoalberi destri
sono isomorfi tra loro oppure accade che il sottoalbero sinistro
del primo sia isomorfo al sottoalbero destro del secondo ed il
sottoalbero destro del primo è isomorfo al sottoalbero sinistro
del secondo.
Una procedura ricorsiva, che sfrutta questa definizione
permette di verificare se due alberi A e B, non ordinati, sono
isomorfi tra di loro.
bool uguale(Tnodo A, Tnodo B)
{ // VERIFICA SE DUE ALBERI SONO ISOMORFI
if (A==NULL || B==NULL)
return (A==NULL) && (B==NULL);
// due alberi sono uguali se sono entrambi NULL
else
return (A->key==B->key) && uguale(A->left,B->left) && uguale(A->right,B->right);
}
Allegato: albIsomorf
ESERCIZIO
Siano A e B due alberi BST verificare se B è un sottoalbero di A.
bool cerca(Tnodo A1, Tnodo B1)
{ // CERCA SE IN A C'E' LA CHIAVE DELLA ROOT DI B
// SE LA TROVA VERIFICA CHE I DUE SOTTO ALBERI SONO UGUALI
if (A1!=NULL) {
if ((A1->key)==(B1->key))
{ if (uguale(A1,B1)==true)
return true;}
else
{ if (A1->key>B1->key)
return cerca(A1->left,B1);
else
return cerca(A1->right,B1); }
} else
return false; }
CONTARE I NODI DI UN ALBERO
In generale se si vogliono contare i nodi di un albero
contenenti un elemento che soddisfa una proprietà data P
si adotta il seguente schema per la funzione conta:
if (A==NULL) return 0;
else
if (A->key soddisfa P) k=1
else k=0
return k +conta(A->left)+conta(A->right)
dove l’espressione booleana in parentesi nei casi in cui P
sia una proprietà difficile da verificare può diventare una
funzione booleana che verifica se A->key gode o meno
della proprietà.
ESERCIZIO
Scrivere una procedura tale che assegnato un albero binario non
ordinato di interi positivi restituisca un puntatore al valore massimo e
indichi quante volte questo valore massimo è contenuto nell'albero.
void CercaMax(Tnodo ANonOrd, int &Max, int &Cont)
{
if (ANonOrd!=NULL)
{
CercaMax(ANonOrd->left,Max,Cont);
if (ANonOrd->key>Max)
{
Max=ANonOrd->key;
Cont=1;
}
else
if (ANonOrd->key==Max) Cont=Cont+1;
CercaMax(ANonOrd->right,Max,Cont);
}
Allegato: alb non ordinati
}
ESERCIZIO
// Scrivere una procedura che assegnato un albero binario di interi
//positivi non ordinato e due numeri positivi N1 e N2 restituisca la
// quantità di numeri pari compresi tra N1 e N2.
void Elab_Albero(Tnodo ANonOrd,int N1a, int N2a, int & Cont)
{
if (ANonOrd!=NULL)
{
Elab_Albero(ANonOrd->left, N1a,N2a,Cont);
if ((ANonOrd->key%2==0)&&(ANonOrd->key>N1a)&&(ANonOrd->key<N2a))
{
Cont=Cont+1;
cout<<" Chiave=> "<<ANonOrd->key<<" cont "<<Cont<<endl;
}
Elab_Albero(ANonOrd->right, N1a,N2a,Cont);
}
}
Allegato: alb non ordinati
ALBERI BILANCIATI
Ricordiamo che un albero si dice bilanciato se il livello di tutte
le foglie è uguale all’altezza dell’albero o a questa stessa
altezza meno 1.
Dato ad esempio, un albero BST di interi non bilanciato, si
attraversa l’albero secondo la procedura IN-ORDER, e per
ogni chiave letta:
•Si inserisce la chiave in un vettore;
•Al termine del processo il vettore risulta ordinato in maniera
crescente;
•Si leggono i dati del vettore come per una ricerca binaria,
dividendolo in sottovettori e inserendo i valori via via letti in un
albero BST che risulterà ordinato e bilanciato.
BILANCIAMENTO
{ Dato un albero binario BST non bilanciato costruire un albero bilanciato }
// MAIN
int main () {
Tnodo Bilanciato,A1;
int V[40];
RTnodo Nodo;
CreaAlbero(A1);
writeTree(A1,1);cout<<endl;
int vmax=0;
DaAlberoAVettore(A1 , V, vmax);
Bilanciato=vet2alb(V, 0 ,vmax-1);
writeTree(Bilanciato,1);cout<<endl;
if (ControlloBilanciamento(Bilanciato)==0)
cout<<" L'albero e' bilanciato "<<endl;
else
if (ControlloBilanciamento(Bilanciato)==1)
cout<<" L'albero non e' bilanciato "<<endl;
cout<<" FINE"<<endl;
system("pause");
}
Trasforma
DaAlberoAVettore
Bilanciamento
vet2alb
Controllo bilanciamento
Stampa
1
2
1
3
2
4
3
5
4
6
5
7
6
7
8
8
9
9
10
11
12
13
14
10 11 12 13 14 15
8
4
12
2
1
6
3
5
10
7
9
14
11
13
15
15
DaAlberoAVettore(A1 , V, vmax);
Bilanciato=vet2alb(V, 0 ,vmax-1);
writeTree(Bilanciato,1);cout<<endl;
if (ControlloBilanciamento(Bilanciato)==0)
cout<<" L'albero e' bilanciato "<<endl;
else
if (ControlloBilanciamento(Bilanciato)==1)
cout<<" L'albero non e' bilanciato "<<endl;
void DaAlberoAVettore(Tnodo A, int V[], int &max)
{ int i;
if (A!=NULL)
{
DaAlberoAVettore(A->left, V, max);
V[max]=A->key;
max=max+1;
DaAlberoAVettore(A->right, V, max);
}
}
Tnodo vet2alb(int Vx[], int i ,int j)
{int k;
if (i>j)
return NULL;
else
if (i==j)
return UnisciAlberi(Vx[i],NULL,NULL);
else
{
k=(i+j)/2;
return UnisciAlberi(Vx[k],vet2alb(Vx,i,k-1),vet2alb(Vx,k+1,j));
}
}
Tnodo UnisciAlberi(int e,Tnodo a, Tnodo b)
{
Tnodo c;
c=new RTnodo;
c->left=a;
c->right=b;
c->key=e;
return c;
}
DaAlberoAVettore(A1 , V, vmax);
Bilanciato=vet2alb(V, 0 ,vmax-1);
writeTree(Bilanciato,1);cout<<endl;
if (ControlloBilanciamento(Bilanciato)==0)
cout<<" L'albero e' bilanciato "<<endl;
else
if (ControlloBilanciamento(Bilanciato)==1)
cout<<" L'albero non e' bilanciato "<<endl;
int ControlloBilanciamento(Tnodo A) //supponiamo un max=10000 e min=0
{int cmaxx,cmin;
DaAlberoAVettore(A1 , V, vmax);
cmaxx=0;
Bilanciato=vet2alb(V, 0 ,vmax-1);
cmin=10000;
writeTree(Bilanciato,1);cout<<endl;
if (ControlloBilanciamento(Bilanciato)==0)
cammino(A,0,cmaxx,cmin);
cout<<" L'albero e' bilanciato "<<endl;
return (cmaxx-cmin);
else
}
if (ControlloBilanciamento(Bilanciato)==1)
cout<<" L'albero e' quasi bilanciato
"<<endl;
void cammino(Tnodo A, int livello, int &cmax, int &cmin)
{
if (A!=NULL)
{
if ((A->right==NULL)|| (A->left==NULL))
{ if (cmax<livello)
cmax=livello;
if (cmin>livello)
cmin=livello;
}
cammino(A->right,livello+1,cmax,cmin);
cammino(A->left,livello+1,cmax,cmin);
}
else
return ;
}
L’animazione che segue mostra come opera
l’algoritmo prima descritto e successivamente
viene mostrato un suo output.
Allegato: albBilanciato
Vet2ALb(V,1,Vmax);
UnisciAlberi(Vx[K],vet2alb(Vx,I,K-1),vet2alb(vx,K+1,j))
a
b
c
d
e
f
g
1
2
3
4
5
6
7
d
UnisciAlberi(Vx[4],vet2alb(Vx,1,3),vet2alb(vx, 5,7))
d
Vet2ALb(V,1,7);
K=4
Vet2ALb(V,1,3);
K=2
b
UnisciAlberi(Vx[2],vet2alb(Vx,1,1),vet2alb(vx, 3,3))
a
Vet2ALb(V,1,1);
K=1
c
Vet2ALb(V,3,3);
K=3
b
a
f
c
e
g
f
Vet2ALb(V,5,7);
K=6
UnisciAlberi(Vx[4],vet2alb(Vx,1,3),vet2alb(vx, 6,7))
e
Vet2ALb(V,5,5);
K=5
Tnodo vet2alb(int Vx[], int i ,int j)
{int k;
if (i>j)
return NULL;
else
if (i==j)
return
UnisciAlberi(Vx[i],NULL,NULL);
else
{
k=(i+j)/2;
return UnisciAlberi(Vx[k],vet2alb(Vx,i,k-1),vet2alb(Vx,k+1,j)); }
g
Vet2ALb(V,7,7);
K=7
20
30
35
40
41
42
43
44
45
0
1
2
3
4
5
6
7
8
35
40
44
41
45
30
20
43
35
42
Tnodo vet2alb(int Vx[], int i ,int j)
{int k;
if (i>j)
return NULL;
albBilan
else
if (i==j)
return UnisciAlberi(Vx[i],NULL,NULL);
else
{ k=(i+j)/2;
return UnisciAlberi(Vx[k],vet2alb(Vx,i,k-1),vet2alb(Vx,k+1,j)); } }
ESERCIZI
•Verificare se un albero A contiene almeno uno zero.
•Verificare se l’albero A contiene solo zeri.
Verificare se un albero A contiene almeno uno zero.
bool unozero(Pnodo A) {
if(A==NULL)return false;
else if A->key =0 return true;
else return ((unozero(A->left) || (unozero(A->right) );
}
Verificare se l’albero A contiene solo zeri.
bool tuttizero(Pnodo A) {
if(A==NULL) return true;
else
if (A-> key!=0) return false;
else
return(tuttizero(A->left) && tuttizero(A-> right) );
}
ESERCIZIO
Sviluppare una funzione che, assegnato un nodo T di un
albero binario, restituisce il puntatore al nodo "Zio” di T se
esiste, NULL altrimenti (nodo "zio" è quel nodo che è figlio
dello stesso genitore del nodo T).
ESERCIZIO
LA FAMIGLIA
{calcola le parentele }
Supponiamo di avere una famiglia tale che ogni suo membro
ha al più due figli.
Descritte le parentele secondo un albero non ordinato scrivere
le funzioni
char Padre
{dato un nome determinare se ha un padre e chi è}
void Figlio
{dato un nome determinare se ha uno o due figli e chi sono}
char Nonno
{dato un nome determinare chi è il nonno}
char Fratello
{dato un nome determinare se ha un fratello e chi è}
char Cugino
{dato un nome determinare se ha un Cugino e chi è}
nonno
5
padre
zio
7
1
figlio
5
cugino
11
10
4
3
Di seguito si mostra lo pseudo-codice che risolve il problema
dell’albero genealogico.
Cerca(A, Candidate, Pcand, Pparent)
Cerca(A, figlio, Pfiglio, Ppadre)  Ppadre->key
padre
figlio
Cerca(A, Ppadre->key, Ppadre, Pnonno)  Ppadre ->left ->key|| Ppadre ->right ->key
Cerca(A, Ppadre->key, Ppadre, Pnonno)  Pnonno ->key
nonno
Cerca(A, Ppadre->key, Ppadre, Pnonno)  Pnonno ->left ->key  Pnonno ->right ->key
zio
Cerca(A, Ppadre->key, Ppadre, Pnonno) 
(Pnonno ->left ->left ->key  Pnonno ->left ->right ->key)||
nonno
(Pnonno -> right ->left ->key  Pnonno -> right ->right ->key)||
5
padre
zio
7
1
figlio
5
cugino
11
10
4
3
9
cugino
ALBERO GENEALOGICO
Assegnato un albero A trovare rispettivamente
il padre di un assegnato figlio, il figlio di un
assegnato padre, il nonno di un assegnato
nipote, lo zio di un assegnato nipote,
// MAIN
cerca_il_padre(A);
cerca_il_figlio(A);
cerca_il_nonno(A);
cerca_lo_zio(A);
void cerca_il_padre(Tnodo Tree)
{int figlio;
Tnodo Candidato=NULL;Tnodo Padre;
cout<<" Cerca il padre di ";cin>>figlio;
Cerca( Tree, figlio, Candidato, Padre);
if (Candidato==NULL) cout<<" Il figlio non c'e'"<<endl;
else {
if (Padre==NULL) cout<<" E' orfano"<<endl;
else
cout<<"Il padre di "<<Candidato->key<<" e' "<<Padre->key<<endl;
}
}
ALBERO GENEALOGICO
void cerca_il_figlio(Tnodo Tree)
{int padre;
Tnodo Candidato,Padre;
cout<<" Cerca il figlio di ";cin>>padre;
Cerca( Tree, padre, Candidato, Padre);
if (Candidato==NULL)cout<<" Il padre non c'e' "<<endl;
else {
if ((Candidato->left==NULL)&&(Candidato->right==NULL))
cout<<" Non ha figli "<<endl;
else
{if (Candidato->left!=NULL)
cout<<"Il figlio sinistro di "<<padre<<" e' "<<Candidato->left->key<<endl;
if (Candidato->right!=NULL)
cout<<"Il figlio destro di "<<padre<<" e' "<<Candidato->right->key<<endl;
}}
}
void cerca_lo_zio(Tnodo Tree)
{int figlio;
Tnodo Candidato,Padre,Nonno;
cout<<" Cerca lo zio di ";cin>>figlio;
Cerca( Tree, figlio, Candidato, Padre);
if (Candidato==NULL) cout<<" Il figlio non c'e'"<<endl;
else
{
if (Padre==NULL) cout<<" E' orfano"<<endl;
else
{ cout<<"Il padre di "<<Candidato->key<<" e' "<<Padre->key<<endl;
Cerca( Tree, Padre->key, Candidato, Nonno);
if (Nonno==NULL) cout<<" il padre e' orfano"<<endl;
else
{cout<<"Il nonno di "<<Candidato->key<<" e' "<<Nonno->key<<endl;
if ((Nonno->left==NULL)&&(Nonno->right==Padre))
cout<<figlio<<" non ha zio "<<endl;
if ((Nonno->left!=NULL)&&(Nonno->left!=Padre))
cout<<"Lo zio di "<<figlio<<" e' "<<Nonno->left->key;}
if ((Nonno->right!=NULL)&&(Nonno->right!=Padre))
cout<<"Lo zio di "<<figlio<<" e' "<<Nonno->right->key;}
} }
void cerca_il_nonno(Tnodo Tree)
{int figlio;
Tnodo Candidato,Padre,Nonno;
cout<<" Cerca il nonno di ";cin>>figlio;
Cerca( Tree, figlio, Candidato, Padre);
if (Candidato==NULL) cout<<" Il figlio non c'e'"<<endl;
else {
if (Padre==NULL) cout<<" E' orfano"<<endl;
else
{ cout<<"Il padre di "<<Candidato->key<<" e' "<<Padre->key<<endl;
Cerca( Tree, Padre->key, Candidato, Nonno);
if (Nonno==NULL) cout<<" il padre e' orfano"<<endl;
else
cout<<"Il nonno di "<<Candidato->key<<" e' "<<Nonno->key<<endl; }
}
ESERCIZIO
Dati due alberi non ordinati verificare che
ordinatamente tutte le chiavi dell'albero A sono multipli
delle chiavi dell'albero B.
Allegato: alberimultipli
ESERCIZIO
1- Scrivere un algoritmo che dato un albero binario scriva le
chiavi in ordine prima crescente e poi decrescente.
2- Assegnato un albero BST di numeri interi, fornire una
procedura ricorsiva che dica quanti nodi, la cui chiave è un
numero dispari, hanno sottoalbero destro nullo.
3- Assegnato un albero non ordinato di interi scrivere una
procedura ricorsiva che trasformi l'albero non ordinato in un
albero BST. Determinare l'altezza dell'albero non ordinato e
dell'albero BST.
4 -Dato un albero binario calcolare quanti nodi hanno il
sottoalbero sinistro nullo.
ESERCIZIO
Sia A un albero binario non ordinato. Ogni qualvolta un
nodo dell'albero ha al più un figlio e presenta il campo
numero uguale a zero eliminare il nodo sostituendolo con
l’unico figlio.
Esempio:
5
5
7
0
0
11
0
4
7
3
11
0
4
3
ESERCIZI
Dato un albero binario calcolare quanti nodi hanno il
sottoalbero sinistro nullo.
Dato un albero binario ordinato di interi definire una funzione
ricorsiva che restituisca il numero di elementi positivi in esso
presenti.
Dato un albero BST contare quanti nodi ci sono al di sotto di
un nodo preassegnato.
Dato un albero BST e la chiave K di un suo nodo determinare
il valore della chiave più piccola e di quella più grande del
sotto albero di K.
Dato un albero non ordinato contare quanti nodi hanno la
stessa chiave e quanti figli sono multipli del padre.