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:
Für unsere frühere Suchroutine für Suchbäume bekommen wir durch die nötigen Anpassungen jetzt die iterative Version: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;
Daß wir hier ein Funktionsresultat zurückliefern anstatt eines Ergebnisparameters, ist nicht wesentlich.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;