E’ da un pò di tempo che sto cercando di dedicarmi all’implementazione in C di programmi sempre meno banali.
Purtroppo non sono un programmatore provetto, e forse non lo sarò mai. Sto tuttavia cercando di colmare il gap che mi separa dal perfetto ingegnere.. anche se a rilento.
Quello che vi sto mostrando è il codice commentato di un albero binario con alcune funzioni interessanti, che aggiornerò man mano in base a quello che mi passerà per il cervello.
Oggetto: Albero Binario
Implementazione in Linguaggio: C (ANSI)
Funzioni: Creazione dell’albero, collezione di informazioni, ricerca e cancellazione.
typedef struct node *Nodepointer;
typedef struct node
{
int valore;
Nodepointer son_sx;
Nodepointer son_dx;
Nodepointer father;
int markup;
} Nodo;
Cominciamo dalle strutture, per poi passare alle funzioni, al main e a tutto il resto (ad esempio gli include).
typedef struct node *Nodepointer; indica che Nodepointer da ora in poi sarà la parola chiave utilizzabile per identificare un puntatore a una struttura chiamata node.
typedef struct node { … } Nodo è invece la definizione di Nodo come parola chiave per la creazione di una struct node.
La struct node altro non è che il singolo nodo dell’albero, vediamo come è composto:
- int valore;
questo intero è il contenuto del nodo, l’informazione che il nodo trasporta.
- Nodepointer son_sx;
Puntatore al nodo figlio sinistro
- Nodepointer son_dx;
Puntatore al nodo figlio destro
- Nodepointer father;
Puntatore al nodo padre
- int markup;
intero di marcatura. Serve per contraddistinguere un nodo visitato da uno non visitato.
Cominciamo dalla prima funzione:
Nodepointer creaNodo(int value)
{
Nodepointer puntatore = malloc(sizeof(Nodo));
puntatore->valore = value;
puntatore->son_sx = NULL;
puntatore->son_dx = NULL;
puntatore->father = NULL;
puntatore->markup = 0;
return puntatore;
}
Questa funzione ha come input un intero (il contenuto del nodo) e restituisce un puntatore a nodo.
Per prima cosa crea la memoria necessaria ad un nodo tramite la funzione malloc, quindi inizializza a NULL tutti i puntatori (rendendo di fatto il nodo isolato da tutto, ma sta a noi del resto collegarlo a quello che vogliamo) e pone a 0 il bit di markup, dato che il nodo non è stato visitato. Quindi, restituisce il puntatore al nodo creato.
Nodepointer settings(Nodepointer nodo, Nodepointer sx, Nodepointer dx, Nodepointer dad)
{
nodo->son_sx = sx;
nodo->son_dx = dx;
nodo->father = dad;
return nodo;
}
Questa funzione invece serve a “legare” il nodo creato a qualche altro nodo, in modo da potere creare un albero.
In input si hanno 4 puntatori a nodo, e in output si ha il primo puntatore in input, aggiornato.
Cominciamo adesso con le visite di questo albero. Cosa si intende per visita? Per visita si intende un controllo sequenziale di tutti i nodi a partire dalla radice dell’albero, e può essere utile per la ricerca di un nodo con un particolare valore all’interno di un albero.
Tuttavia, non ho implementato algoritmi di visita al fine di implementare ricerche, ma mi sono curato solo ed esclusivamente di mostrare l’ordine di controllo dei nodi in visite diverse.
Visita n°1:
Preordine:
void visitapreordine(Nodepointer start)
{
if (start == NULL) return;
start->markup = 1;
printf("%d %d\\\\\\\\n", start->valore, start->markup);
visitapreordine(start->son_sx);
visitapreordine(start->son_dx);
}
E’ una visita DFS ovvero Depth First Search, o normalmente detta visita in profondità.
Ha in input il nodo di partenza della ricerca, in output non restituisce nulla.
Si controlla per prima cosa che l’albero sia consistente, che quindi non si tratti di un albero degenere in un solo nodo, in tal quale caso, si ritorna immediatamente.
Quindi si visita il nodo (ho scelto semplicemente di stampare a video il valore) e si marca come visitato. Successivamente, si ripete ricorsivamente la funzione sul sottoalbero sinistro, e sul sottoalbero destro.
Visita n°2:
Simmetrica:
void visitasimmetrica(Nodepointer start)
{
if (start == NULL) return;
visitasimmetrica(start->son_sx);
start->markup = 1;
printf("%d %d\\\\\\\\n", start->valore, start->markup);
visitasimmetrica(start->son_dx);
}
Anche questa è una visita DFS ovvero Depth First Search, o normalmente detta visita in profondità.
Questa funzione, a differenza della precedente, agisce prima sul sottoalbero sinistro, poi sulla radice, quindi sul sottoalbero destro.
Visita n°3:
PostOrdine:
void visitapostordine(Nodepointer start)
{
if (start == NULL) return;
visitapostordine(start->son_sx);
visitapostordine(start->son_dx);
start->markup = 1;
printf("%d %d\\\\\\\\n", start->valore, start->markup);
}
Anche questa è una visita DFS ovvero Depth First Search, o normalmente detta visita in profondità.
Questa funzione agisce prima sui sottoalberi sinistro e destro, e poi sulla radice.
int main()
{
Nodepointer point1, point2, point3, point4, point5, point6, point7, point8;
point1 = creaNodo(100);
point2 = creaNodo(200);
point3 = creaNodo(300);
point4 = creaNodo(400);
point5 = creaNodo(500);
point6 = creaNodo(600);
point7 = creaNodo(700);
point8 = creaNodo(800);
settings(point1,point2,point3,NULL);
settings(point2,point4,point5,point1);
settings(point3,point6,point7,point1);
settings(point4,point8,NULL,point2);
settings(point5,NULL,NULL,point2);
settings(point6,NULL,NULL,point3);
settings(point7,NULL,NULL,point3);
settings(point8,NULL,NULL,point4);
visitapreordine(point1);
visitasimmetrica(point1);
visitapostordine(point1);
}
Questa è la funzione main, che si limita a creare 8 punti, inizializzarli, settarli e richiamare le procedure di visita.
Presto mi occuperò anche della ricerca in ampiezza, che sembra essere piu difficile da implementare.
Non sei collegato