Gli alberi strutture Dati Astratte alberi Generali



Scaricare 166.93 Kb.
Pagina1/3
17.11.2017
Dimensione del file166.93 Kb.
  1   2   3



Gli alberi


Indice dei Capitoli


  1. Gli alberi ……………….………………………………… 3

3.1 Strutture Dati Astratte ………………………………………… 3

3.2 Alberi Generali ……………………………………………..…..….. 4

3.3 Memorizzazione di alberi generali: array di puntatori ..…….….. 5

3.4 Alberi Binari …………………………….…………………..…... 11

3.5 Un esempio: altezza di un nodo ………………………..…...….. 13

3.6 Alberi generali rappresentati mediante alberi binari …………. 15

3.7 Lettura di un albero da file ……………………………..…..….. 18
Indice delle Procedure e dei Programmi
Proc. 1 – Lettura in preordine di un albero memorizzato come array di puntatori ……… 8

Proc. 2 – Lettura in preordine di un albero binario …………………………………….. 12

Proc. 3 – Valutazione di un’espressione aritmetica rappresentata come albero binario … 13

Proc. 4 – Altezza di un nodo in un albero binario (versione 1) …………………………. 14

Proc. 5 – Altezza di un nodo in un albero binario (versione 2) …………………………. 14

Proc. 6 – Altezza di un nodo in un albero generale memorizzato come array di puntatori 15

Proc. 7 – Altezza di un nodo in un albero generale memorizzato come albero binario … 18
Programma 1 – Lettura di un albero da un file ………….. ……………………………… 21
Indice dei riferimenti tematici
Lo heap ………………………………………………………………………………… 6

I tipi enumerati …………………………………………………………………….….. 20



3. Gli alberi

3.1 Strutture Dati Astratte
Il concetto di Struttura Dati Astratta è tra quelli fondamentali dell’informatica. L’idea è quella che è possibile definire in modo Astratto la struttura, e cioè senza specificare come essa è realizzata nell’implementazione. Sulla base di tale definizione sarà poi possibile individuare alcune operazioni che hanno senso sulla struttura astratta1. Date queste operazioni (e quindi il loro effetto previsto sulla struttura, cioè quella che viene detta la loro semantica, cioè il loro significato) sarà poi necessario scrivere un algoritmo che ne permetta la realizzazione. A questo punto si può cominciare a pensare alla realizzazione pratica: si dovrà scegliere un particolare linguaggio di programmazione (Pascal, C, ecc.); poi, si dovrà scegliere tra le particolari strutture dati concrete che il linguaggio mette a disposizione quella che sembra più adatta per la realizzazione dell’algoritmo; infine, si potrà passare a scrivere il programma, e cioè a tradurre l’algoritmo nel linguaggio scelto.
E’ abbastanza ovvio che questa è una visione ipotetica: nella maggior parte dei casi, la scelta del linguaggio non è permessa: voi dovrete comunque realizzare gli algoritmi in Pascal, e, nella maggior parte degli ambienti industriali il linguaggio in cui realizzare il programma è fissato a priori. Ciononostante, la successione non cambia; semplicemente, si salta un passaggio:

  1. Definisci le operazioni sulla struttura

  2. Inventa gli algoritmi per effettuare (in modo astratto) tali operazioni

  3. [Scegli il linguaggio: passo spesso ‘saltato’]

  4. Scegli la struttura dati concreta

  5. Scrivi i programmi

Poiché quanto detto sembra un pò generico, si può osservare che, nei capitoli precedenti, abbiamo già utilizzato delle Strutture Dati di questo tipo. Nel primo capitolo, la Struttura Dati Astratta Sequenza è stata prima realizzata con i vettori e poi con le liste. Per le Sequenze, abbiamo visto che hanno senso operazioni come



  • Ricerca di un elemento

  • Cancellazione di un elemento

  • Inserimento di un nuovo elemento

  • Modifica di un elemento

  • Ordinamento della sequenza

