Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 18.Alberi binari: operazioni


Costruzione di un BST di interi

Supponiamo di introdurre da tastiera i numeri seguenti nell’ordine indicato:

50 40 60 30 44 55 70 20 35 42 46 80 41 43 45 48 90

Man mano che introduciamo i numeri questi devono essere inseriti in un albero BST rispettando le proprietà che lo caratterizzano.

Quindi l’introduzione di 50 produrrà la creazione della radice dell’albero. L’introduzione di 40 prevede che esso sia rappresentato come figlio sinistro di 50 essendo minore di quest’ultimo. Il numero 60 andrà invece a destra perché maggiore e così via.

Di seguito mostriamo l’albero che si viene così a generare.

Costruzione di un BST di interi (segue)

I numeri vengano introdotti nel seguente ordine :

50 40 60 30 44 55 70 20 35 42 46 80 41 43 45 48 90

L’albero risultante sarà quello indicato in figura.


Costruzione di un BST

L’algoritmo di costruzione di un BST è il seguente.

Mediante una funzione ricorsiva (Insert) si esplora l’albero a destra o a sinistra al fine di individuare dove legare il nuovo nodo (in figura).

Inizialmente A=NULL, quindi, appena si entra, si richiama la funzione (Insert) che crea un nodo di chiave key1 e As e Ad (puntatori ai sottoalberi sinistro e destro) uguali a NULL.


Costruzione di un BST (segue)

Successivamente per ogni chiave introdotta, a seconda se è maggiore o minore della chiave del sottoalbero che si considera, si richiama Insert a destra o a sinistra al fine di trovare il luogo dove inserire la nuova chiave.

Questo luogo si ottiene esplorando l’albero fino a quando o il sottoalbero destro o quello sinistro non è NULL.

A questo punto ricadiamo nel caso base e realmente si inserisce il nodo.

Nel caso la chiave fosse già presente questo fatto viene segnalato e la chiave non viene introdotta nell’albero.

Costruzione di un BST (segue)

Di seguito il codice che permette di costruire un albero leggendo le chiavi da un file .txt

Mostra codice

 

Mostra codice

Allegato: Alb generale 1

Per utilizzare il codice Alb generale 1 è necessario costruire un file di nome TREE01 .txt in cui vanno inserite le chiavi dei singoli nodi dell'albero che si vuole costruire.

Cancellazione di un BST

Per eliminare un BST senza lasciare spazzatura si può attraversare l’albero in POST-ORDER e cancellare così i nodi uno alla volta. E’ utilizzato il POST-ORDER perché la root è sempre l’ultima ad essere deallocata dopo aver deallocato i nodi figli, e quindi nessun link è eliminato prima del dovuto.

void KillTree(Tnodo &Tree){

if (Tree!=NULL) {

KillTree(Tree->left);
KillTree(Tree->right);
delete Tree;
Tree=NULL;

}

}

Visitare tutti i nodi di un BST di interi, attraversando:

  • il sotto albero sinistro;
  • il sotto albero destro;
  • la radice.

Cancellazione di un BST (segue)

void KillTree(Tnodo &Tree){

if (Tree!=NULL) {

KillTree(Tree->left);
KillTree(Tree->right);
delete Tree;
Tree=NULL;

}

}

L’animazione a lato mostra la sequenza di cancellazione dei nodi con l’algoritmo proposto.

Mostra il contenuto di un BST

Utilizzando la visita IN-ORDER è possibile visualizzare un albero ruotato di 90° secondo l’algoritmo che segue:

Mostra codice

Mostra il contenuto di un BST (segue)

In figura è mostrato un esempio di output.

Visitare tutti i nodi di un BST di interi, attraversando:

  • il sotto albero destro;
  • la radice;
  • il sotto albero sinistro.

Allegato: alberi generale

Per utilizzare il codice Allegato alberi generale è necessario costruire un file di nome TREE8 .txt in cui vanno inerite le chiavi dei singoli nodi dell’albero che si vuole costruire


Ricerca di un dato in un BST

Per cercare una determinata chiave su un albero BST si può fare una esplorazione di tipo PRE-ORDER.

Di seguito vengono proposti due algoritmi: il primo, TrovaDato, è costituito da una funzione booleana che restituisce TRUE o FALSE a seconda se la chiave cercata è presente o meno nell’albero; il secondo, TrovaDatoT, restituisce invece il puntatore al nodo con la chiave cercata se trovato, altrimenti restituisce NULL.

Ricerca di un dato in un BST (segue)

Mostra codice Mostra codice

Visitare tutti i nodi di un BST di interi, attraversando:

  • la radice;
  • il sotto albero sinistro;
  • il sotto albero destro.


Conteggio dei nodi in un BST

Per contare quanti nodi ci sono in un albero si può utilizzare una ricorsione con accumulazione come mostrato di seguito:

Mostra codice

Conteggio dei nodi in un BST (segue)

Per contare quante foglie ci sono in un albero si può utilizzare ancora una ricorsione con accumulazione applicata solo al caso in cui entrambi i figli del nodo in esame sono NULL:

Mostra codice

Conteggio dei nodi in un BST (segue)

Un altro esempio di visita PRE-ORDER si ha quando viene richiesto di contare i nodi di un preassegnato livello n. In questo algoritmo oltre al caso base A==NULL è necessario aggiungere il caso base (n==0) al fine di contare solo i nodi del livello richiesto:

Mostra codice

Stampa dei nodi in un BST

Analogo approccio può essere utilizzato per la stampa dei nodi di un preassegnato livello n:

Mostra codice

Costruzione di un albero non ordinato casuale

Per costruire un albero non ordinato casuale si può usare la seguente funzione, AlberoCasuale, che richiama la funzione Insert mostrata di seguito:

Mostra codice Mostra codice

Confronto di due alberi

Un algoritmo per stabilire se due alberi sono uguali è il seguente:

Mostra codice

Altezza di un albero

Mostra codice

Riepilogo

Tutti gli algoritmi descritti nei lucidi precedenti sono contenuti nell’allegato Alberi generale di cui nelle figure si mostra un output.


I materiali di supporto della lezione

Alberi generale

Albero generale 1

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion