chapter11-BinaryTree

chapter11-BinaryTree.hs

module C where

data BinaryTree a = Leaf
    | Node (BinaryTree a) a (BinaryTree a)
  deriving (Eq, Ord, Show)

insert' :: Ord a => a -> BinaryTree a -> BinaryTree a
insert' e Leaf = Node Leaf e Leaf
insert' e (Node left n right)
  | e == n = Node left e right
  | e < n = Node (insert' e left) n right
  | e > n = Node left n (insert' e right)

mapTree :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree _ Leaf = Leaf
mapTree f (Node left n right) = Node (mapTree f left) (f n) (mapTree f right)

preorder :: BinaryTree a -> [a]
preorder Leaf = []
preorder (Node left n right) = [n] ++ preorder left ++ preorder right

inorder :: BinaryTree a -> [a]
inorder Leaf = []
inorder (Node left n right) = preorder left ++ [n] ++ preorder right

postorder :: BinaryTree a -> [a]
postorder Leaf = []
postorder (Node left n right) = preorder right ++ [n] ++ preorder left

foldTree :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTree f acc = foldr f acc . inorder

t1 :: BinaryTree Integer
t1 = insert' 10 Leaf
t2 :: BinaryTree Integer
t2 = insert' 3 t1
t3 :: BinaryTree Integer
t3 = insert' 13 t2