Come implementare gli alberi in C

tramite: O2O
Difficoltà: difficile
14

Introduzione

In informatica per rappresentare dei dati si usano le strutture dati. Le strutture dati sono dei metodi per organizzare dati. A seconda delle operazioni che vogliamo fare su un insieme di dati, possiamo scegliere una struttura dati invece che un'altra. In particolare gli alberi sono una struttura dati astratta che si presta ad un ordinamento parziale. Solitamente in informatica si fa molto uso degli alberi binari. Gli alberi binari sono una sottocategoria degli alberi in cui ogni nodo può avere al più due figli. Una possibile definizione degli alberi binari può essere la seguente:
Dato un insieme X, un albero binario è :
1. Un albero vuoto, oppure
2. Una tripla ordinata (x, L, R) dove x è un elemento di X, L è il sottoalbero destro e R il sottoalbero sinistro.
Null'altro è un albero binario.

Nel linguaggio C. Per implementare gli alberi si fa uso delle struct. Si usa una struct che ha tre campi: un campo dedicato al dato e due puntatori, uno al sottoalbero destro e l'altro al sottoalbero sinistro.
In questo articolo andremo a vedere come implementare gli alberi binari in c e a discutere di alcune proprietà intrinseche alla struttura dati albero.

24

Dichiarazione della struttura dati

Per definire gli alberi prima di tutto dobbiamo dichiarare la struct che andrà a rappresentare un singolo nodo dell'albero. Quindi fuori dal main procediamo a definire la struct (questo passo serve solo a definire come è fatta la struct ma non riserva nessuno spazio di memoria).
Procediamo come segue :

struct albero {

int info; /* campo che contiene il dato che vogliamo salvare nel nodo, in questo caso stiamo
salvando un intero ma a seconda dell'occorrenza possiamo salvare un altro tipo di
dato */

struct albero *figlio_destro; /* questo sarà il puntatore al figlio destro del nodo */
struct albero *figlio_sinistro; /*questo è il puntatore che punta al figlio sinistro del nodo*/
}

In questo modo siamo pronti a dichiarare un albero vuoto nel main semplicemente digitando l'istruzione :

struct albero *root = NULL;
.

34

Alcune proprietà e relazioni sugli alberi binari

Per fare riferimento ai nodi dell'albero e alle relazioni fra di essi, si usano alcuni termini specifici:

1. Il nodo di un albero binario si dice foglia se entrambi i suoi sotto alberi sol no vuoti.
2. Un nodo si dice interno se ha almeno un sotto albero non vuoto.
3. Un percorso dal nodo i al nodo j è la sequenza di archi che viene attraversata per raggiungere
il nodo j partendo da i. La lunghezza del percorso è il numero di archi attraversato.
4. La profondità di un albero è il numero di archi che serve per raggiungere quel nodo partendo dalla radice.
5. L'altezza di un albero è la maggiore profondità considerando tutti i nodi.

Continua la lettura
44

Funzione per calcolare l'altezza di un albero

Una delle funzioni maggiormente usata quando si ha a che fare con un albero è certamente quella che dato un albero in input ci dà in output la sua altezza.
Per costruire in C questa funzione andremo ad usare il concetto di ricorsione. La ricorsione è molto utilizzate per strutture dati come gli alberi e anche le liste perché le definizioni di queste strutture dati sono proprio ricorsive.

Per implementare la funzione "altezza" faremo in questo modo:

int altezza (struct albero *root) /* la funzione è di tipo intero perché l'altezza che restituirà
è di tipo intero */

int h1, h2;
if (root==NULL) /*CASO BASE*/
return -1;
else { /*PASSO INDUTTIVO*/
h1 = altezza (root->figlio_sinistro);
h2= altezza (root->figlio_destro);
}

if (h1>h2)
return h1;
else
return h2:
}
.

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Programmazione

Come implementare i grafi in C

I grafi come gli esperti di informatica sanno, sono uno strumento molto potente per la rappresentazione dei problemi e molte volte anche dei problemi complessi. Infatti, le soluzioni ai cosiddetti problemi complessi possono essere trovate con i grafi...
Programmazione

Realizzare una semplice finestra grafica in Java

Java è un linguaggio di programmazione interamente dedicato agli oggetti ed offre costrutti utili, semplici e intuitivi per gestire ed implementare la totalità dei compiti che un programmatore desidera. La guida di oggi vuole mostrare come realizzare...
Programmazione

Guida alla programmazione a basso livello

In questa guida tratteremo della programmazione a basso livello. Nei vari passi successivi all'introduzione vi rilascio molte informazioni molto utili che vi aiuteranno certamente a programmare sempre meglio a basso livello. Un consiglio che vi dò e...
Programmazione

Come realizzare un'agenda personalizzata

Mediante tale tutorial vi spiegheremo come realizzare un'agenda personalizzata usando il linguaggio di programmazione Java. Lo scopo che vi vogliamo far capire è quello senza l'uso dell'interfaccia grafica, e quindi quello della struttura di un'agenda...
Programmazione

Come spostare un file in Java

Spostare i file in Java potrebbe sembrare inizialmente un'operazione complessa, ma con un po' di attenzione potremo farlo semplicemente da soli, senza dunque rivolgerci ad un tecnico informatico specializzato. Così facendo, non solo potremo imparare...
Programmazione

Il metodo di ordinamento Quicksort

Chiunque di noi (programmatori) si è trovato davanti alla necessità di dover ordinare dei dati, e sappiamo che, siano essi pochi o molti, il coefficiente di difficoltà per risolvere il problema rimane lo stesso. Proprio per agevolare la vita a chiunque...
Programmazione

Come imparare a programmare in C++

L'avvento del computer, ha richiesto la creazione di appositi linguaggi per facilitare la comunicazione tra utente e macchina. I linguaggi sono aumentati di numero e via via è aumentata anche la facilità di comunicazione tra questi due canali. Si parla...
Programmazione

Come Scrivere Su Schermo In Linguaggio C

Il linguaggio C è un linguaggio di programmazione classificabile come 'general purpose', nel senso che non è specifico per applicazioni particolari (gestionali, scientifiche, ludiche, ecc.), ma risulta adatto per la maggior parte delle esigenze informatiche....
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.