FP Laboratory 11/cs

Binární stromy

• Implementujte datový typ Tree, který definuje binární strom, ....

data Tree a = Leaf a 
            | Branch a (Tree a) (Tree a) deriving (Show)

• Připravte si přiklad binárního stromu.

testTree1 :: Tree Int            
testTree1 = Branch 12 (Branch 23 (Leaf 34) (Leaf 45)) (Leaf 55)

testTree2 :: Tree Char            
testTree2 = Branch 'a' (Branch 'b' (Leaf 'c') (Leaf 'd')) (Leaf 'e')

• Implementujte funkci, která sečte všechny hodnoty uložené ve stromu.

sum' :: Tree Int -> Int

sum' :: Tree Int -> Int
sum' (Leaf x) = x
sum' (Branch x l r) = sum' l + x + sum' r

• Implementujte funkci, extrahuje všechny hodnoty ze stromu do seznamu.

toList :: Tree a -> [a]

toList :: Tree a -> [a]
toList (Leaf x) = [x]
toList (Branch x l r) = toList l ++ [x] ++ toList r

• Jedna z možností, jak zapsat strom v textové formě je a(b(d,e),c(e,f(g,h))). Implementujte funkci, která umožní strom načíst a ukládat v takové notaci.

toString :: Show a => Tree a -> String
fromString :: Read a => String -> Tree a

toString :: Show a => Tree a -> String
toString (Leaf x) = show x
toString (Branch x l r) = show x ++ "(" ++ (toString l) ++ "," ++ (toString r) ++ ")"

fromString :: Read a => String -> Tree a
fromString inp = fst (fromString' inp) where
  fromString' :: Read a => String -> (Tree a,String)
  fromString' inp = 
    let
      before = takeWhile (\x ->  x /='(' &&  x /=',' &&  x/=')') inp 
      after = dropWhile (\x ->  x /='(' &&  x /=',' && x/=')') inp
      value = read before
    in if null after || head after /= '(' then (Leaf value, after) else 
        let
          (l,after') = fromString' (tail after)
          (r,after'') = fromString' (tail after') 
        in (Branch value l r, tail after'')