In realtà, per motivi espositivi, io mi sono concentrato su un’unica operazione: l’ordinamento (che è anche la più difficile). Una volta fatto questo (Passo 1), abbiamo cominciato a pensare ai metodi (algoritmi) possibili per realizzare l’operazione ed abbiamo ‘inventato’ (si fa per dire) il Selection Sort (Passo 2). Abbiamo poi ovviamente saltato il Passo 3 (il linguaggio è, per forza, Pascal) e siamo passati al passo 4. Qui, abbiamo scelto i vettori come struttura dati concreta (Tipo Array in Pascal) e, finalmente, abbiamo potuto scrivere il programma (Passo 5).
A questo punto, sono tornato indietro, e cioè al passo 2, cercando di vedere se non era possibile trovare dei metodi più efficienti per effettuare la stessa operazione. E’ importante notare che non siamo tornati al passo 1! L’operazione scelta al passo 1 (l’ordinamento) è esattamente la stessa! Ma il risultato del Passo 2 è cambiato: abbiamo trovato il Merge Sort, e abbiamo visto che è migliore del Selection Sort (in termini di tempo di esecuzione). Avendo rifatto il Passo 2, dobbiamo rifare anche i passi successivi: il Passo 3 (uso di Pascal) è sempre lo stesso. Il Passo 4 (scelta della struttura dati concreta) ha portato casualmente alla scelta della stessa struttura dati, e cioè i vettori (in realtà, per noi, la scelta era obbligata, visto che le liste non le conoscevamo ancora). E infine, il passo 5, cioè la scrittura del programma Merge Sort. Notate che lo stesso algoritmo, con la stessa struttura dati concreta, può comunque portare a programmi diversi, come abbiamo visto con le varie realizzazioni di Merge Sort sui vettori2.
3.2 Alberi generali
Quello che si vuole fare ora è di applicare la stessa metodologia (successione di passi) ad un struttura dati astratta un pò più complicata delle sequenze: gli alberi. La prima cosa da fare è di definire tale struttura; questo, nel caso delle sequenze, non era stato fatto: l’idea di sequenza è sufficientemente intuitiva. Nel caso degli alberi, invece, una definizione è necessaria.
Vi sono molti modi per definire gli alberi. Noi ne vedremo due. La prima è molto elegante, ma un pò difficile da comprendere se non si ha dimestichezza con definizioni ricorsive:


  • Un albero è un insieme di nodi tale che vi è un nodo speciale detto radice e tutti gli altri nodi sono partizionati in modo tale che ogni elemento della partizione è a sua volta un albero.

  • Un insieme vuoto di nodi è un albero

Gli insiemi che costituiscono la partizione dell’albero vengono detti sottoalberi dell’albero dato.


Questa definizione induce una gerarchia: la radice dell’albero è al livello più alto della gerarchia; le radici dei suoi sottoalberi sono al livello gerarchico immediatamente inferiore, e così via, ricorsivamente. Possiamo cioè definire il livello di un nodo nel modo seguente:


  • La radice dell’albero è a livello 0.

  • Se un nodo N è la radice di un sottoalbero di un albero la cui radice ha livello L, allora N ha livello L+1.

Esempio:


A1 = {n1, n2, n3, n4, n5, n6, n7, n8}

A1 è un albero se uno dei suoi nodi è ‘speciale’ (la radice) e gli altri sono partizionati in sottoalberi. Ad esempio:

A1 =

Qui abbiamo che la radice di A1 è n2, e che A1 ha cinque sottoalberi. Naturalmente, è necessario verificare che essi siano davvero, a loro volta, degli alberi. Per {n4}, {n5}, {n6} e {n8} non ci sono problemi: l’unico nodo dell’insieme è la radice, ed essa non ha sottoalberi. Per {n1, n3, n7} dobbiamo ripetere (ricorsivamente) quanto già fatto per A1. Se n3 è il nodo speciale (la radice) e gli altri due nodi sono partizionati in sottoinsiemi separati, abbiamo:



Che è necessariamente un albero, per quanto detto sopra degli insiemi di un elemento.


Come ho detto sopra, questa definizione non è molto intuitiva. Vediamone un’altra:
Un albero è una coppia , il cui primo elemento (N) è un insieme di nodi e il cui secondo elemento è una relazione binaria R NxN, tale che:

  • Esiste un nodo (chiamiamolo NR) che non compare come secondo elemento nella relazione R.

  • Tutti i nodi diversi da NR compaiono esattamente una volta come secondo elemento di R.

