home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / sonderh1 / baum_els.inc < prev    next >
Encoding:
Text File  |  1979-12-31  |  4.7 KB  |  134 lines
  1. {=== MODUL BAUM-ELS == Einfuegen, Loeschen und Suchen in binaeren Baeumen ===}
  2. {----------------------------------------------------------------------------}
  3. { Diese Prozedur sucht nach einem Stichwort. Wird es nicht gefunden, wird
  4.   dies in 'gef' vermerkt, sonst wird ein Zeiger auf den Knoten gesetzt, der
  5.   das Stichwort enthaelt. Desweiteren wird ein Zeiger auf den Vorgaenger und
  6.   die Information, ob der gefundene Knoten rechter oder linker Sohn oder die
  7.   Wurzel des gesamten Baums ist (none), zurueckgegeben. }
  8.  
  9. PROCEDURE search (baum: tree; stichwort: key;
  10.                   VAR knoten, vorg: tree; VAR seite: side; VAR gef: BOOLEAN);
  11.  
  12. BEGIN
  13.   vorg := nil;
  14.   knoten := baum;
  15.   seite := none;
  16.   gef := false;
  17.   WHILE (knoten <> nil) AND NOT (gef) DO
  18.   BEGIN
  19.     IF stichwort > knoten^.info.stichwort THEN
  20.       BEGIN
  21.         vorg := knoten;                                { rechts weitersuchen }
  22.         seite := right;
  23.         knoten := knoten^.rechts;
  24.       END
  25.     ELSE IF stichwort < knoten^.info.stichwort THEN
  26.       BEGIN
  27.         vorg := knoten;                                 { links weitersuchen }
  28.         seite := left;
  29.         knoten := knoten^.links;
  30.       END
  31.     ELSE
  32.       gef := true;                                                { gefunden }
  33.   END;
  34. END;
  35.  
  36. {----------------------------------------------------------------------------}
  37. { Mit 'search' wird im 'baum' nach dem 'stichwort' gesucht, ist es noch nicht
  38.   vorhanden, werden die restlichen Informationen in einen neuen Knoten ein-
  39.   gelesen, der dann an der sortiert in den Baum eingefuegt wird. }
  40.  
  41. PROCEDURE einfuegen (VAR baum: tree; stichwort: key);
  42.  
  43. VAR info: information;
  44.     knoten, vorg: tree;
  45.     seite: side;
  46.     gef: BOOLEAN;
  47.  
  48. BEGIN
  49.   search (baum, stichwort, knoten, vorg, seite, gef);
  50.   IF gef THEN
  51.     message (4)
  52.   ELSE
  53.   BEGIN
  54.     restinfo (stichwort, info);
  55.     message (1);
  56.     New (knoten);
  57.     knoten^.info := info;
  58.     knoten^.links := nil;
  59.     knoten^.rechts := nil;
  60.     CASE seite OF
  61.       right: vorg^.rechts := knoten;
  62.        none: baum := knoten;
  63.        left: vorg^.links := knoten;
  64.     END;
  65.   END;
  66. END;
  67.  
  68. {----------------------------------------------------------------------------}
  69. { Im 'baum' wird mit 'search' nach dem 'stichwort' gesucht und der dazuge-
  70.   hoerige Knoten gegebenenfalls aus dem Baum entfernt. }
  71.  
  72. PROCEDURE loeschen (VAR baum: tree; stichwort: key);
  73.  
  74. VAR knoten, vorg, ast, astvorg, zweig: tree;
  75.     seite: side;
  76.     gef: BOOLEAN;
  77.  
  78. BEGIN
  79.   search (baum, stichwort, knoten, vorg, seite, gef);
  80.   IF gef THEN
  81.     BEGIN
  82.       IF (knoten^.rechts = nil) AND (knoten^.links = nil) THEN
  83.         ast := nil
  84.       ELSE IF knoten^.rechts = nil THEN
  85.         ast := knoten^.links
  86.       ELSE IF knoten^.links = nil THEN
  87.         ast := knoten^.rechts
  88.       ELSE
  89.       BEGIN                             { es sind beide Nachfolger vorhanden }
  90.         ast := knoten^.rechts;  astvorg := nil;       { Es wird das naechst- }
  91.         WHILE ast^.links <> nil DO                    { groessere Stichwort  }
  92.         BEGIN                                         { gesucht.             }
  93.           astvorg := ast; ast := ast^.links;
  94.         END;
  95.         IF astvorg <> nil THEN
  96.         BEGIN                                  { Sonderfall, wenn der rechte }
  97.           astvorg^.links := ast^.rechts;             { Nachfolger selbst der }
  98.           ast^.rechts := knoten^.rechts;              { naechstgroesste ist. }
  99.         END;
  100.         ast^.links := knoten^.links;        { den anderen Teilbaum mitnehmen }
  101.       END;
  102.       CASE seite OF                      { Der neu zusammengesetzte Teilbaum }
  103.         right: vorg^.rechts := ast;       { 'ast' wird an den Vorgaenger des }
  104.          none: baum := ast;               { zu loeschenden Knotens gehaengt. }
  105.          left: vorg^.links := ast;              { der auch die Wurzel selbst }
  106.       END;                                                      { sein kann. }
  107.       Dispose (knoten);
  108.     END
  109.   ELSE
  110.     message (0);                                            { nicht gefunden }
  111. END;
  112.  
  113. {----------------------------------------------------------------------------}
  114. { Hier wird mit 'search' ein Stichwort gesucht und ggf. der dazugehoerige
  115.   Datensatz ausgegeben. Anstelle der 'message' kann die gewuenschte Operation
  116.   eingesetzt werden, z. B. die Korrektur des Datensatzes.                    }
  117.  
  118. PROCEDURE suchen (baum: tree; stichwort: key);
  119.  
  120. VAR info: information;
  121.     knoten, vorg: tree;
  122.     seite: side;
  123.     gef: BOOLEAN;
  124.  
  125. BEGIN
  126.   search (baum, stichwort, knoten, vorg, seite, gef);
  127.   IF gef THEN
  128.     message (3)
  129.   ELSE
  130.     message (0);
  131. END;
  132.  
  133. {=========================== ENDE DES MODULS BAUM-ELS =======================}
  134.