Come implementare gli alberi in C

Tramite: O2O 24/12/2017
Difficoltà: difficile
15

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.

25

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;
.

35

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
45

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

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 programmare in Ante

Ante è un linguaggio di sistema compilato che si concentra sulla fornitura di un'estrema estensibilità attraverso l'uso di un'API di compilazione. Usando tale API, le estensioni del compilatore possono essere create all'interno del programma stesso,...
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

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 definire una classe in C++

Attraverso la lettura di quest'interessante guida, andremo a occuparci del linguaggio C++. Per essere più specifici, come abbiamo avuto occasione di indicarvi nel titolo di questa guida, ci dedicheremo a spiegarvi come definire una classe all'interno...
Programmazione

Inserire elementi in una lista in C++

Molti programmatori Java o utenti principianti, trovano il linguaggio C++ uno tra i più ostici nel suo utilizzo. Java, noto per la sua semplicità, offre dei costrutti utili per gestire e manipolare una struttura dinamica quali una Lista di oggetti....
Programmazione

Come creare un'interfaccia grafica con C++

Se intendete creare un'interfaccia grafica con C++ il lavoro è possibile eseguirlo con dei programmi adatti che utilizzano in genere un'applicazione del tipo API Win32. Grazie ad essa avrete la possibilità di familiarizzare con la sua interfaccia, e...
Programmazione

Come creare animazioni con HTML5

Dalla sua nascita, il linguaggio HTML ha subito diverse modifiche e miglioramenti che, col passare del tempo, l'hanno portato alla sua ultima versione: ovvero l'HTML5. Inizialmente HTML veniva usato per la creazione di siti web statici e anche molto spartani...