NR, nella definizione sopra, è la radice dell’albero, che avevamo già trovato nella prima definizione. Un esempio:


A1 = R={, , , , , , }>


A1 è un albero, la cui radice è n2.
Si deve notare che, come nella prima definizione, anche qui si ottiene una gerarchia (e la corrispondente nozione di livello). Infatti, se nx è la radice (a livello 0), tutti i nodi ny tali che <nx,ny>  R si trovano a livello 1 (esiste cioè una connessione ‘diretta’ tra la radice e tali nodi). Più in generale, se un nodo nz è a livello L, allora tutti i nodi nw tali che <nz,nw>  R sono a livello L+1.
Una rappresentazione grafica, più leggibile, è la seguente:

Fig.1 – Rappresentazione grafica di un albero



Si deve però osservare che mentre le prime due forme in cui l’albero è stato presentato “sono alberi”, secondo le definizioni, la terza è solo “un disegno di un albero”, utile per noi, ma che può corrispondere sia alla prima che alla seconda definizione, indifferentemente. Rimane comunque il fatto, fondamentale, che tutte e tre le forme si riferiscono allo stesso albero.
In tutti i casi precedenti ci siamo, comunque, riferiti ad una nozione astratta di albero (sia in modo formale, come nei primi due casi, sia in modo grafico, come nel terzo). Si è, cioè, parlato di una Struttura Dati Astratta (come era stato richiesto all’inizio). Abbiamo quindi effettuato il Passo 1. Cosa succede ora per il Passo 2? Possiamo pensare a ‘ragionevoli’ operazioni che si possono fare sugli alberi. Ad esempio, dato un nodo, elencare tutti i suoi figli. O, dato un nodo, elencare tutti i suoi discendenti (se il nodo dato è la radice, avremo un elenco di tutti i nodi dell’albero). Oppure, si può pensare di modificare l’albero: si possono aggiungere o eliminare dei nodi, e così via. Poiché le operazioni possibili sono tante, anziché elencarle tutte ora, possiamo immaginare di avere un elenco (magari parziale, come quello che ho fatto sopra) e cominciare a ragionare verso le strutture dati concrete.
Come si era visto nel caso delle sequenze, possono esserci diverse alternative. In quel caso, la struttura dati astratta Sequenza era stata realizzata con due strutture dati concrete (in alternativa): i Vettori e le Liste. La stessa cosa dobbiamo ora fare per gli alberi, ragionando sugli alberi, anzichè sulle sequenze.
3.3 Memorizzazione di alberi generali: array di puntatori
La prima cosa che si può osservare è che le frecce usate nella rappresentazione grafica dell’albero (che, si noti, corrispondono esattamente alle coppie che compongono la relazione R, nella seconda definizione data), assomigliano tanto a dei puntatori. Una prima soluzione, che salta subito agli occhi, è dunque la seguente: Realizziamo i nodi come record (come gli elementi di una lista per implementare una sequenza) e inseriamo, all’interno di essi dei puntatori ai figli. Sorge però un problema: visto che i puntatori sono più d’uno (ogni nodo può avere tanti figli), non possiamo usare un puntatore ‘semplice’, come per le sequenze. Dobbiamo perciò usare (dentro il record del nodo, per la parte relativa ai puntatori), una struttura dati complessa. Come abbiamo già visto, poichè gli elementi di questa struttura dati sono tutti dello stesso tipo (e cioè puntatori a nodi), possiamo considerarli come una sequenza di puntatori, e, come abbiamo visto, possiamo realizzarli o tramite un vettore (di puntatori) o tramite una lista (in cui la parte ‘dato’ è costituita da puntatori). Vediamo cosa succede adottando la prima soluzione.
Converrebbe ora riguardare la sezione relativa ai vantaggi e svantaggi di vettori e liste per la realizzazione delle sequenze. Lo svantaggio principale dei vettori è che (almeno in Pascal) è necessario dichiarare a priori (una volta per tutte) la dimensione del vettore. Come salta subito all’occhio, questo è un problema: nella definizione generale di albero non è posto alcun limite sul numero dei figli. Se però noi dichiariamo, ad esempio, che il nostro vettore di puntatori (ce ne è uno, ovviamente, per ciascun nodo) è di 100 elementi, allora non sarà possibile memorizzare un albero in cui un nodo abbia più di 100 figli. L’altro svantaggio (un pò meno grave) è relativo allo spreco di spazio: se io so che un nodo dell’albero ha 100 figli, e i suoi 100 figli hanno, in media 2 figli, i quali, a loro volta, non hanno figli, dovremo riservare spazio per:

