home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / 1988 / 10_11 / paslist.asc < prev    next >
Text File  |  1979-12-31  |  6KB  |  133 lines
  1.  
  2.  
  3. PROGRAM BaumArray(Input, Output);                  { Kopfzeile }
  4. {---------------------------------------------------------------
  5.       Speichern eines Binärbaums auf zwei Arten:
  6.       a) in einer dynamischen Datenstuktur 
  7.       b) schichtenweise sequentiell in einem ARRAY
  8. ---------------------------------------------------------------}
  9. CONST  N      = 63;              { ermöglicht Baum bis zur     }
  10.                                  { Höhe 6, denn LOG2 (N+1) = 6 }
  11.  
  12. TYPE   Zeiger = ^Knoten;                      { globale Typ-   }
  13.        Knoten = RECORD                        { vereinbarungen }
  14.                    Inhalt: Integer;           { =Grundlage für }
  15.                    Links,                     { den Aufbau des }
  16.                    Rechts: Zeiger             { binären Baums  }
  17.                 END;
  18.  
  19. VAR  Speicher    : ARRAY [1..N] OF Integer;   { globale        }
  20.      Wurzel      : Zeiger;                    { Variablen-     }
  21.      Eingabe     : Integer;                   { vereinbarungen }
  22.      
  23. {--------------------------------------------------------------}
  24.  
  25. PROCEDURE ErzeugeBaum(VAR Anfang:Zeiger; Wert:Integer);
  26. BEGIN
  27.   IF Anfang=NIL THEN
  28.     BEGIN    { füge Wert als erstes Element in leeren Baum ein }
  29.       New(Anfang);                   { reserviere neuen Knoten }
  30.       WITH Anfang^ DO
  31.         BEGIN
  32.           Inhalt:=Wert;
  33.           Links :=NIL;                 { linker Unterbaum leer }
  34.           Rechts:=NIL                 { rechter Unterbaum leer }
  35.         END { WITH }
  36.     END { Anfang=NIL }
  37.   ELSE             { füge Wert in den richtigen Unterbaum ein, }
  38.     WITH Anfang^ DO         { Duplikate werden dabei ignoriert }
  39.       IF Wert<Inhalt THEN
  40.         ErzeugeBaum(Links,Wert)                    { Rekursion }è      ELSE IF Wert>Inhalt THEN
  41.         ErzeugeBaum(Rechts,Wert)                   { Rekursion }
  42. END;                 { Ende der Prozedurdefinition ErzeugeBaum }
  43. {--------------------------------------------------------------}
  44.  
  45. PROCEDURE DurchlaufeBaum(Anfang:Zeiger);             { inorder }
  46. BEGIN                      { Anzeige aller Knoteninhalte gemäß }
  47.   IF Anfang<>NIL THEN               { der vereinbarten Ordnung }
  48.     WITH Anfang^ DO
  49.       BEGIN
  50.         DurchlaufeBaum(Links);                     { Rekursion }
  51.         WRITE(Inhalt:5);
  52.         DurchlaufeBaum(Rechts)                     { Rekursion }
  53.       END { WITH }
  54. END;              { Ende der Prozedurdefinition DurchlaufeBaum }
  55. {--------------------------------------------------------------}
  56.  
  57. PROCEDURE InitArray;        { besetze Array mit Ausnahmewert 0 }
  58. VAR i : 1..N;
  59. BEGIN
  60.   FOR i:=1 TO N DO Speicher[i]:=0                  { Willkür ! }
  61. END;                   { Ende der Prozedurdefinition InitArray }
  62. {--------------------------------------------------------------}
  63.  
  64. PROCEDURE FuelleArray(Baum:Zeiger; Nr:Integer);
  65.                     { Übertragen der Baumstruktur in das Array }
  66. BEGIN
  67.   IF Baum<>NIL THEN
  68.     WITH Baum^ DO
  69.       BEGIN
  70.         IF Nr<=N THEN Speicher[Nr]:=Inhalt;
  71.         FuelleArray(Links,Nr*2);                   { Rekursion }
  72.         FuelleArray(Rechts,Nr*2+1)                 { Rekursion }
  73.       END { WITH }
  74. END;                 { Ende der Prozedurdefinition FuelleArray }
  75. {--------------------------------------------------------------}
  76.  
  77. PROCEDURE DurchlaufeArray(Start:Integer);            { inorder }
  78. BEGIN                       { Anzeige aller Arrayinhalte gemäß }
  79.   IF Speicher[Start]<>0 THEN        { der vereinbarten Ordnung }
  80.     BEGIN
  81.       IF (Start*2)<=N THEN
  82.         DurchlaufeArray(Start*2);                  { Rekursion }
  83.       WRITE(Speicher[Start]:5);
  84.       IF (Start*2+1)<=N THEN
  85.         DurchlaufeArray(Start*2+1)                 { Rekursion }
  86.     END
  87. END;             { Ende der Prozedurdefinition DurchlaufeArray }
  88. {--------------------------------------------------------------}
  89.  
  90. PROCEDURE GibArrayAus;                           { sequentiell }
  91. VAR Anzahl,Feldweite,i : Integer;
  92. BEGIN        { Anzeige aller Inhalte in der Ordnung des Arrays }
  93.   Anzahl:=1;
  94.   REPEAT
  95.     Feldweite:=(N+1) DIV Anzahl;
  96.     FOR i:=Anzahl TO 2*Anzahl-1 DO { gib Schicht des Baums aus }
  97.       IF Speicher[i]<>0 THEN                { 0 = Ausnahmewert }
  98.         Write(Speicher[i]:Feldweite)
  99.       ELSE Write('.':Feldweite);   { nicht benutzte Knoten des }
  100.     WriteLn;                   { Baums werden durch . markiert }
  101.     Anzahl:=Anzahl*2
  102.   UNTIL Anzahl>N
  103. END;                 { Ende der Prozedurdefinition GibArrayAus }
  104. {--------------------------------------------------------------}è
  105. BEGIN                      { Anweisungsteil des Hauptprogramms }
  106.   NEW(Wurzel);                { Wurzel zeigt zunächst noch auf }
  107.   Wurzel:=NIL;             { keinen Knoten; NIL = 'not in list'}
  108.   WriteLn('Elemente eingeben (0=Ende):');
  109.   Read(Eingabe); Write(',  ');
  110.   WHILE Eingabe<>0 DO                    { Speichern von Daten }
  111.     BEGIN                                { geordnet in einem   }
  112.       ErzeugeBaum(Wurzel,Eingabe);       { Binärbaum           }
  113.       Read(Eingabe);
  114.       IF Eingabe<>0 THEN Write(',  ')
  115.     END; { WHILE }
  116.   WriteLn; Writeln;
  117.   WriteLn('Ausgabe der Baumelemente (inorder)');
  118.   WriteLn('----------------------------------');
  119.   DurchlaufeBaum(Wurzel);
  120.   WriteLn;
  121.                                   { Speichern derselben Daten  }
  122.   InitArray;                      { schichtenweise sequentiell }
  123.   FuelleArray(Wurzel,1);          { in einem Array             }
  124.   WriteLn;
  125.   WriteLn('Ausgabe der Arrayelemente (inorder)');
  126.   WriteLn('-----------------------------------');
  127.   DurchlaufeArray(1);
  128.   WriteLn; Writeln;
  129.   WriteLn('Zeilenweise sequentielle Ausgabe des Arrays');
  130.   WriteLn('-------------------------------------------');
  131.   GibArrayAus
  132. END.
  133.