Elaborazione di un Albero binario. L'albero che si propone nel seguente esercizio memorizza numeri interi.

Per ogni nodo, a sinistra ci sono i valori minori e a destra i valori maggiori del valore contentuto nel nodo.
Esempio:

il file Albero.h

Nr.
linea
Commento
3questa dichiarazione serve ad informare il compilatore che l'identificatore Nodo è una struttura.
4, 5l'identificatore pNodo è di tipo "puntatore a Nodo". (il compilatore ha appreso nella linea precedente il tipo dell'identificatore Nodo) e Elemento è un nuovo tipo di variabile intera.
6Alberobinario è una classe.
8radice è di tipo pNodo (come definito alla linea 4).
9, 15Sezione dei metodi privati
17, 25Sezione dei metodi pubblici

il file Albero.cpp: Definizione della struttura Nodo

Nr.
linea
Commento
4Nodo è una struttura.
7il campo che contiene l'informazione è costituito da un intero.
8, 9Ogni nodo dell'albero ha due puntatori ai nodi successori.


il file Albero.cpp: il costruttore e il distruttore

Nr.
linea
Commento
2Il costruttore assegna il valore iniziale zero al puntatore alla radice dell'albero, per indicare che l'albero è vuoto.
5Il distruttore richiama il metodo privato Svuota per rilasciare la memoria occupata dai nodi creati dinamicamente.


il file Albero.cpp: il metodo AggiungiElem

Nr.
linea
Commento
1Il metodo AggiungiNodo riceve il riferimento ad un valore da memorizzare nell'albero.
2Richiama il metodo AggiungiElem passando il riferimento alla radice dell'albero e il riferimento al valore da inserire.
5la prima volta che la funzione viene richiamata la radice vale zero.
Quando l'albero contiene almeno un elemento il riferimento al nodo è diverso da zero quindi verrà eseguito il ramo else .
6 - 9viene creato un nuovo nodo, viene inizializzato con il dato ricevuto e con i due puntatori a zero. Si deve notare che il parametro n è dichiarato come riferimento quindi, la prima volta, alla linea 6 viene modificato anche il valore di radice, o comunque del puntatore contenuto nel nodo genitore.
11si deve decidere se il nodo deve essere inserito nel sotto albero di destra o di sinistra.
12 - 14Avviene una chiamata ricorsiva alla funzione, accedendo ad uno dei due sottoalberi del nodo.



il file Albero.cpp: il metodo inAlbero

Nr.
linea
Commento
1riceve, come parametro, un valore e restituisce un valore logico per indicare se il valore è presente nell'albero.
5se si raggiunge un nodo terminale significa che il valore non è stato trovato.
7, 8se il valore cercato corrisponde al valore contenuto nel nodo si restituisce true
10, 12altrimenti si richiama ricorsivamente la funzione passando il puntatore al sottoalbero appropriato.

il file Albero.cpp: il metodo Sostituisci

Nr.
linea
Commento
1il metodo Sostituisci riceve il puntatore n alla radice di un albero e il puntatore p ad un nodo da sostituire
2q è il puntatore a un nodo
3se il sottoalbero destro è vuoto
4copia il puntatore al nodo corrente
5con n avanza nel sottoalbero sinistro
6nel puntatore a sinistra del sottoalbero corrente copia il puntatore a sinistra contenuto nel nodo da sostituire
7nel puntatore a destra del sottoalbero corrente copia il puntatore a destra contenuto nel nodo da sostituire
8il puntatore al nodo da sostituire viene aggiornato con il puntatore al nodo corrente.
10altrimenti (se il sottoalbero destro non è vuoto) richiama ricorsivamente la funzione passando come parametri il sottoalbero destro e il nodo da sostituire. La condizione di arresto della chiamata ricorsiva è che il sottoalbero destro sia vuoto.

il file Albero.cpp: il metodo Elimina

Nr.
linea
Commento
1il metodo Elimina riceve il puntatore alla radice dell'albero e il valore dell'elemento da eliminare
2se non si è raggiunta una foglia
3e se il campo dato è uguale al valore cercato
4copia il puntatore al nodo corrente
5se il sottoalbero sinistro del nodo da eliminare è vuoto
6sostituisci il nodo con il sottoalbero destro
8altrimenti se il sottoalbero destro del nodo da eliminare è vuoto
9sostituisci il nodo con il sottoalbero sinistro
10il nodo da eliminare ha entrambi i sottoalberi
11richiama la funzione Sostituisci
12cancella il nodo
13se il campo dato è diverso dal valore da eliminare
14se il valore da eliminare è maggiore del valore contenuto nel campo dato
15richiama ricorsivamente la funzione accedendo al sottoalbero destro
17altrimenti richiama ricorsivamente la funzione accedendo al sottoalbero sinistro

il file Albero.cpp: il metodo Svuota

Nr.
linea
Commento
2Se il sottoalbero non è vuoto
3, 4richiama ricorsivamente la funzione svuota passando il puntatore a uno dei due sottoalberi
5al ritorno dalla funzione elimina il nodo

il file Albero.cpp: visita il ordine anticipato

Nr.
linea
Commento
2se non si è raggiunta una foglia
3stampa il dato
4avanza a sinistra
5quando si è esaurito il sottoalbero sinistro avanza nel sottoalbero destro

il file Albero.cpp: visita il ordine differito

Nr.
linea
Commento
2se non si è raggiunta una foglia
3avanza nel sottoalbero sinistro
4quando si è esaurito il sottoalbero sinistro avanza nel sottoalbero destro
5mostra il dato
5

il file Albero.cpp: le funzioni pubbliche

Ciascuna funzione del menu richiama una funzione membro, specificando la radice. La sintassa usata dalle funzioni membro consente di realizzare la ricorsione.

il file Albero.cpp: le voci del menu


il file Albero.cpp: la funzione main