module Trees

where 
import List
import Char

data BinTree = L 
             | N BinTree BinTree
     deriving Show

example1 :: BinTree
example1 = (N (N (N L (N L L)) L) (N (N L L) L))

count :: BinTree -> Int
count L = 1 
count (N t1 t2) = 1 + count t1 + count t2

depth :: BinTree -> Int 
depth L = 0 
depth (N t1 t2) = 1 + max (depth t1) (depth t2) 

data Bleaftree a 
  = Leaf a 
  | Branch (Bleaftree a) (Bleaftree a)
  deriving (Eq,Ord,Show) 

example2 = Branch 
             (Leaf "Jan")
             (Branch (Leaf "kuste")
                     (Leaf "Heleen"))

count2 :: Bleaftree a -> Int
count2 (Leaf _) = 0 
count2 (Branch t1 t2) = 1 + count2 t1 + count2 t2

depth2 :: Bleaftree a -> Int
depth2 (Leaf _) = 0
depth2 (Branch t1 t2) = 
     1 + max (depth2 t1) (depth2 t2)

collect :: Bleaftree a -> [a]
collect (Leaf x) = [x]
collect (Branch t1 t2) = collect t1 ++ collect t2

mapT :: (a -> b) -> Bleaftree a -> Bleaftree b 
mapT f (Leaf x) = Leaf (f x)
mapT f (Branch t1 t2) = 
   Branch (mapT f t1) (mapT f t2) 

data Btree a b = Lf a b 
               | Br a (Btree a b) (Btree a b) 
  deriving (Eq,Ord,Show)

example3 = Br "S" 
             (Lf "NP" "Jan")
             (Br "VP" (Lf "V" "kuste")
                      (Lf "NP" "Heleen"))

data Rose a = Bud a 
            | RBr [Rose a]
     deriving (Eq,Ord,Show) 

rose = RBr [Bud 1, 
            RBr [Bud 2, 
                 Bud 3, 
                 RBr [Bud 4, Bud 5, Bud 6]]]

data Pal = Empty | A | B | PA Pal | PB Pal

instance Show Pal where 
 show Empty = ""
 show A     = "a"
 show B     = "b"
 show (PA pal) = "a" ++ show pal ++ "a"
 show (PB pal) = "b" ++ show pal ++ "b"