Suchbäume

• deklariere Datentyp für binäre Bäume mit Schlüsseln vom Typ a:

  data Tree a = Leaf 
              | Node { key :: a
                     , left :: Tree a
                     , right :: Tree a
                     }
      deriving Show  
          -- entspr. automatischer Deklaration
          -- der Java-Methode toString
  t :: Tree Int
  t = Node { key = 5
           , left = Node { key = 3, left = Leaf, right = Leaf }
           , right = Leaf 
           }
  

• Zähle Blätter in einem Baum:

  leaves :: Tree a -> Int
  leaves t = case t of
      Leaf -> ??
      Node { key = k, left = l, right = r } -> ??
  

• definiere Funktion zum Herstellen eines Suchbaumes aus einer Liste:

  suchbaum :: [ Integer ] -> Tree Integer
  suchbaum [] = Leaf
  suchbaum (x : xs) = 
      let ( smaller, larger ) = partition ( < x ) xs
      in  Node { key = x
               , left = suchbaum smaller
               , right = suchbaum larger
               }
  

  testen z. B. mit suchbaum [8,1,4,3,9]
• definiere Funktion zur Herstellen der Inorder-Reihenfolge der Schlüssel

  inorder :: Tree a -> [a]
  inorder t = case t of
      Leaf -> ???
      Node { key = k, left = l, right = r } ->
          inorder l ++ [ k ] ++ inorder r
  

  testen z. B. mit inorder $ suchbaum [8,1,4,3,9]
• definiere Funktion zum Sortieren:

  sort :: [ Integer ] -> [ Integer ]
  sort xs = inorder $ suchbaum xs
  

  Welche Komplexität hat dieser Algorithmus?