Einführung in die imperative Programmierung

Breitendurchlauf

program Binaerbaum (input, output);  
{Verwaltet einen Binärbaum}
  const
NULL=0;
  EINS=1;
  F=false;
  T=true;

  type
  tRefBinBaum= ^tBinBaum;
  tBinbaum= record
              info: integer;
              links:tRefBinBaum;
              rechts:tRefBinBaum;
            end;
  tRefListe= ^tListe;
  tListe= record
            info: tRefBinBaum;
            next: tRefListe;
          end;

  var
  wurzel : tRefBinBaum;
  Zahl: integer;
  liste: tRefListe;

  procedure einf(inWert:integer;
                 var ioBaum:tRefBinBaum);
  {fügt inWert als neuen Knoten in den Baum ein}
    var
    Zeiger: tRefBinBaum;
  begin
    if ioBaum=nil then
    {Baum ist noch leer}
    begin
      new(Zeiger);
      Zeiger^.info:=inWert;
      Zeiger^.links:=nil;
      Zeiger^.rechts:=nil;
      ioBaum:=Zeiger;
    end
    else
    begin
      if inWert <= ioBaum^.info then
      {Wert links einfügen}
      begin
        if ioBaum^.links=nil then
        {einfügen}
        begin
          new(Zeiger);
          Zeiger^.info:=inWert;
          Zeiger^.links:=nil;
          Zeiger^.rechts:=nil;
          ioBaum^.links:=Zeiger;
        end
        else
        {links weitersuchen}
          einf(inWert, ioBaum^.links);
      end;
      if inWert > ioBaum^.info then
      {Wert rechts einfügen}
      begin
        if ioBaum^.rechts=nil then
        {einfügen}
        begin
          new(Zeiger);
          Zeiger^.info:=inWert;
          Zeiger^.links:=nil;
          Zeiger^.rechts:=nil;
          ioBaum^.rechts:=Zeiger;
        end
        else
        {rechts weitersuchen}
          einf(inWert, ioBaum^.rechts);
      end;
    end;
  end;

  function finden(inBaum:tRefBinBaum;
                  inWert:integer): boolean;
  {sucht inWert im Baum und gibt true oder false zurück}
  begin
    if inBaum=nil then
    {Knoten leer}
      finden:=F
    else
      if inBaum^.info=inWert then
      {Wert gefunden}
        finden:=T
      else
      {links und rechts suchen}
        finden:=finden(inBaum^.links,inWert) or finden(inBaum^.rechts,inWert);
  end;

  procedure inorder(inBaum:tRefBinBaum);
  begin
    if inBaum <> nil then
    begin
      inorder(inBaum^.links);
      writeln(inBaum^.info);
      inorder(inBaum^.rechts);
    end;
  end;

  procedure breitendurchlauf( var liste:tRefListe);
    var ende,neu: tRefListe;
  begin
    if (liste<>nil) then
    begin
      writeln(liste^.info^.info);
      ende:=liste;
      while (ende^.next<>nil) do
        ende:= ende^.next;
      if liste^.info^.links<>nil then
      begin
        neu:=new(tRefListe);
        neu^.info:=liste^.info^.links;
        neu^.next:=nil;
        ende^.next:= neu;
        ende:=neu;
      end;
      if liste^.info^.rechts<>nil then
      begin
        neu:=new(tRefListe);
        neu^.info:=liste^.info^.rechts;
        neu^.next:=nil;
        ende^.next:= neu;
        ende:=neu;
      end;
      liste:=liste^.next;
      breitendurchlauf(  liste);
    end;
  end;

BEGIN
  {Baum aufbauen}
  wurzel:=nil;
  einf(NULL, wurzel);
  einf(EINS , wurzel);
  einf(9, wurzel);
  einf(5, wurzel);
  einf(3, wurzel);
  einf(10, wurzel);
  einf(EINS, wurzel);

  for Zahl:= 20 to 30 do
  begin
    einf(Zahl, wurzel);
    {Zahl := Zahl+1; ist auskommentiert}
  end;

  {Baum drucken}
  writeln('inorder-Durchlauf');
  inorder(wurzel);

  writeln('Breitendurchlauf');
  liste:=new(tRefListe);
  liste^.info:= wurzel;
  liste^.next:= nil;
  breitendurchlauf(liste);


END.