1. Definizione di Albero



Scaricare 99.64 Kb.
17.11.2017
Dimensione del file99.64 Kb.

Prof.S.Cavalieri a.a.2009/2010

Struttura Dati Astratta ABR



La Struttura Dati Astratta Albero Binario di Ricerca (ABR)

1.Definizione di Albero


In informatica, un albero è, per definizione, un insieme di elementi chiamati nodi e da relazioni tra i nodi stessi. Per un albero, devono valere le seguenti proprietà:

  1. Un albero che non contiene nodi si dice vuoto.

  2. Se l’albero non è vuoto, tra tutti i nodi dell'albero, solo uno, prende il nome di "radice"; tale elemento deve esistere necessariamente e deve essere unico.

  3. Tra tutti i nodi dell'albero esiste una particolare relazione tale che: preso un qualunque nodo dell'albero tranne la radice, per tale nodo è possibile individuare sempre uno ed un solo nodo dell'albero, che viene denominato "genitore"; ovviamente esisteranno alcuni nodi per i quali il nodo genitore è rappresentato dalla radice dell'albero stesso. Nel seguito, tutti i nodi posti in relazione con un nodo genitore verranno chiamati nodi "figli".

  4. L'albero è connesso, nel senso che preso un qualunque nodo tranne la radice e procedendo verso il suo genitore, e poi verso il genitore del genitore e così via, si arriva sempre alla radice.

Per una maggiore comprensione, un albero può essere rappresentato graficamente nella seguente maniera.

Come si vede, ogni nodo è stato rappresentato da un cerchio ed etichettato in modo univoco. E' possibile distinguere la radice, e le relazioni tra i nodi sono rappresentate da una linea. Tali relazioni collegano i "figli" con uno ed un solo "genitore". Ad esempio n5, n6 e n7 hanno come genitore il nodo n1. Si può verificare che l'albero in figura è connesso, mentre il seguente insieme di nodi, anche se molto simile, non risulta connesso, e, dunque, non può definirsi albero.

Come si vede, infatti, considerando i nodi n8 o n9 e procedendo verso i nodi genitori non è possibile pervenire alla radice dell'albero.


1.1. Cammino, Altezza e Profondità di un Albero


Sia data una sequenza m1, m2, m3, .., mk di nodi dell'albero. Se m1 è il genitore di m2, m2 è il genitore di m3 e così via, allora tale sequenza è detta cammino. La lunghezza del cammino è pari al numero di nodi che lo compongono meno 1, ossia k-1. Un cammino costituito da un solo nodo (k=1) ha dunque lunghezza 0.

Il nodo m1 è detto antenato di mk e mk è detto discendente di m1. Se la lunghezza del cammino è maggiore o uguale a 1, allora m1 è detto antenato proprio di mk e mk è detto discendente proprio di m1.

Dato un albero e un suo nodo n, si definisce altezza del nodo n il più lungo cammino che va dal nodo n ad una foglia. Se il nodo n coincide con la radice allora l'altezza è quella dell'albero.

La profondità o livello di un nodo è la lunghezza del cammino che va dalla radice al nodo n.



1.2.Definizione di Sottoalbero


Dato un albero T, un sottoalbero è costituito da un generico nodo n di T e da tutti i suoi discendenti. Il nodo n è la radice del sottoalbero.

1.3.Foglie e Nodi Interni


Dato un albero T, un suo nodo n si definisce foglia se non ha figli. Un nodo n si definisce interno se ha uno o più figli. La radice di un albero è un nodo interno se l'albero presenta altri nodi oltre alla radice. La radice è una foglia nel caso contrario, cioè se l'albero è costituito solo dalla radice.

1.4.Ordinamento dei Figli


Dato un albero T e dato un generico nodo n, è possibile individuare tra i suoi figli un ordinamento in base al quale è possibile distinguere i nodi figli. Nel seguito verranno considerati ordinamenti che permettono di individuare un figlio posto all'estrema sinistra, uno posto all'estrema destra e tutti i figli in posizione intermedia.

