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.