## Suchbäume

• deklariere Datentyp für binäre Bäume mit Schlüsseln vom Typ `a`:
```-- brauchen wir später:
import List (partition)

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 ->  1
Node { key = k, left = l, right = r } ->
leaves l + leaves r
```

• definiere Funktion zum Herstellen eines Suchbaumes aus einer Liste:
```suchbaum :: [ Int ] -> Tree Int
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 :: [ Int ] -> [ Int ]
sort xs = inorder \$ suchbaum xs
```
Welche Komplexität hat dieser Algorithmus?

Johannes Waldmann 2005-06-08