Binäre Bäume als Komposita

• Knoten sind innere (Verzweigung) und äußere (Blatt).
• Die richtige Realisierung ist Kompositum

  interface Tree<K>; 
  class Branch<K> implements Tree<K>; 
  class Leaf<K> implements Tree<K>;
  

• Schlüssel: in allen Knoten, nur innen, nur außen.

der entsprechende algebraische Datentyp ist:

data Tree k = Leaf { ... }
  | Branch { left :: Tree k , ... 
           , right :: Tree k }

Übung: Anzahl aller Blätter, Summe aller Schlüssel (Typ?), der größte Schlüssel (Typ?)