Pascal-Aufgabe: Binärbaum + Knoteninhalte

Pascal, Basic und andere nicht aufgelistete
Antworten
BaffA
Beiträge: 4
Registriert: So Nov 29, 2009 3:28 pm

Pascal-Aufgabe: Binärbaum + Knoteninhalte

Beitrag von BaffA » So Nov 29, 2009 3:38 pm

hallo,

möchte mir zu folgender aufgabe gern noch eine 2te meinung einholen.

Mein lösungsvorschlag:
a: falsch, da der knoten-wert sofort ausgegeben wird
b: flasch, wenn die Wurzel des Baums Null ist
c: richtig
d: es muss zuerst der rechte Teilbaum durchlaufen, bevor der Knotenwert ausgegeben wird
e: richtig

stimmt das so? liege ich richtig?

Hier die Aufgabe:
Gegeben sei ein Binärbaum mit den üblichen Typdefinitionen:

Code: Alles auswählen

  type
  tRefBinBaum = ^tBinBaum;
  tBinBaum = record
               info : integer;
               links,
               rechts : tRefBinBaum
             end;
Die Prozedur SymAusgabe soll die Knoteninhalte in der symmetrischen Reihenfolge (inorder) ausgegeben. (Hinweis: der Begriff symmetrische Reihenfolge wird im Skript erklärt.)

Beispiel: Für den binären Baum

Bild

sind die Knotenwerte in der symmetrischen Reihenfolge: 1, 3, 4, 6, 8.

Welche der fünf folgenden Varianten geben die Knotenwerte für beliebige Binärbäume in der symmetrischen Reihenfolge aus?

--> A:

Code: Alles auswählen

procedure SymAusgabe (
              inRefWurzel : tRefBinBaum);
{gibt die Knotenwerte eines Binärbaums in
 symmetrischer Reihenfolge aus}
begin
  if inRefWurzel <> nil then
  begin
     write (inRefWurzel^.info);
     if inRefWurzel^.links <> nil  then
       SymAusgabe(inRefWurzel^.links);
     if inRefWurzel^.rechts <> nil then
       SymAusgabe(inRefWurzel^.rechts)
  end
end; {SymAusgabe}
--> B:

Code: Alles auswählen

procedure SymAusgabe (
              inRefWurzel : tRefBinBaum);
{gibt die Knotenwerte eines Binärbaums in
 symmetrischer Reihenfolge aus}
begin
  if inRefWurzel^.links <> nil  then
    SymAusgabe(inRefWurzel^.links);
  write(inRefWurzel^.info);
  if inRefWurzel^.rechts <> nil then
    SymAusgabe(inRefWurzel^.rechts)
end; {SymAusgabe}
--> C:

Code: Alles auswählen

procedure SymAusgabe (
              inRefWurzel : tRefBinBaum);
{gibt die Knotenwerte eines Binärbaums in 
 symmetrischer Reihenfolge aus}
begin
  if inRefWurzel <> nil then
  begin
    SymAusgabe(inRefWurzel^.links);
    write (inRefWurzel^.info);
    SymAusgabe(inRefWurzel^.rechts)
  end
end; {SymAusgabe}
--> D:

Code: Alles auswählen

procedure SymAusgabe (
              inRefWurzel : tRefBinBaum);
{gibt die Knotenwerte eines Binärbaums in 
 symmetrischer Reihenfolge aus}
begin
  if inRefWurzel <> nil then
  begin
    if inRefWurzel^.links <> nil  then
      SymAusgabe(inRefWurzel^.links);
    if inRefWurzel^.rechts <> nil then
      SymAusgabe(inRefWurzel^.rechts);
  write (inRefWurzel^.info)
  end
end; {SymAusgabe}
--> E:

Code: Alles auswählen

procedure SymAusgabe (
              inRefWurzel : tRefBinBaum);
{gibt die Knotenwerte eines Binärbaums in
 symmetrischer Reihenfolge aus}
begin
  if inRefWurzel <> nil then
  begin
    if inRefWurzel^.links <> nil  then
      SymAusgabe(inRefWurzel^.links);

    write (inRefWurzel^.info);
    if inRefWurzel^.rechts <> nil then
      SymAusgabe(inRefWurzel^.rechts)
  end
end; {SymAusgabe}

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Pascal-Aufgabe: Binärbaum + Knoteninhalte

