Alberi binari di ricerca: versione ricorsiva
 |
A cura di Di Fusco Francesco
2009-04-28 |
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
Dichiarazione del tipo albero_binario
typedef struct albero
{
char info[80];
struct albero *sinistra;
struct albero *destra;
} albero_binario;
Prototipi delle funzioni di inserimento e visita in ordine
albero_binario *inserisci(albero_binario *Root, char *elemento);
void visita_inordine(albero_binario *Root);
int main()
{
int i,n;
char informazione[80];
albero_binario *T=NULL;
printf("Inserisci N");
scanf("%d",&n);
printf("n=%d",n);
Inserimento dei nodi dell'albero
for (i=0;i < n;i++)
{
printf("\n Inserisci elemento");scanf("%s",&informazione);
T=inserisci(T,informazione);
}
printf("Visita dell'albero binario di ricerca\n");
visita_inordine(T);
return 0;
}
La funzione inserisci inserisce un elemento nell'albero binario di ricerca e restituisce il puntatore alla radice dell'albero
albero_binario *inserisci(albero_binario *Root, char *elemento)
{
Se la radice dell'albero è NULL, cioè l'albero è vuoto, viene creato un nuovo nodo
if (Root==NULL)
{
Root=malloc(sizeof(albero_binario));
Controlliamo se la malloc ha restituito un puntatore valido
if (Root!=NULL)
{
se possiamo creare il nodo, copiamo l'elemento nel campo info del nodo appena creato
strcpy(Root->info,elemento);
poiché il nuovo nodo non ha ancora sottoalberi, sia a sinistra che a destra, poniamo a NULL i puntatori sinistra e destra
Root->sinistra=NULL;
Root->destra=NULL;
}
else return NULL;
}
se invece l'albero non è vuoto
else
{
controlliamo se dobbiamo inserire il nuovo elemento a sinistra o a destra della radice. Ricordiamo che tale procedimento è ricorsivo.
Se l'elemento da inserire precede l'elemento che si trova sulla radice,
if (strcmp(elemento,Root->info)<0)
allora il nuovo nodo creato diventa un sottoramo a sinistra della radice corrente. Ciò viene effettuato collegando il puntatore sinistra della radice all'indirizzo del nodo da creare creato. L'indirizzo appena creato viene fornito dalla funzione inserisci
Root->sinistra=inserisci(Root->sinistra, elemento);
else
Root->destra=inserisci(Root->destra, elemento);
}
return Root;
}
// Procedura di vita dell'albero in modo "inorder"
// La visita viene effettuata nel modo seguente:
// Sottoalbero sinistro -- Radice -- Sottoalbero destro
void visita_inordine(albero_binario *Root)
{
if (Root!=NULL)
{
visita_inordine(Root->sinistra); // Visita sottoalbero sinistra
printf("%s\n",Root->info); // Visita Radice
visita_inordine(Root->destra); // Visita sottoalbero destra
}
}
|
|
|
| Documenti allegati: |
| alberi_binari_ricerca.pdf |
| alberi_binari_ricerca.pdf |
| alberi_binari_ricerca.c |