100 puntatori per la radice

100*100 = 10.000 puntatori per i 100 figli

100*200 = 20.000 puntatori per i 200 nipoti (2 nipoti per ciascun figlio)

di questi 30.100 puntatori saranno usati solo 300 (100 dalla radice ai figli, 200 dai figli ai nipoti). Davvero uno spreco notevole!
Ciononostante, visto che questa è la soluzione più intuitiva (e in alcuni casi reali è anche possibile che il numero di figli abbia un range limitato), vediamo come questa si può realizzare. Innanzitutto, la dichiarazione Pascal delle strutture dati ‘concrete’ (supponiamo, nell’esempio, di aver stabilito un numero massimo di 10 figli).
const maxDaughters = 10;

type TreeNodePunt = ^TreeNode;

TreeNode = record

NodeData: TipoDato;

Daughters: array [1..MaxDaughters] of TreeNodePunt

end;
dove TipoDato è un qualsiasi tipo che descriva i dati presenti nel nodo dell’albero (ad esempio una stringa che ne costuisca l’etichetta, o un intero).


Con una memorizzazione di questo tipo, l’albero dell’esempio precedente apparirebbe come nella figura che segue (ricordiamo, si veda quanto detto per le liste, che ogni ‘rettangolo’ che compare nella figura rappresenta un nodo si riferisce a “un pò di memoria” riservata nello heap).

Fig.2 – Rappresentazione di un albero mediante array di puntatori

Notate che l’albero non è così ben allineato ‘per livelli’, come nella figura precedente. Questo l’ho fatto per una questione di spazio sulla pagina, ma è, naturalmente, irrilevante: il livello è specificato dalle relazioni tra i nodi (e quindi, nell’implementazione, dai puntatori) e non da come è fatto il disegno. Ricordate anche che i record che realizzano i nodi dell’albero sono memorizzati nello Heap, e quindi la loro posizione fisica è del tutto casuale e, di conseguenza, indipendente dalla struttura dell’albero. E’ forse il caso, qui, di ricordare cos’è lo heap.
Lo heap
Sebbene la memoria centrale venga utilizzata per svariate funzioni, a noi, in questo corso, ne interessano tre:


  • una parte della memoria è riservata per i programmi in esecuzione. Essa includerà la codifica in linguaggio macchina del programma principale e di tutte le procedure utilizzate, oltre che lo spazio dati del programma principale. Nel corso dell’esecuzione di un programma, lo spazio occupato è fisso: le istruzioni del programma principale e delle procedure sono sempre le stesse, così come le variabili (semplici o array) definite nel main.

  • la seconda parte contiene lo stack. Essa ha dimensione variabile; infatti, nel corso dell’esecuzione del programma, ogni volta che viene richiamata una procedura viene allocato un blocco (frame di attivazione) sullo stack e quando la procedura termina il blocco viene liberato (e quindi lo spazio utilizzato sullo stack diminuisce). Ricordate che questo avviene per qualsiasi procedura, non solo per quelle ricorsive. Dentro ogni blocco dello stack vi sono i parametri della procedura, l’indirizzo di ritorno e le variabili locali. Notate che, mentre per ogni variabile del main è allocato un unico spazio, per quelle delle procedure c’è uno spazio diverso ad ogni chiamata, come si vedrà meglio nel seguito di questo paragrafo.

  • La terza parte è lo heap. Heap, in inglese vuol dire ‘mucchio’. Il termine vuole dare l’idea di un insieme di celle non strutturate, cioè senza alcuna organizzazione prefissata. Dentro lo heap ci vanno i dati dinamici, e cioè i record, che possono essere ‘creati’ (mediante la new) e ‘eliminati’ (mediante la dispose) nel corso dell’esecuzione di un programma. La differenza fondamentale rispetto allo stack è che la gestione dello stack è rigida (metti in cima e togli dalla cima; infatti è una pila), e regolata dal processore (un programma non può ‘decidere’ se allocare o no un blocco all’atto della chiamata di una procedura), mentre la gestione dello stack è libera: è il programma che decide se e quante new eseguire e se fare o meno delle dispose.