Beitrag von Xin » Mo Nov 30, 2009 10:27 am

BaffA hat geschrieben:hallo,

möchte mir zu folgender aufgabe gern noch eine 2te meinung einholen.

Mein lösungsvorschlag:
a: falsch, da der knoten-wert sofort ausgegeben wird
b: flasch, wenn die Wurzel des Baums Null ist
c: richtig
d: es muss zuerst der rechte Teilbaum durchlaufen, bevor der Knotenwert ausgegeben wird
e: richtig

stimmt das so? liege ich richtig?
Du liegst richtig, aber Du fragtest nach Meinungen. Als Informatiker würde ich B und C für richtig erachten und E für falsch.
Warum?
B ist in meinem Augen richtig, weil ich die Verantwortlichkeiten anders sehe. Arbeite ich mit einem nicht existierenden Baum und verlange vom Computer die Ausgabe eines nicht existierenden Baums, dann bekomme ich, was ich angefordert habe. Aktuelle Sprachen bieten jedoch nicht die Möglichkeit, hier die Korrektheit des Codes statisch zu prüfen, von daher ist Deine Auffassung 'falsch' diskussionsfähig.
C ist richtig, für Sicherheitsbewußte. Nachteil: der Funktionsaufruf wird auch für nicht existierende Blätter durchgeführt.
E ist falsch, da für jedes Blatt zweimal geprüft wird, ob der Baum existiert oder nicht. Hier besteht also Optimierungsbedarf => in meinen Augen falsch.

Das Optimale kommt aus Lösung B:

Code: Alles auswählen

procedure SymAusgabe_UnverifiedRoot (
              inRefWurzel : tRefBinBaum);
{gibt die Knotenwerte eines Binärbaums in
symmetrischer Reihenfolge aus, prüft nicht
die Wurzel}
begin
  if inRefWurzel^.links <> nil  then
    SymAusgabe(inRefWurzel^.links);
  write(inRefWurzel^.info);
  if inRefWurzel^.rechts <> nil then
    SymAusgabe(inRefWurzel^.rechts)
end; {SymAusgabe}

procedure SymAusgabe (
              inRefWurzel : tRefBinBaum);
{gibt die Knotenwerte eines Binärbaums in
symmetrischer Reihenfolge aus}
begin
  if inRefWurzel^.links <> nil  then
    SymAusgabe_UnverifiedRoot( inRefWurzel );
end;
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

BaffA
Beiträge: 4
Registriert: So Nov 29, 2009 3:28 pm

Re: Pascal-Aufgabe: Binärbaum + Knoteninhalte

Beitrag von BaffA » Di Dez 01, 2009 1:27 pm

danke für deine hilfe :)

hier die musterlösung:
Die Prozeduren C und E sind richtig.

zu A) Die Prozedur SymAusgabe gibt die Knotenwerte in Hauptreihenfolge (preorder)
aus. Für den in der Aufgabe gezeichneten Baum sind die Knotenwerte in Haupt-
reihenfolge : 6, 3, 1, 4, 8.

zu B) Der Fall eines leeren Baumes ist nicht berücksichtigt.

zu C) Die Prozedur ist richtig.

zu D) Die Prozedur gibt die Knotenwerte nicht in der symmetrischen Reihenfolge aus.
Für den in der Aufgabe gezeichneten Baum ist die Ausgabe: 1, 4, 3, 8, 6. Einen
derartigen Baumdurchlauf nennt man postorder-Durchlauf.

zu E) Die Prozedur ist richtig.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Pascal-Aufgabe: Binärbaum + Knoteninhalte

Beitrag von Xin » Di Dez 01, 2009 2:53 pm

Wie gesagt: E liefert das richtige Ergebnis aber auf eine Art und Weise, die in meinen Augen nicht akzeptabel ist, also falsch.
Mit B kann ich besser leben. Das wird Dir Dein Informatiklehrer vermutlich anders beibringen, weil meine Lösungen auf Disziplin basieren, die Lösungen Deines Lehrers auf Funktion. Arbeite ich nicht diszipliniert, funktioniert es nicht, E hat einen Sicherungsanker, verbrät dafür aber unnötig Rechenleistung.
Normalerweise macht man die Fehler bei komplizierten Sachen, da nutzt Dir Deine Sicherung nix, also lass ich sie gleich weg.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten