LP Haskell Arbre Binari de Cerca (2014)

Apunte Catalán
Universidad Universidad Politécnica de Cataluña (UPC)
Grado Ingeniería Informática - 3º curso
Asignatura LP (Llenguatges de Programació)
Año del apunte 2014
Páginas 2
Fecha de subida 26/06/2014
Descargas 3

Descripción

Implementació de un Arbre binari de Cèrca i algunes funcions útils en Haskell
(Llenguatges de Programació) LP

Vista previa del texto

{- Funcions a implementar size t1 height t1 equal t2 t3 isomorphic t1 t1' preOrder t1 postOrder t1 inOrder t1 - } data Tree a = Node a (Tree a) (Tree a) |Empty deriving(Show) size Empty = 0 size (Node a t1 t2) = 1 + s1 + s2 where { s1 = size t1; s2 = size t2 } height Empty = 0 height (Node a t1 t2) = 1 + max s1 s2 where s1 = size t1 s2 = size t2 equal Empty Empty = True equal Empty t = False equal t Empty = False equal (Node a at1 at2) (Node b bt1 bt2) = equal at1 bt1 && equal at2 bt2 && a == b isomorphic Empty Empty = True isomorphic Empty t = False isomorphic t Empty = False isomorphic (Node a at1 at2) (Node b bt1 bt2) = a == b && ((isomorphic at1 bt1 && isomorphic at2 bt2) || (isomorphic at1 bt2 && isomorphic at2 bt1)) preOrder Empty = [] preOrder (Node a at1 at2) = aux (Node a at1 at2) [] aux Empty l = l aux (Node a at1 at2) l = a:(aux at1 lf) where lf = aux at2 l postOrder Empty = [] postOrder (Node a at1 at2) = (postOrder at1) ++ (postOrder at2) ++ (a:[]) inOrder Empty = [] inOrder (Node a at1 at2) = (inOrder at1) ++ (a:[]) ++ (inOrder at2) breadthFirst Empty = [] breadthFirst (Node a at1 at2) = a:(fun [] (at1:at2:[])) fun l [] = l fun l (Empty:lt) = l fun l ((Node a at1 at2):lt) = a:(fun l (lt ++ ( [at1 , at2]))) build [] [] = Empty t7 = Node 7 Empty Empty t6 = Node 6 Empty Empty t5 = Node 5 Empty Empty t4 = Node 4 Empty Empty t3 = Node 3 t6 t7 t2 = Node 2 t4 t5 t1 = Node 1 t2 t3 t1' = Node 1 t3 t2 ...