Árbol Binario de búsqueda en Haskell. Operaciones: crea un árbol a partir de una lista, inserta nodos a un árbol, búsqueda de un nodo, mostrar número de nodos, mostrar número de hojas, mostrar altura del árbol y recorridos preorden, inorden y postorden.

abbHaskell.hs

-- Estructura del árbol
data Abb a = Vacio | Nodo a (Abb a) (Abb a) deriving (Show)

-- Insertar un nuevo nodo a un árbol definido
-- insertarNodo (Valor a insertar) (Árbol)
insertarNodo :: (Ord a) => a -> Abb a -> Abb a
insertarNodo nuevo Vacio = Nodo nuevo Vacio Vacio
insertarNodo nuevo (Nodo a izq der)
 | nuevo <= a = Nodo a (insertarNodo nuevo izq) der
 | nuevo > a = Nodo a izq (insertarNodo nuevo der)

-- Devuelve True o False si el nodo se halla en el árbol
-- BuscarNodo (Valor a buscar) (Árbol)
buscarNodo :: (Ord a) => a -> Abb a -> Bool
buscarNodo buscado Vacio = False
buscarNodo buscado (Nodo a izq der)
 | buscado == a = True
 | buscado < a = buscarNodo buscado izq
 | otherwise = buscarNodo buscado der

-- Crea un nuevo árbol a partir de una lista
-- crearDeLista (Lista de números)
crearDeLista :: (Ord a) => [a] -> Abb a
crearDeLista [] = Vacio
crearDeLista (raiz:sub) = Nodo raiz (crearDeLista (filter (<= raiz) sub)) (crearDeLista (filter (> raiz) sub))

-- Devuelve el número de elementos en el árbol
-- numeroNodos (Árbol)
numeroNodos :: (Num a) => Abb t -> a
numeroNodos Vacio = 0
numeroNodos (Nodo _ izq der) = 1 + numeroNodos izq + numeroNodos der

-- Devuelve el número de hojas (nodos sin hijos) del árbol
-- numeroHojas (Árbol)
numeroHojas :: (Ord a) => Abb a -> Int
numeroHojas Vacio = 0
numeroHojas (Nodo actual Vacio Vacio) = 1
numeroHojas (Nodo actual izq der) = numeroHojas izq + numeroHojas der

-- Devuelve la altura del árbol (número de niveles desde la raíz a la hoja más baja)
-- alturaArbol (Árbol)
alturaArbol :: (Ord a) => Abb a -> Int
alturaArbol Vacio = 0
alturaArbol (Nodo _ izq der) = 1 + max (alturaArbol izq) (alturaArbol der)

-- Devuelve una lista de los nodos en recorrido preorden (raíz, izquierda, derecha)
-- preorden (Árbol)
preorden :: (Ord a) => Abb a -> [a]
preorden Vacio = []
preorden (Nodo actual izq der) = [actual] ++ preorden izq ++ preorden der

-- Devuelve una lista de los nodos en recorrido inorden (izquierda, raíz, derecha)
-- inorden (Árbol)
inorden :: (Ord a) => Abb a -> [a]
inorden Vacio = []
inorden (Nodo actual izq der) = inorden izq ++ [actual] ++ inorden der

-- Devuelve una lista de los nodos en recorrido postorden (izquierda, derecha, raíz)
-- postorden (Árbol)
postorden :: (Ord a) => Abb a -> [a]
postorden Vacio = []
postorden (Nodo actual izq der) = postorden izq ++ postorden der ++ [actual]

hola que tal, soy inexperto en haskell y me gustaría saber como haces que funcione o si puedes poner un ejemplo usando tu código e imprimiendo un árbol ya que lo intente pero no pude, saludos :)

@mixtor123 Hola. Para ejecutar el código sólo debes descargar el archivo o copiar y pegar el contenido en un archivo .hs y abrirlo con el GHCi que normalmente se instala con Haskell. La expresión crearDeLista es la única que al parecer no funciona muy bien pues únicamente crea un árbol donde todos los elementos se convierten en el hijo derecho del anterior. Por ejemplo:

*Main> let arbol1 = crearDeLista [1, 5, 8, 6]
*Main> arbol1
Nodo 1 Vacio (Nodo 5 Vacio (Nodo 8 (Nodo 6 Vacio Vacio) Vacio))

Como ves no es muy útil...

En la línea 2 se muestra la estructura de un árbol, que es (Nodo padre) (Hijos Izquierdos) (Hijos derechos), donde los hijos es otro árbol que a la vez puede ser vacío.

Por poner un ejemplo, éste árbol se puede representar así:

Nodo 104 (Nodo 71 (Nodo 17 (Nodo 3 Vacio Vacio) (Nodo 18 Vacio Vacio)) (Nodo 19 Vacio Vacio)) (Nodo 240 (Nodo 108 Vacio (Nodo 110 Vacio Vacio)) (Nodo 245 Vacio Vacio))

Entonces las operaciones las puedes ejecutar desde el GHCi de la siguiente manera:

*Main> let arbol2 = Nodo 104 (Nodo 71 (Nodo 17 (Nodo 3 Vacio Vacio) (Nodo 18 Vacio Vacio)) (Nodo 19 Vacio Vacio)) (Nodo 240 (Nodo 108 Vacio (Nodo 110 Vacio Vacio)) (Nodo 245 Vacio Vacio))
*Main> buscarNodo 240 arbol2
True
*Main> numeroNodos arbol2
10
*Main> numeroHojas arbol2
5
*Main> alturaArbol arbol2
4
*Main> preorden arbol2
[104,71,17,3,18,19,240,108,110,245]
*Main> inorden arbol2
[3,17,18,71,19,104,108,110,240,245]
*Main> postorden arbol2
[3,18,17,19,71,110,108,245,240,104]

No soy un experto en Haskell, y de hecho esta es una recopilación de formas de hacer las operaciones que me fui encontrando por Internet. Ya no recuerdo cómo funciona y realmente nunca lo aprendí bien, fue sólo para pasar una asignación en la universidad 🙃 pero espero sea de ayuda. Saludos.

Muchas gracias, tu ejemplo me fue de mucha ayuda!