Pointer Reversal (Ablauf)

• pre: p = null, c = root, ∀z : mark(z) = 0
• post: ∀z : mark(z) = if (root→^*z) then 3 else 0

Schritt (neue Werte immer mit '): falls mark(c) = ...

• 0: c' = head(c);head'(c) = p;mark'(c) = 1;p' = c;
• 1,2,3: falls mark(p) = ...
  • 1: head'(p) = c;tail'(p) = head(p);mark'(p) = 2;c' = tail(p);p' = p
  • 2: tail'(p) = c;mark'(p) = 3;p' = tail(p);c' = p;

Knoten werden in Tiefensuch-Reihenfolge betreten.