Last active
June 5, 2024 22:29
-
-
Save anscharivs/d09357dd8688211a4d852e500fd697b9 to your computer and use it in GitHub Desktop.
Á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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- 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] |
Muchas gracias, tu ejemplo me fue de mucha ayuda!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@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: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í:
Entonces las operaciones las puedes ejecutar desde el GHCi de la siguiente manera:
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.