Vi sono molti modi per gestire lo heap, che dipendono dalla macchina. In ogni caso, i programmi di gestione dello heap devono poter effettuare le operazioni seguenti:



  • Quando viene richiamata la new, essi devono determinare la dimensione del record che deve essere creato, in modo da sapere quanto spazio libero è necessario (e questo si determina in base alla dichiarazione del tipo). Devono cercare se nello heap c’è una sequenza di celle libere adiacenti grande a sufficienza per contenere il record. Devono ‘segnalare’ che queste celle sono ora occupate. Devono restituire al programma chiamante l’indirizzo delle prima di queste celle.

  • Quando viene chiamata la dispose, devono mettere le celle prima occupate dal record di cui si fa la dispose nello spazio libero, in modo che esso sia disponibile per successive new.

Queste operazioni sono possibili, ad esempio, mantenendo nello heap una ‘lista’ di spazi vuoti. All’atto della new si perrcorrerà la lista fino a trovare uno spazio vuoto grande a sufficienza e si riserverà lo spazio (parte di esso o tutto) per il programma chiamante. All’atto della dispose lo spazio liberato sarà rimesso nella lista degli spazi vuoti.

-----------------------

Possiamo quindi passare a vedere qualche operazione che si può effettuare sugli alberi. La cosa più naturale è la ‘lettura’ dell’albero. Notate che il termine lettura si usa di norma per indicare una elencazione dei nodi, e non per riferirsi all’introduzione dell’albero (input) da tastiera o da file. Se si osserva l’albero disegnato in precedenza, si può notare che vi sono due metodi principali per percorrere l’albero: o si scende per livelli, o si scende fino in fondo su uno dei cammini (dalla radice alla foglia più a sinistra) e poi si risale e si ridiscende per prendere la foglia successiva, e così via (questo può, ovviamente, essere fatto partendo dalla foglia più a destra, non cambia molto). Abbiamo così due metodi principali per percorrere un albero:


  • Percorrimento in ampiezza

In questo caso (lettura per livelli), si otterrà:

  • Livello 0 (radice): n2

  • Livello 1: n4, n3, n5, n6, n8

  • Livello 2: n1, n7

Per cui, la sequenza completa è: n2, n4, n3, n5, n6, n8, n1, n7

Si noti, comunque, che i figli di un nodo non si intendono ordinati tra loro, e che quindi il loro ordine è del tutto casuale (e non significativo).



  • Percorrimento in profondità

In questo caso, si otterrà:

  • Si parte dalla radice (n2)

  • Si scende sul primo figlio di n2 (n4)

  • Poiché n4 non ha figli si risale (n2)

  • Si scende sul figlio successivo di n2 (n3)

  • Si scende sul primo figlio di n3 (n1)

  • Poiché n1 non ha figli si risale (n3)

  • Si scende sul figlio successivo di n3 (n7)

  • Poiché n7 non ha figli si risale (n3)

  • Poiché tutti i figli di n3 sono stati esaminati, si risale (n2)

  • Si scende sul figlio successivo di n2 (n5)

  • Poiché n5 non ha figli si risale (n2)

  • Si scende sul figlio successivo di n2 (n6)

  • Poiché n6 non ha figli si risale (n2)

  • Si scende sul figlio successivo di n2 (n8)

  • Poiché n8 non ha figli si risale (n2)

  • Poiché tutti i figli di n2 sono stati esaminati, si risale (fine)

Sebbene questo metodo sembri molto più complicato del precedente, è in alcuni casi, di più semplice implementazione, oltre ad essere più efficiente sotto certi aspetti.

Deve essere osservato che, se si vuole usare questo tipo di percorrimento per stampare i nodi di un albero, rimangono aperte alcune possibilità di scelta. Infatti, a differenza del percorrimento in ampiezza, qui si passa sullo stesso nodo più volte. Ad esempio, si passa da n3 tre volte e da n2 ben sei volte. In teoria, la stampa dell’etichetta del nodo può essere effettuata una qualsiasi di queste volte, ma è evidente che ci sono almeno due passaggi speciali: la prima volta che si arriva ad un nodo e l’ultima volta che si passa dal nodo. Ed, in effetti, questi sono i due modi principali per elencare i nodi: nel primo caso, si parla di lettura in preordine, nel secondo caso di lettura in postordine. Nel primo caso si otterrà quindi il seguente elenco:

n2, n4, n3, n1, n7, n5, n6, n8
Mentre con la lettura in postordine otterremo:

n4, n1, n7, n3, n5, n6, n8, n2


Possiamo ora, finalmente, passare a vedere una prima procedura che opera sugli alberi. Quella che segue è la procedura per la lettura, e stampa, di un albero in preordine. La procedura utilizza ambedue le forme di ‘ripetizione’ viste fino ad ora: l’iterazione e la ricorsione. L’iterazione (un ciclo while) viene usata per esaminare tutti i figli di un nodo, e la ricorsione per scendere di livello.

procedure preorder (root: TreeNodePunt);

var i: integer;

begin


if root <> NIL

then


begin

writeln (root^.NodeData);

i := 1;

while (i <= maxDaughters) and (root^.maxDaughters[i] <> NIL) do



begin

preorder (root^.Daughters[i]);

i := i+1

end


end

end;
Proc.1 – Lettura in preordine di un albero memorizzato come array di puntatori

Per comprendere bene come questo programma funziona, e inoltre per ricordare i concetti principali dei meccanismi ricorsivi, può essere utile simulare l’esecuzione del programma su una (ideale) macchina a stack. La chiamata iniziale avverrà da un programma esterno (supponiamo sia il programma principale) che quindi includerà (tra altre) le seguenti istruzioni:
program esempioalbero ()

var radice: TreeNodePunt;

begin



leggiAlbero (radice);



preorder (radice);

end.
Supponiamo dunque che all’atto della chiamata di preorder, l’albero sia già stato letto e memorizzato nella forma che abbiamo visto sopra.


Nel momento in cui viene eseguita la chiamata a preorder, un nuovo blocco viene allocato sullo stack. Questo nuovo blocco (come tutti i blocchi associati alla procedura preorder) includerà tre elementi:

  • Il valore del parametro di input

  • L’indirizzo di ritorno

  • Una cella per la variabile locale i.

Disegnando lo stack dal basso verso l’alto, esso apparirà quindi nel seguente modo:



In cui, IndHeap(n2) è l’indirizzo (nello Heap) della cella in cui inizia il record che contiene il nodo n2,  è l’indirizzo (nello spazio istruzioni del programma principale) della istruzione che segue immediatamente il richiamo alle preorder, e la cella associata alla variabile i non ha ancora nessun valore.


A questo punto, inizia l’esecuzione del body della procedura. Poiché root non è NIL, viene eseguita la writeln. L’argomento (root) permette di identificare la posizione del nodo nello heap e la definizione di tipo permette di stabilire dove si trova nel record il campo cercato (nel nostro caso all’inizio) e di che tipo è tale campo (il dato da stampare). La writeln può quindi effettuare la stampa. Poi viene inizializzata la variabile i. Questo vuol dire scrivere nello stack, nella cella associata alla variabile i, il valore 1. Finalmente si entra nel while. Le condizioni sono verificate; infatti i vale 1 e, sempre grazie al valore di root (vedi stack) è possibile trovare il record relativo al nodo n2, e, da esso, prelevare il primo elemento (i vale sempre 1) dell’array di puntatori (che sta dentro il record) Daughters. Poiché Daughters(1) è il puntatore al nodo (nello Heap) n4, esso non è NIL e quindi si esegue il body della while. Nel body c’è subito la chiamata ricorsiva, che produce l’introduzione (sullo stack) di un nuovo blocco. Lo stack sarà dunque come segue:

Nel nuovo blocco, la variabile root contiene l’indirizzo del record relativo al nodo n4, e l’indirizzo di ritorno è diverso dal precedente, perché quando questa esecuzione della procedura preorder sarà terminata, bisognerà tornare alla stessa procedura preorder, all’interno della quale si trovava la chiamata, e non al main. Quindi  corrisponderà all’indirizzo dell’istruzione i:=i+1, e cioè l’istruzione successiva alla chiamata ricorsiva. E’ essenziale osservare che adesso, nello stack, ci sono due diverse i: quella della prima chiamata (relativa ai figli di n2, che ‘ricorda’ la posizione attuale: sul primo figlio, cioè n4) e quella della chiamata ricorsiva (relativa ai figli di n4, non ancora inizializzata).


