home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Turbo Toolbox
/
Turbo_Toolbox.iso
/
sonderh1
/
baum_els.inc
< prev
next >
Wrap
Text File
|
1979-12-31
|
5KB
|
134 lines
{=== MODUL BAUM-ELS == Einfuegen, Loeschen und Suchen in binaeren Baeumen ===}
{----------------------------------------------------------------------------}
{ Diese Prozedur sucht nach einem Stichwort. Wird es nicht gefunden, wird
dies in 'gef' vermerkt, sonst wird ein Zeiger auf den Knoten gesetzt, der
das Stichwort enthaelt. Desweiteren wird ein Zeiger auf den Vorgaenger und
die Information, ob der gefundene Knoten rechter oder linker Sohn oder die
Wurzel des gesamten Baums ist (none), zurueckgegeben. }
PROCEDURE search (baum: tree; stichwort: key;
VAR knoten, vorg: tree; VAR seite: side; VAR gef: BOOLEAN);
BEGIN
vorg := nil;
knoten := baum;
seite := none;
gef := false;
WHILE (knoten <> nil) AND NOT (gef) DO
BEGIN
IF stichwort > knoten^.info.stichwort THEN
BEGIN
vorg := knoten; { rechts weitersuchen }
seite := right;
knoten := knoten^.rechts;
END
ELSE IF stichwort < knoten^.info.stichwort THEN
BEGIN
vorg := knoten; { links weitersuchen }
seite := left;
knoten := knoten^.links;
END
ELSE
gef := true; { gefunden }
END;
END;
{----------------------------------------------------------------------------}
{ Mit 'search' wird im 'baum' nach dem 'stichwort' gesucht, ist es noch nicht
vorhanden, werden die restlichen Informationen in einen neuen Knoten ein-
gelesen, der dann an der sortiert in den Baum eingefuegt wird. }
PROCEDURE einfuegen (VAR baum: tree; stichwort: key);
VAR info: information;
knoten, vorg: tree;
seite: side;
gef: BOOLEAN;
BEGIN
search (baum, stichwort, knoten, vorg, seite, gef);
IF gef THEN
message (4)
ELSE
BEGIN
restinfo (stichwort, info);
message (1);
New (knoten);
knoten^.info := info;
knoten^.links := nil;
knoten^.rechts := nil;
CASE seite OF
right: vorg^.rechts := knoten;
none: baum := knoten;
left: vorg^.links := knoten;
END;
END;
END;
{----------------------------------------------------------------------------}
{ Im 'baum' wird mit 'search' nach dem 'stichwort' gesucht und der dazuge-
hoerige Knoten gegebenenfalls aus dem Baum entfernt. }
PROCEDURE loeschen (VAR baum: tree; stichwort: key);
VAR knoten, vorg, ast, astvorg, zweig: tree;
seite: side;
gef: BOOLEAN;
BEGIN
search (baum, stichwort, knoten, vorg, seite, gef);
IF gef THEN
BEGIN
IF (knoten^.rechts = nil) AND (knoten^.links = nil) THEN
ast := nil
ELSE IF knoten^.rechts = nil THEN
ast := knoten^.links
ELSE IF knoten^.links = nil THEN
ast := knoten^.rechts
ELSE
BEGIN { es sind beide Nachfolger vorhanden }
ast := knoten^.rechts; astvorg := nil; { Es wird das naechst- }
WHILE ast^.links <> nil DO { groessere Stichwort }
BEGIN { gesucht. }
astvorg := ast; ast := ast^.links;
END;
IF astvorg <> nil THEN
BEGIN { Sonderfall, wenn der rechte }
astvorg^.links := ast^.rechts; { Nachfolger selbst der }
ast^.rechts := knoten^.rechts; { naechstgroesste ist. }
END;
ast^.links := knoten^.links; { den anderen Teilbaum mitnehmen }
END;
CASE seite OF { Der neu zusammengesetzte Teilbaum }
right: vorg^.rechts := ast; { 'ast' wird an den Vorgaenger des }
none: baum := ast; { zu loeschenden Knotens gehaengt. }
left: vorg^.links := ast; { der auch die Wurzel selbst }
END; { sein kann. }
Dispose (knoten);
END
ELSE
message (0); { nicht gefunden }
END;
{----------------------------------------------------------------------------}
{ Hier wird mit 'search' ein Stichwort gesucht und ggf. der dazugehoerige
Datensatz ausgegeben. Anstelle der 'message' kann die gewuenschte Operation
eingesetzt werden, z. B. die Korrektur des Datensatzes. }
PROCEDURE suchen (baum: tree; stichwort: key);
VAR info: information;
knoten, vorg: tree;
seite: side;
gef: BOOLEAN;
BEGIN
search (baum, stichwort, knoten, vorg, seite, gef);
IF gef THEN
message (3)
ELSE
message (0);
END;
{=========================== ENDE DES MODULS BAUM-ELS =======================}