-
-
Save hardentoo/21d47c058c3e29194eb8e57b852bd966 to your computer and use it in GitHub Desktop.
Haskell BTree
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
module BinaryTree | |
where | |
-- Haskell Binary Tree Examples | |
-- A binary tree can either be empty or a node with a left and right branch | |
data Tree a = EmptyTree | Node a (Tree a) (Tree a) | |
deriving ( Show, Read, Eq ) | |
singleton :: a -> Tree a | |
singleton x = Node x EmptyTree EmptyTree | |
insert :: (Ord a) => a -> Tree a -> Tree a | |
insert x EmptyTree = singleton x | |
insert x (Node a left right) | |
| x == a = Node x left right | |
| x < a = Node a (insert x left) right | |
| x > a = Node a left (insert x right) | |
treeElem :: (Ord a) => a -> Tree a -> Bool | |
treeElem x EmptyTree = False | |
treeElem x (Node a left right) | |
| x == a = True | |
| x < a = treeElem x left | |
| x > a = treeElem x right | |
-- (a -> b) -> Tree a -> Tree b | |
instance Functor Tree where | |
fmap f EmptyTree = EmptyTree | |
fmap f (Node x leftsub rightsub) = Node (f x) (fmap f leftsub) (fmap f rightsub) | |
-- Helper function to make a binary tree structure | |
makeTree :: (Ord a) => [a] -> Tree a | |
makeTree xs = foldr insert EmptyTree xs | |
-- tree size $ makeTree [1,2,3] The number of elements in the binary tree | |
treeSize :: Num a => Tree t -> a | |
treeSize EmptyTree = 0 | |
treeSize (Node _ left right) = 1 + treeSize left + treeSize right | |
-- In a binary tree the smallest item is the item furthest left | |
minTreeValue :: Tree t -> t | |
minTreeValue (Node x EmptyTree _) = x | |
minTreeValue (Node x leftBranch _) = minTreeValue leftBranch | |
-- In a binary tree the largest item is the item furthest right | |
maxTreeValue :: Tree t -> t | |
maxTreeValue (Node x _ EmptyTree) = x | |
maxTreeValue (Node x _ rightBranch) = maxTreeValue rightBranch | |
-- Returns the sum of all items in a numerical binary tree | |
treeSum :: Num a => Tree a -> a | |
treeSum EmptyTree = 0 | |
treeSum (Node x left right) = x + (treeSum left) + (treeSum right) | |
-- A function that returns the product of all values in the tree | |
treeToList :: Tree a -> [a] | |
treeToList EmptyTree = [] | |
treeToList (Node x leftBranch rightBranch) = x : a ++ b | |
where a = (treeToList leftBranch) | |
b = (treeToList rightBranch) | |
treeProduct :: Num a => Tree a -> a | |
treeProduct EmptyTree = 0 | |
treeProduct (Node x left right) = foldr (*) 1 $ treeToList (Node x left right) | |
-- Returns the height of a binary tree | |
treeHeight :: Tree a -> Int | |
treeHeight EmptyTree = 0 | |
treeHeight (Node _ leftBranch rightBranch) = 1 + max (treeHeight leftBranch) (treeHeight rightBranch) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment