Während des Suchens sind wir in einem von drei Zuständen: entweder, wir haben das Gesuchte schon gefunden, oder wir wissen schon, daß es nicht da sein kann, oder wir wissen noch nichts darüber. Diesen Suchzustand rechnen wir mit:
PROCEDURE suche(k: keytype; d: Daten; VAR wo: Ort);
VAR Zustand: (suchen, ja, nein);
BEGIN Zustand := suchen;
WHILE Zustand = suchen
DO IF leer(d) THEN wo := NIRGENDS; Zustand := nein;
ELSE wo := Einstieg(d);
IF k = key(wo) THEN Zustand := ja
ELSE d := Teilstruktur(d);
END;
END;
END;
END suche;
Für unsere frühere Suchroutine
für Suchbäume bekommen wir
durch die nötigen Anpassungen jetzt die iterative Version:
PROCEDURE lookup(k: keytype; b: stree): stree;
VAR Zustand: (suchen, ja, nein);
BEGIN Zustand := suchen;
WHILE Zustand = suchen
DO IF b = NIL THEN Zustand := nein
ELSIF k < b^.key THEN b := b^.left;
ELSIF k > b^.key THEN b := b^.right;
ELSE (* k = b^.key *) Zustand := ja;
END;
END;
RETURN b;
END lookup;
Daß wir hier ein Funktionsresultat zurückliefern anstatt
eines Ergebnisparameters, ist nicht wesentlich.