1.5.Contenuto di Ciascun Nodo


Gli alberi possono unicamente servire a definire relazioni tra nodi. In tal caso a ciascun nodo viene associata una etichetta in modo da poter essere distinto da qualunque altro nodo. L'etichetta assume valori appartenenti ad un determinato dominio. Ad esempio nelle figure precedenti è stata utilizzata come etichetta la sequenza nx, dove x è un numero naturale.

In altri casi ciascun nodo può contenere delle informazioni di un certo tipo. Ad esempio è possibile organizzare un archivio tramite particolari strutture arboree. In tal caso, ciascun nodo verrà sempre distinto da un altro attraverso una particolare etichetta, ma in più conterrà una o più informazioni, ciascuna appartenente ad un determinato dominio.

Nel seguito la trattazione sugli alberi verrà focalizzata sulle strutture arboree utilizzate per la memorizzazione di informazioni, tipicamente per la realizzazione e la gestione di archivi. In particolare, supporremo che il contenuto informativo di ciascun nodo dell'albero binario di ricerca appartenga al tipo generico denominato tipobaseABR.

1.6.Alberi Binari


Un albero si dice binario quando ogni genitore può avere al più due figli. Sui figli di ciascun nodo è possibile individuare un ordinamento, in base al quale è possibile distinguere un figlio sinistro e l'altro figlio destro (rappresentati graficamente dalla relativa posizione). La seguente figura mostra un albero binario, in cui il nodo n1 e n4 sono i figli sinistro e destro della radice. Analogamente i nodi n5 e n7 sono i figli sinistro e destro di n1. Il nodo n4 ha solo un figlio destro n10.

2.Struttura Dati Astratta Albero Binario di Ricerca (ABR)


La definizione di un albero binario non implica la definizione della strategia di inserimento, ricerca e cancellazione delle informazioni memorizzate in un albero. A tal proposito possono essere definite infinite strategie. Quella che presenta numerosi vantaggi è quella basata sul seguente concetto.

In genere un nodo ha un contenuto informativo appartenente ad un certo tipo (dominio). Si supponga di aver definito gli operatori "<" e ">" (minore e maggiore) per il tipo di appartenenza di ciascun elemento nel nodo.

Una particolare modalità di gestione dell'albero binario consiste nel disporre i nodi nell'albero binario, in modo che preso un qualunque nodo dell'albero, tutti i nodi del sottoalbero di sinistra contengono elementi che risultano minori, in accordo all'operatore "<", dell'elemento del nodo, e tutti i nodi del sottoalbero di destra contengono elementi che risultano maggiori, secondo l'operatore ">", dell'elemento del nodo.

Nel caso in cui un nodo contenga più elementi di tipo diverso (ad esempio si pensi ad uno struct in C), in genere la relazione di ordine tra i nodi viene compiuta su uno solo tra questi elementi, denominato chiave di ricerca. Ovviamente tutte le operazioni di inserimento, ricerca e cancellazione devono usare la stessa chiave di ricerca !



L'organizzazione appena descritta prende il nome di ALBERO BINARIO DI RICERCA. Il vantaggio principale di tale organizzazione risiede essenzialmente nell’abbattimento dei tempi necessari alla ricerca di un elemento. Ogni volta che è necessario ricercare un elemento, il confronto del valore dell'elemento con quello contenuto in un generico nodo (o con la chiave di ricerca scelta), permette di eliminare dalla ricerca o il sottoalbero corrente di destra o quello di sinistra. Visto che la ricerca di un elemento è sempre presente sia nella fase di inserimento che in quella di cancellazione, il vantaggio di utilizzare una albero binario di ricerca è notevole.

2.1.Funzioni Primitive di una Struttura Dati ALBERO BINARIO DI RICERCA


Siano:

  • n l'etichetta che contraddistingue un generico nodo di una Albero Binario di Ricerca

  • x un generico valore appartenente al dominio tipobaseABR, ossia del tipo memorizzato in ciascun elemento dell'albero.

Le seguenti funzioni primitive sono definite per l’Albero Binario di Ricerca (ABR):

  • EmptyABR(n). Restituisce il valore booleano vero se l'albero binario di ricerca avente n come radice è vuoto.

  • FullABR(n). Restituisce il valore booleano vero se l'albero binario di ricerca avente n come radice è pieno.

  • LeftChild(n). Restituisce il nodo figlio sinistro del nodo n dell'albero binario di ricerca.

  • RightChild(n). Restituisce il nodo figlio destro del nodo n dell'albero binario di ricerca.

  • Label(n). Fornisce il contenuto informativo del nodo n dell'albero binario di ricerca.

  • MakeNullABR(n). La funzione inizializza l'albero binario di ricerca la cui radice è individuata dal nodo n. Si ricorda che l’inizializzazione consente di garantire che tale albero sia vuoto, ma non permette di svuotare un albero binario di ricerca contenente elementi, che devono essere estratti uno per uno.

  • Member(n, x). La funzione ricerca l'elemento x nell'albero binario di ricerca avente per radice il nodo n. Fornisce il valore vero se l'elemento esiste, falso in caso contrario.

  • InsertABR(n, x). La funzione inserisce l'elemento x nell'albero binario di ricerca avente come radice il nodo n. La funzione non effettua alcun inserimento se l'elemento x esiste già nell'albero.

  • Delete(n, x). La funzione elimina l'elemento x, se esiste, dall'albero binario di ricerca caratterizzato dal nodo n come radice.



3.Rappresentazione della Struttura Dati Albero Binario di Ricerca


Come per le pile, code e liste la rappresentazione di una struttura dati Albero Binario di Ricerca può essere realizzata tramite vettori o puntatori. Nel seguito verrà considerata solo la rappresentazione basata su puntatori. Essa consiste nel rappresentare ogni nodo dell’albero Binario di Ricerca tramite un elemento di memoria allocato in modo dinamico (cioè tramite la funzione malloc() in C). Tale elemento di memoria contiene:

  • un campo in cui è memorizzata l’informazione,

  • un campo che contiene l’indirizzo dell’elemento relativo al figlio sinistro e

  • un campo in cui è memorizzato l’indirizzo dell’elemento relativo al figlio destro.

In questa rappresentazione, la struttura dati ABR è rappresentato dal puntatore all’elemento relativo alla radice dell’ABR.

La seguente figura mostra un esempio di tale rappresentazione. Nella figura la variabile abr rappresenta la struttura dati ABR e coincide con l’indirizzo dell’elemento relativo alla radice dell’ABR. Come si vede ogni elemento contiene i tre campi descritti in precedenza.





Nel seguito verranno descritte le implementazioni delle funzioni primitive dell'ABR, sotto le ipotesi di rappresentare la struttura dati ABR tramite puntatori, come appena illustrato. Prima, però, verrà formalizzata l'implementazione dell'ABR in linguaggio C.

Con tipobaseABR intendiamo l'insieme dei valori che può assumere il contenuto informativo di ciascun nodo dell'ABR. Ad esempio, se il tipo di dato di ogni singolo elemento fosse float, l’implementazione del dominio tipobaseABR risulterebbe:
typedef float tipobaseABR;
Visto che alcune funzioni primitive restituiscono il tipo booleano, esso può essere implementato tramite il tipo short:
typedef short boolean;
Ciascun nodo dell’ABR viene rappresentato da una struttura struct nodoABR, composta da tre campi: info, leftchild, rightchild. Dunque, ciascun nodo dell'albero viene etichettato e riconosciuto dal puntatore alla struct nodoABR, puntatore che chiameremo abr.
typedef struct nodoABR {

tipobaseABR info;

struct nodoABR * leftchild , * rightchild;

} * abr;


