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.
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.
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.
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.
Di seguito il codice che permette di costruire un albero leggendo le chiavi da un file .txt
Mostra codiceMostra 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.
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:
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.
Utilizzando la visita IN-ORDER è possibile visualizzare un albero ruotato di 90° secondo l’algoritmo che segue:
Mostra codiceIn figura è mostrato un esempio di output.
Visitare tutti i nodi di un BST di interi, attraversando:
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
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.
Visitare tutti i nodi di un BST di interi, attraversando:
Per contare quanti nodi ci sono in un albero si può utilizzare una ricorsione con accumulazione come mostrato di seguito:
Mostra codicePer 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 codiceUn 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 codiceAnalogo approccio può essere utilizzato per la stampa dei nodi di un preassegnato livello n:
Mostra codicePer costruire un albero non ordinato casuale si può usare la seguente funzione, AlberoCasuale, che richiama la funzione Insert mostrata di seguito:
Mostra codice Mostra codiceUn algoritmo per stabilire se due alberi sono uguali è il seguente:
Mostra codiceTutti gli algoritmi descritti nei lucidi precedenti sono contenuti nell’allegato Alberi generale di cui nelle figure si mostra un output.