slides

Programmazione Funzionale
Esercizi sugli alberi e liste
Davide Mottin - Themis Palpanas
May 14, 2014
1/13
Funzioni sugli alberi
Visite di alberi
Alberi ordinati
Nodi a livello n
Sommario
2/13
Per cominciare
Scaricare ed eseguire il codice presente nella pagina
http://disi.unitn.it/~mottin/funprog/tree_example.ml.
Funzioni sugli alberi
3/13
Visita in preordine
Data la definizione di albero binario:
type ’a tree = Empty | Tr of ’a
* ’a tree * ’a tree;;
costruire una funzione preorder : ’a tree -> ’a list che
preso un albero restituisca la lista degli elementi leggendo prima la
radice, poi il figlio sinistro e infine il figlio destro.
Funzioni sugli alberi
4/13
Visita in preordine - Soluzione
l e t rec p r e o r d e r = f u n c t i o n
Empty −> [ ]
| Tr ( x , l , r ) −>
x : : ( preorder l @ preorder r ) ; ;
E se volessimo visitare prima il figlio sinistro poi la radice e poi il
figlio destro?
Funzioni sugli alberi
5/13
Visita simmetrica - Soluzione
l e t rec i n o r d e r = f u n c t i o n
Empty −> [ ]
| Tr ( x , l , r ) −>
( inorder l ) @ (x : : ( inorder r ) ) ; ;
Funzioni sugli alberi
6/13
Alberi ordinati
Costruire una funzione ordered elements : ’a tree -> ’a
list che preso un albero restituisca la lista degli elementi in
preordine dove un sottoalbero viene visitato solamente se
l’etichetta `e minore di quella del padre.
Funzioni sugli alberi
7/13
Alberi ordinati - Soluzione
let ordered elements = function
Empty −> [ ]
| Tr ( x , l , r ) −>
l e t r e c aux f l a b = f u n c t i o n
Empty −> [ ]
| Tr ( x , l , r ) −>
i f ( x < f l a b ) then
x : : ( aux x l @ aux x r )
else []
i n x : : ( aux x l @ aux x r ) ; ;
Funzioni sugli alberi
8/13
Nodi di un albero a livello n
Data la definizione di albero binario:
type ’a tree = Empty | Tr of ’a
* ’a tree * ’a tree;;
costruire una funzione get level : int -> ’a tree -> ’a
list che preso in input un intero n e un albero restituisca la lista
di tutti gli elementi dello stesso presenti a livello n.
Esempio
let tr = Tr(3,Tr(5,Tr(2,Empty,Empty),Tr(1,Empty,Empty)),
Tr(3,Empty,Empty));;
get_level 3 tr = [2;1];;
Funzioni sugli alberi
9/13
Nodi di un albero a livello n - Soluzione
let get level n tr =
l e t r e c aux c = f u n c t i o n
Empty −> [ ]
| Tr ( x , l , r ) −>
l e t l s t = ( aux ( c +1) l )@( aux ( c +1) r ) i n
i f c = n then x : : l s t e l s e l s t
i n aux 1 t r ; ;
Funzioni sugli alberi
10/13
Elementi per livello
Costruire una funzione all levels che restituisce una lista di liste
con tutti gli elementi per ogni livello.
Esempio
all_levels tr = [[3]; [5; 3]; [2; 1]]
Suggerimento
Usare la funzione get level per ottenere la lista dei nodi a livello
n.
Funzioni sugli alberi
11/13
Elementi per livello - Soluzione
l e t rec h e i g h t = f u n c t i o n
Empty −> 0
| Tr ( , l , r ) −> 1 + max ( h e i g h t l ) ( h e i g h t r ) ; ;
let a l l l e v e l s tr =
l e t r e c aux a c c = f u n c t i o n
0 −> a c c
| n −> aux ( ( g e t l e v e l n t r ) : : a c c ) ( n−1)
i n aux [ ] ( h e i g h t t r ) ; ;
E se volessimo costruire una funzione di visita in ampienza? (La
visita in ampiezza prevede che i nodi vengano visitati livello per
livello)
Funzioni sugli alberi
12/13
Visita in ampiezza - Soluzione
let bfs tr =
l e t r e c aux a c c = f u n c t i o n
0 −> a c c
| n −> aux ( ( g e t l e v e l n t r ) @acc ) ( n−1)
i n aux [ ] ( h e i g h t t r ) ; ;
Funzioni sugli alberi
13/13

Download Report