Pointer Reversal (Ablauf)

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

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

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

Knoten werden in Tiefensuch-Reihenfolge betreten.