Bäume in Haskell

Bäume sind, wie Listen, Rekursive Datenstrukturen in Haskell. Ein Binärbaum ist entweder leer oder er besteht aus einem Wert in einem Knoten und zwei Teilbäumen (links und rechts).

-- Ein ITree ist entweder Empty
-- oder ein INode mit einem Int-Wert und zwei ITree-Kindern.
data ITree = INode Int ITree ITree | Empty

Diese Definition ist doppelt rekursiv.

• Konstruktoren: INode :: Int -> ITree -> ITree -> ITree und Empty :: ITree

Beispiel: Der Baum

INode 5
  (INode 3 (INode 1 Empty Empty) (INode 4 Empty Empty))
  (INode 7 (INode 6 Empty Empty) (Empty))

entspricht:
!VL01_Funktionale_Programmierung, p.68

Doppelt rekursive Funktionen auf Bäumen

Funktionen auf Bäumen sind oft ebenfalls doppelt rekursiv.

sumt :: ITree -> Int
sumt Empty = 0 -- Rekursionsanker
sumt (INode v tl tr) = v + sumt tl + sumt tr -- Zwei rekursive Aufrufe