btree.hs

module BinaryTree where 
import Data.Maybe(fromJust)
data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Show, Eq) 

isNode (Node _ _ _) = True
isNode _ = False

isLeaf (Leaf _) = True
isLeaf _ = False


getLeft :: Tree a -> Tree a
getLeft leaf@(Leaf _) = leaf
getLeft (Node _ left _) = left

getRight :: Tree a -> Tree a
getRight leaf@(Leaf _) = leaf
getRight (Node _ _ right) = right

getValue :: Tree a -> a
getValue (Leaf val) = val
getValue (Node value _ _) = value


hasValue :: (Ord a) => Tree a -> a -> Bool
hasValue (Leaf l_value) value = value == l_value
hasValue (Node n_value left right) value = if (value == n_value) then True else
                                 if (value < n_value) then (hasValue left value) else hasValue right value
farLeft :: Tree a -> Tree a
farLeft (Leaf x) = Leaf x
farLeft (Node _ left _) = farLeft left


farRight :: Tree a -> Tree a
farRight leaf@(Leaf x) = leaf
farRight (Node _ _ right) = farRight right

treeReverse :: Tree a -> Tree a
treeReverse leaf@(Leaf _) = leaf
treeReverse (Node val left right) = Node val (treeReverse right) (treeReverse left)

treeMap :: (a -> b) -> Tree a -> Tree b
treeMap func (Leaf value)            = Leaf $ func value
treeMap func (Node value left right) = Node (func value) (treeMap func left) (treeMap func right)

treeToInfixList :: Tree a -> [a]
treeToInfixList (Leaf value)            = [value]
treeToInfixList (Node value left right) = (treeToInfixList left) ++ [value] ++ (treeToInfixList right)

treePrintInfix :: (Show a) => Tree a -> IO()
treePrintInfix (Leaf value) = putStr ((show value) ++ " ")
treePrintInfix (Node value left right) = (treePrintInfix left) >>
                                         (putStr ((show value) ++ " ")) >>
                                         treePrintInfix right >>
                                         putStr "\n"

{-treeFilter :: (a -> Bool) -> Tree a -> Maybe (Tree a)
treeFilter func (Leaf value)            = func value
treeFilter func node@(Node value left right) = something
                                          where left_tree = if func value then Node value (treeFiter func left) else 2-}


treeIsSorted :: (Ord a) => Tree a -> Bool
treeIsSorted (Leaf value) = True
treeIsSorted (Node value left right) =  
                                       ((treeIsSorted left) && (treeIsSorted right) && (value >= left_value) && (value <= right_value))
                                       where left_value  = getValue left
                                             right_value = getValue right

a_tree = Node 100 (Node 7 (Leaf 5) (Leaf 10)) (Node 107 (Leaf 105) (Leaf 110))