1. Definizione di Albero


Rappresentazione della Struttura Dati Albero Binario di Ricerca



Scaricare 142.5 Kb.
Pagina7/11
21.12.2019
Dimensione del file142.5 Kb.
1   2   3   4   5   6   7   8   9   10   11

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.




Condividi con i tuoi amici:
1   2   3   4   5   6   7   8   9   10   11


©astratto.info 2019
invia messaggio

    Pagina principale