module BTree where data BTree a = Empty | Node a (BTree a) (BTree a) deriving (Eq, Show, Read) size :: BTree a -> Integer size Empty = 0 size (Node _ l r) = size l + size r + 1 height :: BTree a -> Integer height Empty = 0 height (Node _ l r) = max (height l) (height r) + 1 fromList :: [a] -> BTree a fromList [] = Empty fromList (x:xs) = Node x Empty (fromList xs) make :: [a] -> BTree a make [] = Empty make xs = Node z (make ys) (make zs) where m = length xs `div` 2 (ys,z:zs) = splitAt m xs searchTree :: Ord a => [a] -> BTree a searchTree = foldr insert Empty where insert x Empty = Node x Empty Empty insert x (Node y l r) | x < y = Node y (insert x l) r | otherwise = Node y l (insert x r) flatten :: BTree a -> [a] flatten Empty = [] flatten (Node x l r) = flatten l ++ [x] ++ flatten r