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 }
leaves :: Tree a -> Int leaves t = case t of Leaf -> 1 Node { key = k, left = l, right = r } -> leaves l + leaves r
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]
inorder :: Tree a -> [a] inorder t = case t of Leaf -> ??? Node { key = k, left = l, right = r } -> inorder l ++ [ k ] ++ inorder rtesten z. B. mit
inorder $ suchbaum [8,1,4,3,9]
sort :: [ Int ] -> [ Int ] sort xs = inorder $ suchbaum xsWelche Komplexität hat dieser Algorithmus?