Nell'implementazione dell'ABR ci serve una costante per indicare che un albero è vuoto. Siccome un albero è rappresentato dalla sua radice, un albero è vuoto quando non ha radice, ossia quando il puntatore alla radice vale NULL. Per questo motivo faremo uso di una costante, chiamata ALBEROVUOTO, pari al valore NULL:
#define ALBEROVUOTO NULL
Nell’implementazione delle funzioni primitive si farà uso della funzione definita dall’utente, chiamata Confronta. Essa riceve in ingresso due parametri tipobaseABR a e b:
int Confronta (tipobaseABR a, tipobaseABR b)
e restituisce:

  • 0, se a e b sono identici

  • Un numero negativo se a è minore di b

  • Un numero positivo se a è maggiore di b

Ovviamente il significato di maggiore o minore dipende dalla chiave o dalle chiavi di ricerca scelte e dal tipobaseABR. Il motivo dell’uso di tale funzione è che nell’inserimento, ricerca e cancellazione in un albero binario di ricerca è necessario utilizzare espressioni che realizzano confronti logici (uguale, maggiore e minore). Come si sa, gli operatori ==, < e > non possono essere applicati a tutti i tipi di dati (ad esempio non si possono applicare a struct). Dunque per avere delle funzioni che effettuano confronti logici e che valgano per qualunque TipobaseABR, faremo uso della funzione astratta Confronta, che implementeremo in modo diverso per ciascun TipobaseABR.

3.1.Rappresentazione delle Operazioni Primitive dell’ABR

boolean EmptyABR(abr n)

{

return(n==ALBEROVUOTO);



}
boolean FullABR(abr n)

{

return(0);



}
abr LeftChild(abr n)

{

if (!EmptyABR(n))



return(n->leftchild);

}
abr RightChild(abr n)

{

if (!EmptyABR(n))



return(n->rightchild);

}
tipobaseABR Label(abr n)

{

if (!EmptyABR(n))



return(n->info);

}
void MakeNullABR(abr *p)

{

*p=ALBEROVUOTO;



}


  • Member(n,x). La strategia di ricerca può essere realizzata nella seguente maniera:

  1. se il sottoalbero la cui radice è il nodo n è vuoto allora l'elemento x cercato non è presente.

  2. se il sottoalbero la cui radice è il nodo n non è vuoto e x compare nella radice n, allora x esiste e la funzione ritorna il valore vero.

  3. se il sottoalbero la cui radice è il nodo n non è vuoto e x non compare nella sua radice n, allora bisogna considerare il sottoalbero di destra se x è superiore, secondo la relazione d'ordine ">", dell'elemento contenuto nella radice n. Viceversa, la ricerca deve essere applicata al sottoalbero di sinistra.

I precedenti passi possono essere espressi dal seguente algoritmo ricorsivo:
boolean Member(abr n, tipobaseABR x)

{

if (EmptyABR(n)) return(0);



if (!Confronta(n->info,x)) return(1);

if (Confronta(n->info,x)>0) return(Member(n->leftchild,x));

else return(Member(n->rightchild,x));

}


  • InsertABR(n, x). La strategia di inserimento può essere realizzata nella seguente maniera:

  1. se il sottoalbero la cui radice è il nodo n è vuoto allora viene generato un nuovo sottoalbero contenente unicamente un nodo radice, nella quale viene memorizzato l'elemento x.

  2. se il sottoalbero la cui radice è il nodo n non è vuoto e x compare nella radice di tale sottoalbero, allora x esiste e non si deve inserire.

  3. se il sottoalbero non è vuoto e x non compare nella sua radice, allora bisogna considerare il sottoalbero di destra se x è superiore, secondo la relazione d'ordine ">", dell'elemento contenuto nella radice. Viceversa, l'inserimento deve essere applicato al sottoalbero di sinistra.

I precedenti passi possono essere espressi dal seguente algoritmo ricorsivo:
void InsertABR(abr *p, tipobaseABR x)

