Beispielcode (Übungen

data Tree k
     = Branch { left :: Tree k, key :: k, right :: Tree k }
     | Leaf   { }
  deriving Show

-- | vollständiger binärer Baum der Höhe h
full :: Integer -> Tree Integer
full h =
     if h > 0
     then Branch { left = full (h-1), key = h, right = full (h-1) }
     else Leaf {}

-- | Fibonacci-Baum
fib :: Integer -> Tree Integer
fib h =
     case h > 0 of
       True  -> Branch { left = fib (h-1), key = h, right = fib (h-2) }
       False ->  Leaf {}

-- | Anzahl der Branch-Konstruktoren im Baum
branches :: Tree k -> Integer
branches t = case t of
    Leaf {} -> 0
    Branch {} -> branches (left t) + 1 + branches (right t)

-- | Inorder-Liste der Schlüssel
inorder :: Tree k -> [ k ]
inorder t = case t of
    Leaf {} -> []
    Branch {} -> inorder (left t) ++ [key t] ++ inorder (right t)

-- | Hausaufgabe 1:
-- Einfügen eines Schlüssels in einen (unbalancierten) Suchbaum
insert :: Ord k => Tree k -> k -> Tree k
insert t k =  ... key t < k ...

-- | Hausaufgabe 2:
-- Herstellen eines (unbalancierten) Suchbaums aus einer Liste von Schlüsseln
fromList :: Ord k => [ k ] -> Tree k
fromList l = case l of
   x : xs -> ...
   []     -> ...

-- | Hausaufgabe 3:
-- vergleiche Leistung dieser beiden Funktionen:
sort1, sort2 :: Ord k => [k] -> [k]
sort1 = inorder . fromList
sort2 = Data.Set.toAscList . Data.Set.fromList