Ora inizia l’esecuzione della preorder chiamata ricorsivamente. Root non è NIL, il dato (n4) viene stampato, i viene inizializzata a 1, e si verifica la condizione della while. Tale condizione non è soddisfatta! Infatti root^.Daughters[i] è NIL, poiché (anche se i vale 1) n4 non ha figli, e quindi anche il suo primo figlio è NIL. Il body della while non viene dunque eseguito nemmeno una volta e si esce dalla procedura. Si noti comunque, che l’esecuzione ha avuto un effetto, poiché n4 è stato stampato. Uscendo dalla procedura il blocco in cima allo stack viene disallocato, e quindi lo stack rimane come si vede sotto.


1

Poiché l’indirizzo di ritorno che compariva nel blocco superiore era , la prossima istruzione da eseguire è l’incremento di i, che quindi assumerà ora il valore 2. Terminata quindi l’esecuzione del body della while, si verificano nuovamente le condizioni. Esse sono di nuovo verificate, poiché n2 ha anche un secondo figlio; quindi si esegue nuovamente il body, e lo stack diventa:


Si noti che:



  • L’indirizzo di ritorno è sempre . Infatti, l’istruzione da eseguire dopo terminata l’esecuzione è sempre la i:=i+1 della procedura chiamante.

  • root contiene ora l’indirizzo del secondo figlio di n2, e cioè n3

  • Non c’è nessuna traccia sullo stack del fatto che sia già stato analizzato il sottoalbero di radice n4, eccetto per il fatto che il valore di i nel blocco in basso vale 2 e non 1! Questo però ci dice solo come continuare dopo, e non cosa è stato fatto prima: n4 poteva non avere figli (come nel nostro caso) o essere la radice di un sottoalbero molto complesso, ma lo stato in cui ci troviamo ora sarebbe esattamente lo stesso!

Non ripeto ora passo passo cosa succede: dovrebbe essere chiaro che, poiché n3 ha dei figli, la while viene eseguita. Questo comporta l’esecuzione della chiamata ricorsiva e l’aggiunta di un blocco sullo stack. La cosa più importante da osservare è che ora ci sono nello stack tre versioni della variabile i:



  • La prima (più in basso) ci dice che stiamo lavorando sul secondo figlio di n2 (e cioè n3).

  • La seconda (intermedia) ci dice che stiamo lavorando sul primo figlio di n3 (e cioè n1).

  • La terza (più in alto) ci dice che non abbiamo ancora cominciato a esaminare i figli di n1.

Non è un caso che siamo attualmente posizionati su un nodo al terzo livello della gerarchia (n1) e che ci siano tre blocchi sullo stack: per ciascun livello, infatti dobbiamo ricordarci a che punto siamo arrivati!

Ora, si verificherà (dopo averlo stampato) che il nodo n1 non ha figli, e quindi si risale sull’albero, il che corrisponde a togliere un blocco dallo stack, e poi si ridiscenderà si n7 (aggiunta di un blocco) e così via.



3.4 Alberi binari
In un albero binario, ogni nodo ha zero, uno, o due figli. Però, gli alberi binari non sono un caso particolare degli alberi generali che abbiamo appena visto (in cui si abbia MaxDaughters=2); infatti, essi non rispettano le definizioni precedenti. Il motivo è che negli alberi binari vengono distinti i due possibili figli in figli sinistri e figli destri. In altre parole, l’ordine dei figli è, nel caso degli alberi binari, di importanza fondamentale! Scambiare il figlio sinistro e il figlio destro in un albero binario produce due alberi diversi. Al contrario, scambiare il primo e il secondo figlio di un nodo in un albero generale non ha alcun effetto: l’albero risultante è lo stesso albero dell’albero originale (l’ordine dei figli non ha importanza). Non solo, ma anche avendo un unico figlio, è diverso il caso in cui tale figlio sia figlio sinistro dal caso in cui esso sia figlio destro.
Non c’è molto da dire sulle modalità di rappresentazione degli alberi binari, poiché la soluzione è praticamente immediata (e unica, visto che non presenta particolari inconvenienti):
type BinaryNodePointer = ^BinaryNode;

