Di seguito ci rifaremo alla seguente struct per definire un
nodo di un albero:
struct RTnodo
{
int key;
RTnodo *left, *right;
};
typedef RTnodo* Tnodo;
Per esplorare un albero vi sono tre diverse modalità.
ALGORITMI DI ATTRAVERSAMENTO DI BST
Visitare tutti i nodi di un BST di interi,
attraversando:
• il sotto albero sinistro;
• la radice;
• il sotto albero destro;
Visitare tutti i nodi di un BST di interi,
attraversando:
• la radice;
• il sotto albero sinistro;
• il sotto albero destro;
Visitare tutti i nodi di un BST di interi,
attraversando:
• il sotto albero sinistro;
• il sotto albero destro;
• la radice;
INORDER
PREORDER
POSTORDER
I codici per gli attraversamenti sono:
void InOrder(Tnodo A) {
if (A!=NULL) {
InOrder(A->left);
cout<<A->key<<" ";
InOrder(A->right);
}
else
cout<<endl;
}
void Preorder(Tnodo A) {
if (A!=NULL) {
cout<<A->key<<" ";
Preorder(A->left);
Preorder(A->right);
}
else
cout<<" ";
}
void Postorder(Tnodo A) {
if (A!=NULL) {
Postorder(A->left);
Postorder(A->right);
cout<<A->key<<" ";
}
else
cout<<" ";
}
50
60
40
30
20
44
35
41
55
42
70
46
43
45
80
48
90
OPERAZIONI SUI BST
Tnode
Left
Key
Right
struct RTnodo
{
int key;
RTnodo *left, *right;
};
typedef RTnodo* Tnodo;
Le principali operazioni che ci interessa definire sono:
•Creazione di un albero
•Inserimento di un nuovo nodo con un valore assegnato al
campo dati Key e NULL ai campi Left e Right
•Selezione un nodo data una chiave
•Fornire informazioni sull’albero (altezza, numero nodi, livelli,
figli, etc.)
•Cancellazione di un nodo
OPERAZIONI SUI BST
Ogni nodo di un BST punta ad altri due nodi, ciascuno dei quali è una
variabile dinamica di tipo struct.
Quindi una variabile di tipo RTnodo, cioè un puntatore alla radice di
un BST, che è a sua volta una variabile BST, può essere passata da un
blocco ad un altro. In altre parole dato un nodo di un BST, questo è
radice per i suoi sottoalberi e i nodi a cui punta sono a loro volta radici
di altri sottoalberi. Pertanto possiamo adoperare ricorsivamente queste
variabili.
struct RTnodo
{
int key;
char info;
RTnodo *left, *right;
};
typedef RTnodo* Tnodo;
NomeAlbero
Left
Key
Info
Right
COSTRUZIONE DI UN BST DI INTERI
Supponiamo di introdurre da tastiera i numeri seguenti
nell’ordine indicato.
50 40 60 30 44 55 70 20 35 42 46 80 41 43 45 48 90
Man mano che introduciamo i numeri questi devono essere
inseriti in un albero BST rispettando le proprietà che lo
caratterizzano.
Quindi l’introduzione di 50 produrrà la creazione della radice
dell’albero. L’introduzione di 40 prevede che esso sia
rappresentato come figlio sinistro di 50 essendo minore di
quest’ultimo. Il numero 60 andrà invece a destra perché
maggiore e così via.
Di seguito mostriamo l’albero che si viene così a generare.
COSTRUZIONE DI UN BST DI INTERI
Supponiamo che i numeri vengano introdotti nel seguente ordine :
50 40 60 30 44 55 70 20 35 42 46 80 41 43 45 48 90
L’albero risultante sarà:
50
60
40
30
20
44
35
41
55
42
70
46
43
45
80
48
90
COSTRUZIONE DI UN BST
L’algoritmo di costruzione di un BST è il seguente.
Mediante una funzione ricorsiva (Insert) si esplora l’albero
a destra o a sinistra al fine di individuare dove legare il
nuovo nodo.
As
A
key1
Ad
Inizialmente A=NULL, quindi, appena si entra, si richiama
la funzione (Insert) che crea un nodo di chiave key1 e As
e Ad (puntatori ai sottoalberi sinistro e destro) uguali a
NULL.
COSTRUZIONE DI UN BST
Successivamente per ogni chiave introdotta, a seconda
se è maggiore o minore della chiave del sottoalbero che
si considera, si richiama Insert a destra o a sinistra al fine
di trovare il luogo dove inserire la nuova chiave.
Questo luogo si ottiene esplorando l'albero fino a quando
o il sottoalbero destro o quello sinistro non è NULL.
A questo punto ricadiamo nel caso base e realmente si
inserisce il nodo.
Nel caso la chiave fosse già presente questo fatto viene
segnalato e la chiave non viene introdotta nell’albero.
Di seguito il codice che permette di costruire un albero leggendo
le chiavi da un file .txt
void InsertSort( Tnodo &A,int m, bool &inserito) {
if(A==NULL) {
A=new RTnodo;
A->key = m;
A->left=NULL;
A->right=NULL;
inserito=true; }
else if(A->key<m) InsertSort(A->right,m,inserito);
else if(A->key>m) InsertSort(A->left,m,inserito);
else inserito=false;
void CreaAlbero(Tnodo& A) {
int Num;
cout<<"\n CREA ALBERO \n"<<endl;
A=NULL;
string NomeIn, NomeOut;
ifstream filista;
ofstream outlista;
NomeIn="TREE01.txt";
filista.open(NomeIn.c_str());
}
if (!filista)
{ cerr<<"Non si puo' aprire il file"<<endl;
system("pause"); }
filista>>Num;
while (!filista.eof()) {
bool temp=false;
InsertSort( A, Num, temp);
if (temp==false) cout<<"\t\tNumero preesistente ="<<Num<<endl;
else cout<<" Inserito numero= "<<Num<<endl;
filista>>Num;;
struct RTnodo {
}
int key;
}
RTnodo *left, *right;
};
Allegato: Alb generale 1
typedef RTnodo* Tnodo;
ESERCIZIO
Eliminare un BST senza lasciare spazzatura.
Soluzione
Attraversa l’albero con un algoritmo (post-order) e cancella ogni nodo incontrato.
E’ utilizzato il post-order perché la root è sempre l’ultima ad essere deallocata dopo aver
deallocato i nodi figli, e quindi nessun link è eliminato prima del dovuto.
void KillTree(Tnodo &Tree){
if (Tree!=NULL) {
KillTree(Tree->left);
KillTree(Tree->right);
delete Tree;
Tree=NULL;
}
}
Visitare tutti i nodi di un BST di interi, attraversando:
• il sotto albero sinistro;
• il sotto albero destro;
• la radice;
post-order
Maria
Giulio
Dora
Anna
Sergio
Guido
Riccardo
Toni
12
Roberto
MOSTRA IL CONTENUTO DI UN BST
writeTree(A,1);
…………………………
void writeTree(Tnodo A, int i) {
if (A!=NULL)
{
writeTree (A->right,i+1);
for (int j=1;j<=i;j++)
{
cout<<" ";
}
cout<<A->key;
cout<<endl;
writeTree(A->left,i+1);
}
}
in-order
Visitare tutti i nodi di un BST di interi, attraversando:
• il sotto albero destro;
• la radice;
• il sotto albero sinistro;
RICERCA DI UN DATO SU UN BST
50
60
40
30
20
44
35
65
42
41
46
43
bool TrovaDato(int d, Tnodo A) {
if (A==NULL)
return false;
else if (d==A->key)
return true;
else
return (TrovaDato(d,A->left) || TrovaDato(d,A->right));
}
Visitare tutti i nodi di un BST di interi, attraversando:
• la radice;
• il sotto albero sinistro;
• il sotto albero destro;
70
45
80
48
90
Tnodo TrovaDatoT(int d, Tnodo A) {
if (A==NULL)
return NULL;
else if (d==A->key)
return A;
else
if ( A->key > d)
return TrovaDatoT(d,A->left);
else
return TrovaDatoT(d,A->right);
}
pre-order
int contafoglie(Tnodo A)
{// CONTA LE FOGLIE DELL’ALBERO
if (A==NULL)
return 0;
else
{
if ((A->left==NULL)&&(A->right==NULL))
return contafoglie(A->left)+contafoglie(A->right)+1;
else
return contafoglie(A->left)+contafoglie(A->right);
}
}
alberiGenerale0_1
PROVE INTERCORSO 2010-2011
A1
1 – Scrivere una funzione ricorsiva che data una matrice quadrata A NxN
calcoli la somma di tutti gli elementi che sono collocati al di sotto delle
due diagonali come mostrato in figura.
-1
3
-1
-6
2
12
-12
4
1
1
2
3
-1
-6
2
12
0
-10
3
-5
4
-5
3
4
-5
4
-5
-7
-5
4
-5
6
3
-1
-6
3
-1
6
-2
1
0
2
1
1
5
25
-3
-2
2
1
4
-2
7
6
-29
8
PRECONDIZIONI
i=N/2+1;
j=N/2-1;
if ((N%2)==1) j=N/2;
-2
7
6
5 int ricA1(int A[][Nmax], int i, int j, int N)
-3 {
if (i>N-1)
2
return 0;
else
1
if (j<=i-1)
-47
return ricA1(A,i,j+1,N)+A[i][j];
else
return ricA1(A,i+1,N-i-1,N);
Risposta = (4+6+3-5-2-3+12+4+6+1-2+8)=32
}
A2
1 – Data la successione
a1 =3, a2=1, a3=-1
an = an-1 -3* an-2 + an-3
Scrivere una procedura ricorsiva che riempia una matrice NxN con i soli
valori della successione maggiori di 0.
Esempio N=3
PRECONDIZIONI
Successione= 3, 1, -1,3,5,.-5,-17, 3, 49 ,23 ,-121 ,-141, 245, 547 i=0, j=2;
matrice[0][0]=a1;
matrice[0][1]=a2;
void calcolaMatrice(int matrice[Nmax][Nmax],int i,int j,int N,int a1,int a2,int a3)
{ int an;
if (i>N-1)
return;
else
Matrice
if (j>N-1)
3
1
3
calcolaMatrice(matrice,i+1,0,N,a1,a2,a3);
else
5
3
49
{ an=a3-3*a2+a1;
23 245 547
if (an>0)
{ matrice[i][j]=an;
calcolaMatrice(matrice,i,j+1,N,a2,a3,an); }
else
calcolaMatrice(matrice,i,j,N,a2,a3,an);}
}
A3
1- Date le successioni:
b1=5, b2= -1, b3=3
a1 =3, a2=1, a3=-1
bn=-3* bn-1- bn-2+ bn-3
an=an-1-3* an-2+ an-3
e un vettore V[N], con N pari, scrivere una funzione ricorsiva che riempia il
vettore V nella prima metà con gli elementi di an e la seconda metà con gli
elementi di bn.
Esempio
PRECONDIZIONI
N=14
a1=3, a2=1, a3=-1;
Successione an= 3, 1, -1, -1,-9, -3, 23 …..
b1=5, b2=-1, b3=3;
Successione bn= 5, -1, 3,-11, 27, -65, 157 ,……
vet[0]=a1;vet[1]=a2;vet[2]=a3;
Vettore [3, 1, -1, -1,-9, -3, 23, 5, -1, 3,-11, 27, -65, 157] N=14;
i=3;
j=N/2+3;
void vettore(int vet[], int a1,int a2,int a3,int b1,int b2,int b3,int i,int j,int N)
{ int an=0,bn=0;
if(i<(N/2)
{ an=a1-3*a2+a3;
bn=-3*b1-b2+b3;
vet[i]=an;
vet[j]=bn;
vettore(vet,an,a1,a2,bn,b1,b2,i+1,j+1,N);
}
return;
}
A4
1 – Scrivere una funzione ricorsiva che data una matrice quadrata A NxN
calcoli la somma di tutti gli elementi che sono collocati a sinistra delle due
diagonali come mostrato in figura.
-1
1
0
-5
3
0
2
-2
3
1
-10
4
-1
2
1
7
-1
2
3
-5
-6
1
4
6
-6
3
-5
-7
3
1
-2
5
2
-1
4
-5
-1
5
7
-3
12
-6
-5
4
6
25
6
2
-12
2
3
-5
-2
-3
-29
1
4
12
4
6
1
-2
8
-47
Risposta = (3-1-6+2+12-12+2+3-1-6-5+4)=-5
PRECONDIZIONI
i=1;
j=0;
N=N-1;
int ricA1(int A[][Nmax], int i, int j, int N)
{
if (j>N/2-1)
return 0;
else
if (i>N-1-j)
return ricA1(A,j+2,j+1,N);
else
return ricA1(A,i+1,j,N)+A[i][j];
}