Dddd

´ Cap´ ıtulo 9. Programaci´n con Arboles o

107

´ Arboles ´ Arboles generales
Un ´rbol es una estructura no lineal ac´ a ıclica utilizada para organizar informaci´n de forma eficiente. o La definici´n es recursiva: o Un ´rbol es una colecci´n de valores {v1 , v2, . . . vn} tales que a o Si n = 0 el ´rbol se dice vac´ a ıo. En otro caso, existe un valor destacado que se denomina ra´ (p.e. v1), y los dem´s elementos forman ız a parte de colecciones disjuntas que a su vez son ´rboles. Estos ´rboles se llaman sub´rboles del ra´ a a a ız.
§ ¦

10 ¥ 35 52 33

¤

§ C ¤ § c ¤ §j ¤ ¦ ¥¦ ¥ ¦ ¥

22

§ § ¤ x ¦ ¥ ¦

15 12 ¥

¤

§ c¤ ¦ ¥

´ Cap´ ıtulo 9. Programaci´n con Arboles o

108

Representaci´n en Haskell o
§

10 ¦ ¥
§ C ¤ § c ¤ §j ¤ ¦ ¥¦ ¥ ¦ ¥

¤

22

3552 33

§ § ¤ x ¦ ¥ ¦

15 12 ¥

¤

§ c¤ ¦ ¥

data ´ Arbol a = Vac´ | Nodo ıo Show

a
ra´ ız

´ [Arbol a] deriving
hijos

´ a1 :: Arbol Integer a1 = Nodo 10 [a11, a12, a13] where a11 = Nodo 22 [hoja 15, hoja 12] a12 = hoja 35 a13 = Nodo 52 [hoja 33] profundidad profundidad Vac´ ıo profundidad (Nodo profundidad (Nodo

´ hoja :: a → Arbol a hoja x = Nodo x [ ] ´ ra´ ız :: Arbola → a ra´ Vac´ ız ıo = error ”ra´z de ´rbol vac´o” ı a ı ra´ (Nodo x ) ız =x ´ tama˜ o n :: Arbol a → Integer tama˜ o Vac´ n ıo =0 = (+1) . sum . map tama˜ o $ xs n tama˜ o (Nodo xs) n

[ ]) xs)

´ :: Arbol a → Integer =0 =1 = (+1) . maximum . map profundidad $ xs

´ Cap´ ıtulo 9. Programaci´n con Arboles o

109

´ Arboles binarios
Un ´rbol binario es ´rbol tal que cada nodo tienecomo m´ximo dos sub´rboles. a a a a
§ ¦ ¥ § )¤ ” § ¤ ¦ ¥¦ ¥ § § ¤” ¤ § )¤ ” ¦ ¥¦ ¥ ¦ ¥

10

¤

15

18

24

27 24

´ data ArbolB a = Vac´ ıoB ´ | NodoB (ArbolB a)
sub izq

a
ra´ ız

´ (ArbolB a) deriving Show
sub der

Consideraremos que las tres componentes del constructor NodoB son el sub´rbol izquierdo, el dato ra´ a ız y el sub´rbol derecho respectivamente. a Si falta unsub´rbol, se usa Vac´ . a ıoB
´ a2 :: ArbolB Integer a2 = NodoB aI 10 aD where aI = NodoB aII 15 aID aD = NodoB aDI 18 aDD aII = hojaB 24 aID = hojaB 27 aDI = Vac´ ıoB aDD = hojaB 24 ´ hojaB :: a → ArbolB a hojaB x = NodoB Vac´ ıoB x Vac´ ıoB

´ Cap´ ıtulo 9. Programaci´n con Arboles o

110

´ Arboles binarios (II)
´ ra´ ızB :: ArbolB a → a ra´ Vac´ ızB ıoB =error ”ra´z de´rbol vac´o” ı a ıra´ (NodoB x ) =x ızB ´ tama˜ oB n :: ArbolB a → Integer tama˜ oB Vac´ n ıoB =0 tama˜ oB (NodoB i r d ) =1 + tama˜ oB i + tama˜ oB d n n n ´ profundidadB :: ArbolB a → Integer profundidadB Vac´ ıoB =0 profundidadB (NodoB i r d ) =1 + max (profundidadB i ) (profundidadB d )

EJERCICIO: Define funciones para Comprobar si un dato pertenece a un ´rbol. a Contar cu´ntas veces aparece un dato en un´rbol. a a Sumar todos los nodos de un ´rbol de n´meros. a u Calcular el valor m´ximo almacenado en un ´rbol. a a Da versiones para ´rboles binarios y generales. a

´ Cap´ ıtulo 9. Programaci´n con Arboles o

111

Recorrido de ´rboles binarios a
´ enOrdenB :: ArbolB a → [a] enOrdenB Vac´ ıoB =[ ] enOrdenB (NodoB i r d ) =enOrdenB i + (r : enOrdenB d ) + ´ preOrdenB :: ArbolB a → [a] preOrdenBVac´ ıoB =[ ] preOrdenB (NodoB i r d ) =(r : preOrdenB i ) + preOrdenB d + ´ postOrdenB :: ArbolB a → [a] postOrdenB Vac´ ıoB =[ ] postOrdenB (NodoB i r d ) =postOrdenB i + postOrdenB d + [r ] + + Main> enOrdenB a2 [24, 15, 27, 10, 18, 24] :: [Integer ] Main> preOrdenB a2 [10, 15, 24, 27, 18, 24] :: [Integer ] Main> postOrdenB a2 [24, 27, 15, 24, 18, 10] :: [Integer ]

EJERCICIO: Define losrecorridos en pre-orden y post-orden para ´rboles generales. a

´ Cap´ ıtulo 9. Programaci´n con Arboles o

112

La funci´n fmap o
La funci´n map solo est´ predefinida para listas, pero existe una versi´n sobrecargada predefinida en la o a o siguiente clase:
class Functor m where fmap :: (a → b) → m a → m b

Por ejemplo, las listas son una instancia predefinida de esta clase:
instance...