|
Sezione
 |
Servizio |
|
|
 |
Allegati & Link |
PAGINE di Luigi De Vivo/1
[10 di 12]
|
27/09/02 |
La responsabilità di questo programma è a cura e merito di
Luigi De Vivo |
 |
 | Questo programma è offerto da
Luigi De Vivo; si tratta
di un programma che affronta il tema degli Alberi
Binari di Ricerca, tipico della gestione dei dati. |
| Data la sua alta specializzazione l'Autore del sito lascia
la parola all'Autore del programma... |
| Tutto il testo seguente è opera sua e, per ulteriori
spiegazioni possiamo riferirci al suo recapito postale (dvlugi@inwind.it). |
| Il programma ha solo lo scopo di mostrare "la potenza"
dell'algoritmo, utilizzato nella gestione di dati per la ricerca, modifica,
cancellazione, ecc. |
| Vettori,
sequenze e pile appartengono ad una classe
di tipi strutturati che possiamo dire
lineare. |
| Con il termine lista lineare
si intende una struttura informatica costituita da un insieme di
s elementi (con s>0) x1,x1,x1,..,xs,
ordinati in modo che ciascun elemento eccettuato il primo e l’ultimo abbia un
predecessore ed un successore. |
| Il tipo più semplice di struttura non
lineare è l’Albero Binario, un
insieme Q di nodi tali che:
 | se Q non è vuoto, un nodo I è designato come radice; |
| i restanti nodi possono essere ripartiti in 2 insiemi
disgiunti Q1 e Q2 ciascuno dei quali è a sua volta un albero binario. |
|
| In definitiva un albero binario
o è vuoto (cioè senza nodi) oppure è
costituito da una coppia ordinata di alberi binari
(detti sotto-albero destro e
sotto-albero sinistro) cui è associato un
nodo detto radice. |
| Poichè qualunque nodo
di un albero binario ha al più 2 sotto
alberi è naturale rappresentare gli alberi in memoria con
liste a doppia concatenazione. Ciascun nodo
conterrà un link al sotto-albero sinistro e un link al sotto-albero destro.
|
| Ovviamente vi è almeno un terzo campo per rappresentare la
chiave associata al nodo; ad esempio: |
|
Type
Chiave= Word; (*Generico tipo "T"*)
Albero= ^Nodo;
Nodo= Record
Sinistro: Albero;(*Puntatore
sotto-albero sinistro*)
Key: Chiave;
(*Chiave*)
Destro: Albero;
(*Puntatore sotto-albero destro*)
End; |
| Un classico problema connesso alla gestione di un
Albero Binario è quello della
visita, che consiste nel visitare una sola volta
tutti i suoi nodi, intendendo per visita l’accesso all’informazione associata
a quel nodo per un qualsiasi scopo (ricerca, modifica, stampa ecc.). |
©
2001-2010 - Studio Tecnico
ing. Giorgio OBER
Tutti i diritti sono riservati
|
