Algoritmi su Alberi
Questo
esercizio implementa un pacchetto di procedure tipiche della gestione
dell’albero binario di ricerca.
1) Carica i
dati dal file ‘dati.txt’;
2) Costruzione
di un albero di ricerca bilanciato;
3) Ricerca di
una chiave nell’albero;
4) Lettura
dell’albero in modo simmetrico;
5) Lettura
dell’albero in modo anticipato;
6) Lettura
dell’albero in modo differito;
7) Verifica
della proprietà dell’albero binario di ricerca;
Verifica
della proprietà di albero completo;
9) Verifica
della proprietà di albero bilanciato;
10)
Calcolo del grado di sbilanciamento dell’albero.
L’esecuzione
del programma porterà alla visualizzazione di un menù di scelta che consente
l’esecuzione delle suddette procedure inserendo il numero associato (tra 1 e
10) ad ognuna di esse. Il programma terminerà inserendo il numero 11 associato
all’opzione di uscita mentre inserendo un qualsiasi altro numero sarà
visualizzato un messaggio di errore e sarà possibile effettuare una nuova
scelta.
Carica i dati dal file ‘dati.txt’
|
void carica_dati(char { FILE *dati; int i=-1;
dati = fopen(nomefile,”r”);
if (dati != NULL) { while *tot=i;
} else { printf(”ERRORE: } } |
Questa prima
procedura si occupa della lettura di un file contenente interi ordinati memorizzandoli in
un vettore che poi sarà restituito in output. Per fare ciò riceve in input il
nome del file da cui leggere i dati e restituisce in output il vettore
contenente i dati letti e un intero che indica quanti dati sono stati
registrati nel vettore.
Costruzione di un albero di
ricerca bilanciato
|
tipo_ABR { int indice;
if (low <= high) { indice = albero = albero = albero = costruisci_albero(albero,vettore,indice+1,high); } return albero; } |
Preso in input un
vettore ordinato e gli indicatori di inizio e fine del vettore, dà in output un
albero di ricerca bilanciato. Utilizzando la funzione ABR_inserisci_elemento()
della libreria ADTabr.h sarà inserito l’elemento mediano del vettore
nell’albero e tale procedimento sarà effettuato ricorsivamente sul sottoalbero
sinistro e destro rispettivamente per la parte sinistra e destra del vettore.
Ricerca di una chiave
nell’albero
|
void cerca_chiave(tipo_ABR { tipo_ABR nodo; tipo_chiave key;
printf(”Inserisci la chiave da cercare: “); scanf(”%d”,&key);
nodo =
if (nodo == NULL) { printf(”La chiave NON e’ stata } else { printf(”La chiave e’ stata } } |
Questa procedura
preso in input l’albero, richiede all’utente la chiave da ricercare. Per
effettuare tale compito si avvale della funzione di libreria ABR_cerca_chiave(
) e avverte l’utente dell’esito di tale ricerca.
Lettura dell’albero in modo
simmetrico
|
void { if (!ABR_albero_vuoto(albero)) { leggi_simmetrico(ABR_albero_sinistro(albero)); printf(”%d leggi_simmetrico(ABR_albero_destro(albero)); } } |
Questa
procedura legge l’albero servendosi delle funzioni della libreria:
ABR_albero_vuoto()
che ci dice se l’albero è vuoto oppure no;
ABR_albero_sinistro() che ci restituisce il sottoalbero sinistro;
ABR_albero_destro() che ci
restituisce il sottoalbero destro;
ABR_mostra_key() che ci restituisce la chiave dell’albero.
Lettura dell’albero in modo
anticipato
|
void { if (!ABR_albero_vuoto(albero)) { printf(”%d “,ABR_mostra_key(albero)); leggi_anticipato(ABR_albero_sinistro(albero)); leggi_anticipato(ABR_albero_destro(albero)); } } |
Questa
procedura legge l’albero servendosi delle funzioni della libreria:
ABR_albero_vuoto()
che ci dice se l’albero è vuoto oppure no;
ABR_albero_sinistro() che ci restituisce il sottoalbero sinistro;
ABR_albero_destro() che ci
restituisce il sottoalbero destro;
ABR_mostra_key() che ci restituisce la chiave dell’albero.
Lettura dell’albero in modo
differito
|
void { if (!ABR_albero_vuoto(albero)) { leggi_differito(ABR_albero_sinistro(albero)); leggi_differito(ABR_albero_destro(albero)); printf(”%d } } |
Questa
procedura legge l’albero servendosi delle funzioni della libreria:
ABR_albero_vuoto()
che ci dice se l’albero è vuoto oppure no;
ABR_albero_sinistro() che ci restituisce il sottoalbero sinistro;
ABR_albero_destro() che ci
restituisce il sottoalbero destro;
ABR_mostra_key() che ci restituisce la chiave dell’albero.
Verifica della proprietà dell’albero binario di ricerca
|
int { if (!ABR_albero_vuoto(albero)) { valore_precedente = if { valore_precedente = return 1 && } return 0; } else { return 1; } }
void verifica_albero_binario_ricerca(tipo_ABR { if (verifica_abr_ric(albero,INT_MIN)) { printf(”L’albero e’ un albero binario di } else { printf(”L’albero NON e’ un albero binario } } |
Queste due procedure
ci permettono di verificare che l’albero che diamo in input, è oppure no un
albero binario di ricerca.
Verifica della proprietà di
albero completo
|
int { int livello_sx,livello_dx;
if (!ABR_albero_vuoto(albero)) { livello_sx = livello_dx = if (livello_sx == livello_dx) { return livello_sx; } return -2; } else { return } }
void { if (verifica_completo_ric(albero,0) > -2) { printf(”L’albero e’ un albero } else { printf(”L’albero NON e’ un albero } } |
Queste due procedure
ci permettono di verificare che l’albero che diamo in input, è oppure no un
albero completo.
Verifica della proprietà di
albero bilanciato
|
int { int livello_sx,livello_dx;
if (!ABR_albero_vuoto(albero)) { livello_sx = livello_dx = if (abs(livello_sx – livello_dx) < 2) { return livello_sx; } return -2; } else { return } }
void { if (verifica_bilanciato_ric(albero,0) > -2) { printf(”L’albero e’ un albero } else { } } |
Queste due procedure
ci permettono di verificare che l’albero che diamo in input, è oppure no un
albero bilanciato.
Calcolo del grado di
sbilanciamento dell’albero
|
void calcola_dati_sbilanciamento(tipo_ABR { if (!ABR_albero_vuoto(albero)) { *nodi = *nodi + 1;
calcola_dati_sbilanciamento(ABR_albero_destro(albero),min,max,nodi,livello+1); } else { if(livello-1 { *min = livello-1; }
if(livello-1 > *max) { *max = livello-1; } } }
void { int livello_min = INT_MAX; int livello_max = INT_MIN; int numero_nodi = 0; float sbilanciamento;
if (numero_nodi > 0) { sbilanciamento = (float) (livello_max - } else { sbilanciamento = 0; }
printf(”Il grado di sbilanciamento e’ } |
Queste due procedure
ci permettono di ottenere un indice che esprime il grado di sbilanciamento
dell’albero. Quest’ultimo viene calcolato nel seguente modo:
Gradi_Sbilanciamento = (altezza_massima – altezza_minima) / numero_nodi
Per calcolare i dati necessari al calcolo del grado di sbilanciamento, ci
serviamo della procedura calcola_dati_sbilanciamento().
UTILIZZAZIONE ED ESEMPIO
D’USO
Compilando
ed eseguendo gestalbero.c abbiamo :
CODICE SORGENTE
GestAlbero.c
#define ELEMENTO_FITTIZIO 0
/******************** FUNZIONI DI ADTabr.h *********************/
#include “ADTabr.h”
/*PROPRIETA’*/
int ABR_albero_vuoto(tipo_ABR);
/*COSTRUTTORI*/
tipo_ABR ABR_crea_albero();
tipo_ABR
ABR_inserisci_elemento(tipo_ABR,tipo_chiave,tipo_elemento);
/*DISTRUTTORI*/
tipo_ABR
ABR_cancella_albero(tipo_ABR);
tipo_ABR
ABR_cancella_elemento(tipo_ABR,tipo_chiave);
/*SELETTORI*/
tipo_ABR ABR_albero_sinistro(tipo_ABR);
tipo_ABR
ABR_albero_destro(tipo_ABR);
tipo_ABR
*ABR_indirizzo_albero_sinistro(tipo_ABR);
tipo_ABR
*ABR_indirizzo_albero_destro(tipo_ABR);
/*GESTIONE DEI DATI*/
tipo_chiave
ABR_mostra_key(tipo_ABR);
tipo_elemento ABR_mostra_elemento(tipo_ABR);
/*OPERAZIONI DI RICERCA*/
tipo_ABR
ABR_minimo(tipo_ABR);
tipo_ABR
ABR_successore(tipo_ABR,tipo_chiave);
tipo_ABR
ABR_cerca_chiave(tipo_ABR,tipo_chiave);
/********************* CODICE SORGENTE **********************/
void carica_dati(char
*nomefile,int *vettore,int *tot)
{
FILE *dati;
int i=-1;
dati = fopen(nomefile,”r”);
if (dati != NULL)
{
while
(fscanf(dati,”%d”,&vettore[++i]) != EOF);
*tot=i;
fclose(dati);
}
else
{
printf(”ERRORE: impossibile
aprire il file %s\n”,nomefile);
}
}
tipo_ABR
costruisci_albero(tipo_ABR albero,int *vettore,int low,int high)
{
int indice;
if (low <= high)
{
indice =
((high-low)/2)+low;
albero =
ABR_inserisci_elemento(albero,vettore[indice],ELEMENTO_FITTIZIO);
albero =
costruisci_albero(albero,vettore,low,indice-1);
albero =
costruisci_albero(albero,vettore,indice+1,high);
}
return albero;
}
void cerca_chiave(tipo_ABR
albero)
{
tipo_ABR nodo;
tipo_chiave key;
printf(”Inserisci la chiave da cercare: “);
scanf(”%d”,&key);
nodo =
ABR_cerca_chiave(albero,key);
if (nodo == NULL)
{
printf(”La chiave NON e’ stata
trovata.\n\n”);
}
else
{
printf(”La chiave e’ stata
trovata.\n\n”);
}
}
void leggi_simmetrico(tipo_ABR
albero)
{
if (!ABR_albero_vuoto(albero))
{
leggi_simmetrico(ABR_albero_sinistro(albero));
printf(”%d “,ABR_mostra_key(albero));
leggi_simmetrico(ABR_albero_destro(albero));
}
}
void
leggi_anticipato(tipo_ABR albero)
{
if (!ABR_albero_vuoto(albero))
{
printf(”%d “,ABR_mostra_key(albero));
leggi_anticipato(ABR_albero_sinistro(albero));
leggi_anticipato(ABR_albero_destro(albero));
}
}
void leggi_differito(tipo_ABR
albero)
{
if (!ABR_albero_vuoto(albero))
{
leggi_differito(ABR_albero_sinistro(albero));
leggi_differito(ABR_albero_destro(albero));
printf(”%d “,ABR_mostra_key(albero));
}
}
int verifica_abr_ric(tipo_ABR
albero,int valore_precedente)
{
if (!ABR_albero_vuoto(albero))
{
valore_precedente =
verifica_abr_ric(ABR_albero_sinistro(albero),valore_precedente);
if (valore_precedente <
ABR_mostra_key(albero))
{
valore_precedente =
ABR_mostra_key(albero);
return 1 &&
(verifica_abr_ric(ABR_albero_destro(albero),valore_precedente));
}
return 0;
}
else
{
return 1;
}
}
void
verifica_albero_binario_ricerca(tipo_ABR albero)
{
if (verifica_abr_ric(albero,INT_MIN))
{
printf(”L’albero e’ un albero binario di
ricerca.\n\n”);
}
else
{
printf(”L’albero NON e’ un albero binario di
ricerca.\n\n”);
}
}
int
verifica_completo_ric(tipo_ABR albero,int livello)
{
int livello_sx,livello_dx;
if (!ABR_albero_vuoto(albero))
{
livello_sx =
verifica_completo_ric(ABR_albero_sinistro(albero),livello+1);
livello_dx =
verifica_completo_ric(ABR_albero_destro(albero),livello+1);
if (livello_sx == livello_dx)
{
return livello_sx;
}
return -2;
}
else
{
return
livello-1;
}
}
void
verifica_completo(tipo_ABR albero)
{
if (verifica_completo_ric(albero,0) > -2)
{
printf(”L’albero e’ un albero
completo.\n\n”);
}
else
{
printf(”L’albero NON e’ un albero
completo.\n\n”);
}
}
int
verifica_bilanciato_ric(tipo_ABR albero,int livello)
{
int livello_sx,livello_dx;
if (!ABR_albero_vuoto(albero))
{
livello_sx =
verifica_bilanciato_ric(ABR_albero_sinistro(albero),livello+1);
livello_dx =
verifica_bilanciato_ric(ABR_albero_destro(albero),livello+1);
if (abs(livello_sx – livello_dx) < 2)
{
return livello_sx;
}
return -2;
}
else
{
return
livello-1;
}
}
void
verifica_bilanciato(tipo_ABR albero)
{
if (verifica_bilanciato_ric(albero,0) > -2)
{
printf(”L’albero e’ un albero
bilanciato.\n\n”);
}
else
{
printf(”L’albero NON e’ un albero
bilanciato.\n\n”);
}
}
void
calcola_dati_sbilanciamento(tipo_ABR albero,int *min,int *max,int *nodi,int
livello)
{
if (!ABR_albero_vuoto(albero))
{
*nodi = *nodi + 1;
calcola_dati_sbilanciamento(ABR_albero_sinistro(albero),min,max,nodi,livello+1);
calcola_dati_sbilanciamento(ABR_albero_destro(albero),min,max,nodi,livello+1);
}
else
{
if(livello-1
< *min)
{
*min = livello-1;
}
if(livello-1 > *max)
{
*max = livello-1;
}
}
}
void
calcola_sbilanciamento(tipo_ABR albero)
{
int livello_min = INT_MAX;
int livello_max = INT_MIN;
int numero_nodi = 0;
float sbilanciamento;
calcola_dati_sbilanciamento(albero,&livello_min,&livello_max,&numero_nodi,0);
if (numero_nodi > 0)
{
sbilanciamento = (float) (livello_max -
livello_min)/numero_nodi;
}
else
{
sbilanciamento = 0;
}
printf(”Il grado di sbilanciamento e’
%f\n\n”,sbilanciamento);
}
main()
{
int scelta,tot=0;
int vettore[MAX_VETTORE];
tipo_ABR albero;
albero = ABR_crea_albero();
do {
printf(”*****************************************************\n”);
printf(”* ESERCIZIO DI ALGORITMI E STRUTTURE
DATI *\n”);
printf(”* Divisato Antonio 50/358
*\n”);
printf(”* Ferrara Francesco
Saverio 566/811
*\n”);
printf(”*
Liguori Vincenzo 408/301
*\n”);
printf(”*****************************************************\n”);
printf(”\nMENU DI SCELTA:\n”);
printf(”\t 1) Carica i dati dal file
‘dati.txt’\n”);
printf(”\t 2) Costruisci l’albero
bilanciato\n”);
printf(”\t 3) Cerca una chiave
nell’albero\n”);
printf(”\t 4) Leggi l’albero in modo
simmetrico\n”);
printf(”\t 5) Leggi l’albero in modo
anticipato\n”);
printf(”\t 6) Leggi l’albero in modo
differito\n”);
printf(”\t 7) Verifica che l’albero e’ un
albero binario di ricerca\n”);
printf(”\t Verifica che l’albero e’
completo\n”);
printf(”\t 9) Verifica che l’albero e’
bilanciato\n”);
printf(”\t10) Calcola il grado di
sbilanciamento dell’albero\n”);
printf(”\t11) USCITA\n\n”);
printf(”Inserisci la scelta: “);
scanf(”%d”,&scelta);
switch(scelta) {
case 1:
carica_dati(”dati.txt”,vettore,&tot);
printf(”Il vettore
e’ stato caricato!\n”);
getchar();
getchar();
break;
case 2:
albero =
costruisci_albero(albero,vettore,0,tot-1);
printf(”L’albero e’
stato creato!\n”);
getchar();
getchar();
break;
case 3:
cerca_chiave(albero);
printf(”La
procedura e’ terminata!\n”);
getchar();
getchar();
break;
case 4:
leggi_simmetrico(albero);
printf(”\nL’albero
e’ stato letto!\n”);
getchar();
getchar();
break;
case 5:
leggi_anticipato(albero);
printf(”\nL’albero
e’ stato letto!\n”);
getchar();
getchar();
break;
case 6:
leggi_differito(albero);
printf(”\nL’albero
e’ stato letto!\n”);
getchar();
getchar();
break;
case 7:
verifica_albero_binario_ricerca(albero);
printf(”La
procedura e’ terminata!\n”);
getchar();
getchar();
break;
case 8:
verifica_completo(albero);
printf(”La
procedura e’ terminata!\n”);
getchar();
getchar();
break;
case 9:
verifica_bilanciato(albero);
printf(”La
procedura e’ terminata!\n”);
getchar();
getchar();
break;
case 10:
calcola_sbilanciamento(albero);
printf(”La
procedura e’ terminata!\n”);
getchar();
getchar();
break;
case 11:
break;
default:
printf(”\n\nERRORE DI
SCELTA!!!\nInserire un numero compreso tra 1 e 11.\n”);
getchar();
getchar();
break;
}
} while (scelta != 11);
albero = ABR_cancella_albero(albero);
}
ADTabr.h
/******************************************************************************
*
ALBERO BINARIO HEADER FILE
*
* funzioni per manipolare il dato astratto albero
binario di ricerca *
******************************************************************************/
/* #include <stdio.h>
*/
/*********************** DEFINIZIONE STRUTTURA DATI ***********************/
#define CHIAVE_NULLA 0;
#define ELEMENTO_NULLO 0;
typedef int tipo_elemento;
/*qui puoi modificare il tipo dell’elemento*/
typedef int tipo_chiave; /*qui puoi modificare il tipo
della chiave*/
typedef struct tipo_nodo
*tipo_ABR;
typedef struct tipo_nodo{
tipo_elemento *elemento;
tipo_chiave key;
tipo_ABR sx;
tipo_ABR dx;
} tipo_nodo;
/******************** FUNZIONI DI GESTIONE
DELL’ABR
**********************/
/*PROPRIETA’*/
int
ABR_albero_vuoto(tipo_ABR);
/*COSTRUTTORI*/
tipo_ABR ABR_crea_albero();
tipo_ABR
ABR_inserisci_elemento(tipo_ABR,tipo_chiave,tipo_elemento);
/*DISTRUTTORI*/
tipo_ABR
ABR_cancella_albero(tipo_ABR);
tipo_ABR
ABR_cancella_elemento(tipo_ABR,tipo_chiave);
/*SELETTORI*/
tipo_ABR
ABR_albero_sinistro(tipo_ABR);
tipo_ABR
ABR_albero_destro(tipo_ABR);
tipo_ABR *ABR_indirizzo_albero_sinistro(tipo_ABR);
tipo_ABR
*ABR_indirizzo_albero_destro(tipo_ABR);
/*GESTIONE DEI DATI*/
tipo_chiave
ABR_mostra_key(tipo_ABR);
tipo_elemento
ABR_mostra_elemento(tipo_ABR);
/*OPERAZIONI DI RICERCA*/
tipo_ABR
ABR_minimo(tipo_ABR);
tipo_ABR ABR_successore(tipo_ABR,tipo_chiave);
tipo_ABR
ABR_cerca_chiave(tipo_ABR,tipo_chiave);
/********************* IMPLEMENTAZIONE DELLE FUNZIONI **********************/
int ABR_albero_vuoto(tipo_ABR
tree)
{
return tree == NULL;
}
tipo_ABR ABR_crea_albero()
{
return NULL;
}
tipo_ABR
ABR_cancella_albero(tipo_ABR tree)
{
if (tree != NULL)
{
tree->sx = ABR_cancella_albero(tree->sx);
tree->dx = ABR_cancella_albero(tree->dx);
if (tree->elemento !=
NULL)
{
free(tree->elemento);
}
free(tree);
}
return NULL;
}
tipo_ABR
ABR_cancella_nodo(tipo_ABR tree)
{
if (tree != NULL)
{
if
(tree->elemento != NULL)
{
free(tree->elemento);
}
free(tree);
}
return NULL;
}
tipo_ABR
ABR_crea_nodo(tipo_chiave key,tipo_elemento elemento)
{
tipo_ABR nodo;
nodo = (tipo_ABR) malloc(sizeof(tipo_nodo));
nodo->sx = NULL;
nodo->dx = NULL;
nodo->elemento = (tipo_elemento *)
malloc(sizeof(tipo_elemento));
*(nodo->elemento) = elemento;
nodo->key = key;
return nodo;
}
tipo_chiave
ABR_mostra_key(tipo_ABR tree)
{
if (ABR_albero_vuoto(tree))
{
return CHIAVE_NULLA;
}
else
{
return
tree->key;
}
}
tipo_elemento
ABR_mostra_elemento(tipo_ABR tree)
{
if (ABR_albero_vuoto(tree))
{
return ELEMENTO_NULLO;
}
else
{
return
*(tree->elemento);
}
}
tipo_ABR
ABR_albero_sinistro(tipo_ABR tree)
{
return tree->sx;
}
tipo_ABR
ABR_albero_destro(tipo_ABR tree)
{
return tree->dx;
}
tipo_ABR
*ABR_indirizzo_albero_sinistro(tipo_ABR tree)
{
return &(tree->sx);
}
tipo_ABR
*ABR_indirizzo_albero_destro(tipo_ABR tree)
{
return &(tree->dx);
}
tipo_ABR
ABR_inserisci_elemento(tipo_ABR tree,tipo_chiave key,tipo_elemento elemento)
{
if (tree != NULL)
{
if (key <
tree->key)
{
tree->sx
= ABR_inserisci_elemento(tree->sx,key,elemento);
}
else
{
tree->dx = ABR_inserisci_elemento(tree->dx,key,elemento);
}
}
else
{
tree =
ABR_crea_nodo(key,elemento);
}
return tree;
}
tipo_ABR ABR_minimo(tipo_ABR
tree)
{
if (tree != NULL)
{
if
(tree->sx == NULL)
{
return tree;
}
else
{
return ABR_minimo(tree->sx);
}
}
else
{
return NULL;
}
}
tipo_ABR
ABR_successore_ricorsivo(tipo_chiave key,tipo_ABR tree,tipo_ABR padre_tree)
{
if (tree != NULL)
{
if (key >
tree->key)
{
return ABR_successore_ricorsivo(key,tree->dx,padre_tree);
}
else
{
if
(key < tree->key)
{
return
ABR_successore_ricorsivo(key,tree->sx,tree);
}
else
{
if (tree->dx != NULL)
{
return
ABR_minimo(tree->dx);
}
else
{
return
padre_tree;
}
}
}
}
else
{
return padre_tree;
}
}
tipo_ABR ABR_successore(tipo_ABR
tree, tipo_chiave key)
{
return
ABR_successore_ricorsivo(key,tree,NULL);
}
tipo_ABR
ABR_stacca_succ(tipo_ABR tree, tipo_ABR padre)
{
if (tree != NULL)
{
if
(tree->sx != NULL)
{
return ABR_stacca_succ(tree->sx,tree);
}
else
{
if
(tree == padre->sx)
{
padre->sx =
tree->dx;
}
else
{
padre->dx =
tree->dx;
}
tree->dx = NULL;
}
}
return tree;
}
tipo_ABR
ABR_cancella_elemento(tipo_ABR tree,tipo_chiave key)
{
tipo_ABR nodo;
if (tree != NULL)
{
if (key <
tree->key)
{
tree->sx =
ABR_cancella_elemento(tree->sx,key);
}
else
{
if
(key > tree->key)
{
tree->dx =
ABR_cancella_elemento(tree->dx,key);
}
else /*trovata la key*/
{
if ((tree->sx ==
NULL) || (tree->dx == NULL))
{
nodo = tree;
if
(nodo->sx == NULL)
{
tree = nodo->dx;
}
else
{
tree = nodo->sx;
}
}
else
{
nodo =
ABR_stacca_succ(tree->dx,tree);
tree->elemento = nodo->elemento;
nodo->elemento = NULL;
tree->key = nodo->key;
}
nodo =
ABR_cancella_nodo(nodo);
}
}
return tree;
}
}
tipo_ABR
ABR_cerca_chiave(tipo_ABR tree,tipo_chiave key)
{
if (tree != NULL)
{
if (key <
tree->key)
{
return ABR_cerca_chiave(tree->sx,key);
}
else
{
if
(key > tree->key)
{
return
ABR_cerca_chiave(tree->dx,key);
}
else
{
return tree;
}
}
}
else
{
return NULL;
}
}