{

if (EmptyABR(*p)) {



*p=(struct nodoABR *)malloc(sizeof(struct nodoABR));

(*p)->info=x;

(*p)->leftchild=(*p)->rightchild=ALBEROVUOTO;

} else if (Confronta((*p)->info,x)>0) InsertABR(&(*p)->leftchild,x);

else if (Confronta((*p)->info,x)<0) InsertABR(&(*p)->rightchild,x);

}
/*da notare che se Confronta((*p*)->info,x)==0 allora l’elemento x non viene inserito*, visto che è già presente nell’ABR/




  • Delete(n, x). L'algoritmo di cancellazione è più complesso rispetto quello di inserimento e di ricerca. I passi principali di cui si compone possono essere riassunti nel seguente modo:

  1. se il sottoalbero, la cui radice è il nodo n, è vuoto allora l'elemento x cercato non è presente, dunque non può essere cancellato.

  2. se il sottoalbero, la cui radice è il nodo n, non è vuoto e x non compare nella sua radice, allora bisogna considerare il sottoalbero di destra se x è superiore dell'elemento contenuto nella radice. Viceversa si deve considerare il sottoalbero di sinistra.

  3. se il sottoalbero, la cui radice è il nodo n, non è vuoto e x compare nella radice di tale sottoalbero, allora x esiste e deve essere cancellato. La cancellazione deve continuare a garantire le proprietà dell'ALBERO BINARIO DI RICERCA. La modalità con cui l'elemento deve essere cancellato è differente e dipende dal fatto che il nodo è interno o è una foglia. Si consideri l'esempio mostrato in Figura 1.


Figura 1
In riferimento all’ABR mostrato in Figura 1, sono possibili differenti casi:



  • Caso 1. Il nodo da cancellare è una foglia allora la cancellazione è semplice e consiste nell'eliminazione della foglia stessa. In tal caso le proprietà dell'ABR sono palesemente mantenute. Ciò accade quando, considerando l’esempio precedente bisogna cancellare il nodo 7, 11, 13, 15, 18 o 20.

  • Caso2. Se il nodo è interno allora bisogna differenziare se esso possiede uno o due figli. Se possiede un solo figlio allora il nodo può essere eliminato e sostituito dalla radice dell'unico sottoalbero. Le proprietà dell'ABR sono mantenute perché il nodo cancellato apparteneva ad un sottoalbero contenente elementi tutti più grandi o tutti più piccoli rispetto al genitore del nodo cancellato. Dunque se noi sostituiamo il nodo cancellato con il nodo radice del suo sottoalbero, tutto questo sottoalbero continua a contenere elementi o tutti più grandi o tutti più piccoli del genitore del nodo cancellato, mantenendo le proprietà dell'ABR. Il caso 2 si verifica ad esempio quando si deve cancellare il nodo 6, 10 o 17.

  • Caso 3. Le cose sono più complesse se il nodo da cancellare presenta due figli. In tal caso la cancellazione del nodo comporta la presenza di due sottoalberi distinti aventi come radice il figlio destro e il figlio sinistro del nodo da cancellare. Il problema è come connettere questi sottoalberi mantenendo le proprietà dell'ABR. Sia TS il sottoalbero la cui radice è il figlio sinistro del nodo da cancellare e TD il sottoalbero la cui radice è il figlio destro del nodo da cancellare. È chiaro che tutti gli elementi di TD sono più grandi di tutti gli elementi di TS. Una soluzione potrebbe essere quella di sostituire il nodo cancellato con il più piccolo elemento di TD o con il più grande elemento di TS. Nel primo caso sia min l'elemento più piccolo di TD. Se min è messo al posto del nodo cancellato verrà formato un albero T che ha per radice un elemento min, che risulta più grande di tutti gli elementi di TS, perchè min apparteneva a TD, e più piccolo di tutti gli elementi di TD per ipotesi. Dunque la proprietà dell'ABR è mantenuta. Nel secondo caso, se max è l'elemento più grande di TS, e se esso viene sostituito al nodo cancellato, otteniamo un albero T che ha come radice l'elemento max, che è più grande di tutti gli elementi di TS per ipotesi e più piccolo di tutti gli elementi di TD perché max apparteneva a TS. Quindi anche in questo caso la proprietà degli ABR è mantenuta. Con riferimento all’esempio fornito, si supponga di dover cancellare il nodo 16. In tal caso, esso può essere sostituito dal massimo nodo del sottoalbero di sinistra, ossia dal nodo 15. Oppure esso può essere sostituito dal più piccolo nodo del sottoalbero di destra, ossia dal nodo 17. In entrambi i casi la proprietà degli ABR è rispettata. Nel seguito si farà l'ipotesi di sostituire il nodo cancellato con il più piccolo tra gli elementi del sottoalbero di destra TD. In accordo a tale ipotesi, l’albero mostrato in Figura 1, diventa quello mostrato in Figura 2, a seguito della cancellazione del nodo 16.





Figura 2 - Esempio della Procedura di Cancellazione
In accordo a quanto detto, la funzione di cancellazione risulta:

void Delete(abr *p, tipobaseABR x)

{

abr tmp;


if (!EmptyABR(*p)) {

if (!Confronta((*p)->info,x)) {

tmp=*p;

if (EmptyABR((*p)->leftchild)) {



*p=(*p)->rightchild;

free (tmp);

} else if (EmptyABR((*p)->rightchild)) {

*p=(*p)->leftchild;

free (tmp);

} else {


*p=DelMin(&(*p)->rightchild);

(*p)->leftchild=tmp->leftchild;

(*p)->rightchild=tmp->rightchild;

free (tmp);

}

} else if (Confronta((*p)->info,x)>0) Delete(&(*p)->leftchild,x);



else Delete(&(*p)->rightchild,x);

}

}


dove la funzione DelMin restituisce il puntatore al nodo più piccolo del sottoalbero di destra:
abr DelMin(abr *p)

{

abr pmin;



if ((*p)->leftchild==ALBEROVUOTO) {

pmin=*p;


*p=(*p)->rightchild;

return(pmin);

} else return(DelMin(&(*p)->leftchild));

}
Infatti, l’elemento più piccolo del sottoalbero di destra è quello posto più a sinistra che non possiede alcuno figlio sinistro.



4.Operazioni Non Primitive sulla Struttura Dati Astratta ABR




4.1.Algoritmi di Visita


Alcune tra le procedure ricorsive più utilizzate per gli alberi binari di ricerca sono le visite. Esse possono essere in preordine, in ordine e in postordine. Le differenze risiedono nelle modalità con cui le chiamate ricorsive si susseguono.
Visita di un Albero in Preordine

La visita in preordine di un generico albero T, consiste nel compiere una determinata azione di accesso al contenuto informativo della radice dell'albero T, e poi applicare ricorsivamentre la procedura ai due sottoalberi aventi come radice i figli della radice, partendo dal sottoalbero a sinistra e procedendo con quello a destra. L'azione di accesso al contenuto informativo di ciascun nodo dipende ovviamente dal singolo problema. Nel seguito, per semplicità, si supporrà che l'operazione di accesso al contenuto informativo è quella relativa alla sua visualizzazione sullo schermo; supponendo che il tipobaseABR sia un float, l’accesso all’informazione contenuta in ogni nodo dell’ABR sarà:


void VisualizzaElemento(tipobaseABR x)

{

printf("\n%f ", x);



}

void preordine(abr n)

{

if (!EmptyABR(n)) {



VisualizzaElemento(Label(n));

preordine(LeftChild(n));

preordine(RightChild(n));

}

}


Visita di un Albero in Ordine

La visita in ordine di un generico albero T, consiste nell'applicare la visita ricorsivamente al sottoalbero di sinistra della radice di T, poi nel visitare la radice di T e poi nell'applicare ricorsivamentre la procedura al sottoalbero di destra. La procedura è:

void inordine(abr n)

{

if (!EmptyABR(n)) {



inordine(LeftChild(n));

VisualizzaElemento (Label(n));

inordine(RightChild(n));

}

}


Visita di un Albero in Postordine

La visita in postordine di un generico albero T, consiste nell'applicare ricorsivamente la procedura ai sottoalberi aventi come radice i due figli della radice (procedendo da quello a sinistra verso quello a destra) e poi nell'applicare la visita alla radice dell'albero T. La procedura è:


void postordine(abr n)

{

if (!EmptyABR(n)) {



postordine(LeftChild(n));

postordine(RightChild(n));

VisualizzaElemento(Label(n));

}

}



4.2.Altezza di un Nodo


La seguente funzione determina l’altezza di un ABR la cui radice è individuata dal puntatore rappresentato dalla variabile n di tipo abr.
unsigned int altezza(abr n)

{

unsigned int a=0,h;



abr tmp;
tmp=LeftChild(n);

if (!EmptyABR(tmp)) {

h=altezza(tmp);

if (h>=a) a=h+1;

}

tmp=RightChild(n);



if (!EmptyABR(tmp)) {

h=altezza(tmp);

if (h>=a) a=h+1;

}

return(a);



}

4.3.Distruzione di un Albero


L’eliminazione di tutti gli elementi di un albero, può essere realizzata tramite l’uso delle funzioni EmptyABR e Delete:

while (!EmptyABR(n))

Delete(&n,Label(n));
dove n è il puntatore alla radice dell'albero che si vuole distruggere.

5.Un'Applicazione relativa alla Gestione di un Albero Binario di Ricerca


Il seguente programma gestisce una struttura dati ABR contenente elementi di tipo struct composti da tre campi: cognome, nome ed età. Si suppone l’esistenza di un file di nome “abr.h” contenente l’implementazione dell’ADT ABR (con puntatori), la definizione del tipobaseABR e tutte le funzioni primitive.
#include
void flush(void);
#include "abr.h"
abr albero;
void preordine(abr);

void inordine(abr);

void postordine(abr);

unsigned int altezza(abr);


main(){

unsigned short scelta;

tipobaseABR elemento;
MakeNullABR(&albero);
do {

printf("\nMenu di Operazioni ABR \n ");

printf("\n1-Inserimento ");

printf("\n2-Ricerca ");

printf("\n3-Cancellazione ");

printf("\n4-Visita Albero Binario di Ricerca in Preordine ");

printf("\n5-Visita Albero Binario di Ricerca in Ordine ");

printf("\n6-Visita Albero Binario di Ricerca in Postordine ");

printf("\n7-Calcolo Altezza ABR ");

printf("\n8-Eliminazione ABR ");

printf("\n9-Fine ");

printf("\nInserisci la scelta -----> ");

scanf("%u",&scelta);

flush();
switch(scelta) {

case 1 :

LeggiElemento(&elemento);

InsertABR(&albero,elemento);

break;


case 2 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto ");

else {

CercaElemento(&elemento);



if (Member(albero,elemento))

printf("\nElemento Trovato \n ");

else printf("\nElemento non Trovato \n ");

}

break;



case 3 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto ");

else {

CercaElemento(&elemento);



Delete(&albero,elemento);

}

break;



case 4 :

if (EmptyABR(albero)) printf("\n Albero Vuoto \n");

else preordine(albero);

break;


case 5 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto \n");

else inordine(albero);

break;


case 6 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto \n");

else postordine(albero);

break;


case 7 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto \n");

else printf("\nL'altezza dell'ABR e' %u ",altezza(albero));

break;


case 8 :

while (!EmptyABR(albero))

Delete(&albero,Label(albero));

}

} while (scelta<9);



}
void flush(void){

while (getchar()!='\n');

}
void preordine(abr n){

if (!EmptyABR(n)) {

VisualizzaElemento(Label(n));

preordine(LeftChild(n));

preordine(RightChild(n));

}

}


void inordine(abr n){

if (!EmptyABR(n)) {

inordine(LeftChild(n));

VisualizzaElemento(Label(n));

inordine(RightChild(n));

}

}


void postordine(abr n){

if (!EmptyABR(n)) {

postordine(LeftChild(n));

postordine(RightChild(n));

VisualizzaElemento(Label(n));

}

}


unsigned int altezza(abr n){

unsigned int a=0,h;

abr tmp;

tmp=LeftChild(n);

if (!EmptyABR(tmp)) {

h=altezza(tmp);

if (h>=a) a=h+1;

}

tmp=RightChild(n);



if (!EmptyABR(tmp)) {

h=altezza(tmp);

if (h>=a) a=h+1;

}

return(a);



}

5.1.File abr.h

#include


#define ALBEROVUOTO NULL
#define STR 15
typedef struct {

char cognome[STR], nome[STR];

unsigned short eta;

} tipobaseABR;


typedef short boolean;
typedef struct nodoABR {

tipobaseABR info;

struct nodoABR * leftchild , * rightchild;

} * abr;
void LeggiStringa(char s[],unsigned short dim){

unsigned short i;

for (i=0; (s[i]=getchar())!='\n' && i

s[i]='\0';

}
void LeggiElemento(tipobaseABR * x){

printf("\nInserisci l'Elemento ");

printf("\nInserisci il Cognome ");

LeggiStringa(x->cognome, STR);

printf("\nInserisci il Nome ");

LeggiStringa(x->nome, STR);

printf("\nInserisci l'eta' ");

scanf("%d",&x->eta);

flush();


}
void CercaElemento(tipobaseABR * x){

printf("\nRicerca per Cognome e Nome ");

printf("\nInserisci il Cognome ");

LeggiStringa(x->cognome, STR);

printf("\nInserisci il Nome ");

LeggiStringa(x->nome, STR);

}
void VisualizzaElemento(tipobaseABR x){

printf("\n\nElemento ");

printf("\nCognome = %s ", x.cognome);

printf("\nNome = %s ", x.nome);

printf("\nEta' = %d \n\n",x.eta);

}
int Confronta(tipobaseABR a, tipobaseABR b){

if (!strcmp(a.cognome,b.cognome))

return strcmp(a.nome,b.nome);

else return strcmp(a.cognome,b.cognome);

}
boolean EmptyABR(abr n){

return(n==ALBEROVUOTO);

}
boolean FullABR(abr n){

return(0);

}
abr LeftChild(abr n){

return(n->leftchild);

}
abr RightChild(abr n){

return(n->rightchild);

}
tipobaseABR Label(abr n){

return(n->info);

}
void MakeNullABR(abr *p){

*p=ALBEROVUOTO;

}
boolean Member(abr n, tipobaseABR x){

if (EmptyABR(n)) return(0);

if (!Confronta(n->info,x)) return(1);

if (Confronta(n->info,x)>0) return(Member(n->leftchild,x));

else return(Member(n->rightchild,x));

}
void InsertABR(abr *p, tipobaseABR x){

if (!FullABR(*p)){

if (EmptyABR(*p)) {

*p=(struct nodoABR *)malloc(sizeof(struct nodoABR));

(*p)->info=x;

(*p)->leftchild=(*p)->rightchild=ALBEROVUOTO;

} else if (Confronta((*p)->info,x)>0) InsertABR(&(*p)->leftchild,x);

else if (Confronta((*p)->info,x)<0) InsertABR(&(*p)->rightchild,x);

}

}
abr DelMin(abr *p){



abr pmin;

if ((*p)->leftchild==ALBEROVUOTO) {

pmin=*p;

*p=(*p)->rightchild;

return(pmin);

} else return(DelMin(&(*p)->leftchild));

}

void Delete(abr *p, tipobaseABR x){



abr tmp;

if (!EmptyABR(*p)) {

if (!Confronta((*p)->info,x)) {

tmp=*p;


if (EmptyABR((*p)->leftchild)) {

*p=(*p)->rightchild;

free (tmp);

} else if (EmptyABR((*p)->rightchild)) {

*p=(*p)->leftchild;

free (tmp);

} else {

*p=DelMin(&(*p)->rightchild);

(*p)->leftchild=tmp->leftchild;

(*p)->rightchild=tmp->rightchild;

free (tmp);

}

} else if (Confronta((*p)->info,x)>0) Delete(&(*p)->leftchild,x);



else Delete(&(*p)->rightchild,x);

}

}









©astratto.info 2017
invia messaggio

    Pagina principale