BinaryNode = record

NodeData: TreeData;

LeftD, RightD: BinaryNodePointer;

end;

Come si vede, si tratta di record che includono un campo per i dati (nome o etichetta del nodo) e due distinti puntatori: il primo al figlio sinistro (l’ho chiamato LeftD) e il secondo al figlio destro (RightD).


Possiamo subito vedere la procedura di lettura in preordine di un albero binario, che non è altro che una semplificazione di quella già vista per gli alberi generali.
L’unica differenza è che qui, anziché avere un ciclo while, con la corrispondente necessità di inizializzare e incrementare la variabile i, si hanno solamente due richiami ricorsivi in sequenza: il primo per il sottoalbero che ha come radice il figlio sinistro, il secondo per il sottoalbero che ha come radice il figlio destro. E’ chiaro che qui il ciclo non serve: si sa che i puntatori ai figli sono esattamente due (anche se uno o tutti e due potrebbero essere NIL)!

procedure BinPreorder (root: BinaryNodePointer);

begin

if root <> NIL



then

begin


writeln (root^.NodeData);

BinPreorder (root^.LeftD);

BinPreorder (root^.RightD)

end


end;
Proc.2 – Lettura in preordine di un albero binario

Gli alberi binari sono molto importanti, perché, pur avendo una struttura molto semplice, permettono di memorizzare (con una tecnica un pò particolare) anche alberi generali. Prima, però, di vedere tale tecnica, facciamo un esempio di uso di alberi binari. In particolare, gli alberi binari possono essere utilizzati per memorizzare delle espressioni aritmetiche. Vediamo quindi come questo può essere realizzato, ed una procedura per valutare l’espressione.


Nell’espressione, assumiamo che tutti gli operatori siano binari e che gli unici operatori permessi siano +, -, *, /. Nella scrittura dell’espressione, possiamo inserire tutte le parentesi, che ci consentono di ricavare in modo immediato la struttura interna dell’espressione. Ad esempio:

((3+7) – (18 * (10/5)))


In questa espressione compare un operatore principale (che è quello relativo alle parentesi più esterne, nel nostro caso -) che può avere come argomenti o dei valori interi o delle espressioni aritmetiche. Nel nostro caso, ambedue gli argomenti dell’operatore principale sono a loro volta delle espressioni: (3+7) e (18*(10/5)). Ciascun operatore può essere rappresentato come un nodo di un albero binario, i cui argomenti sono i sottoalberi sinistro e destro. Ad esempio, nel nostro caso:

Naturalmente, poiché la definizione è ricorsiva, anche i sottoalberi verranno rappresentati nello stesso modo, ottenendo così alla fine:



Si osservi che le parentesi tonde non compaiono più: esse infatti servono solo per rendere espliciti, nella rappresentazione lineare ‘standard’ dell’espressione i livelli di annidamento delle sottoespressioni; ma questo, nell’albero, è già dato esplicitamente nella struttura dell’albero stesso.


Possiamo ora pensare alla struttura (tipo Pascal) dei nodi dell’albero. Innanzitutto, poiché le foglie dell’albero hanno associati dei dati interi, mentre i nodi intermedi si riferiscono a dati di tipo char, non sarà possibile memorizzare tali informazioni nello stesso campo del record. Di conseguenza, dovremo avere due campi ‘dati’: il primo sarà di tipo integer e verrà usato quando il record contiene i dati di una foglia. Il secondo sarà di tipo char e verrà usato, nei nodi intermedi, per memorizzare l’operazione. Ora però sorge un problema: come fare a sapere di che tipo di nodo si tratta? E’, ovviamente, possibile verificare sempre se un nodo non ha figli (nel qual caso dovrà necessariamente contenere un valore, e non un operatore), ma è più semplice utilizzare lo stesso campo usato per l’operazione come indicatore di tipo di nodo; ad esempio, possiamo porre in tale campo il valore ‘v’, se il nodo contiene un valore intero (e cioè si tratta di una foglia). A questo punto, possiamo dare la definizione di tipo:

type AritmPointer = ^AritmNode;




  1   2   3


©astratto.info 2017
invia messaggio

    Pagina principale