Prüfe: Sind alle Blätter in einem Baum die Maxima der Pfade zu ihnen?

[DesWeeedert]

Hallo,

ich habe hier mal wieder eine Aufgabe, an der ich gerade scheitere:

Schreiben Sie eine rekursive Funktion, die einen Binärbaum mit mindestens zwei Knoten übergeben bekommt und den gesamten Baum durchläuft. Dabei entscheidet Ihre Funktion ob der Wert jedes Blattes des Baumes größer ist als jeder der Werte der Knoten auf dem Pfad von der Wurzel zu diesem Blatt. Neben dem üblichen Zeiger auf die Baumwurzel ist ein weiterer Übergabeparameter erforderlich. Kommentieren Sie, mit welchem Wert dieser beim ersten Aufruf zu belegen ist.

Als Beispiel gibt es eine Grafik im Anhang. Der linke Baum erfüllt die Bedingung, der rechte Baum nicht.

Wenn ein Baum die Bedingung nicht erfüllt, dann soll die Funktion false ausgeben, ansonsten true.

Hier kommt das Programm, es geht um die Funktion BlattMax. Alles andere ist vorgegeben und richtig:

Code:

program TesteBlattMax (input, output);

  type
    tNatZahl = 1..maxint;
    tRefBinBaum = ^tBinBaum;
    tBinBaum = record
                 Wert:tNatZahl;
                 links:tRefBinBaum;
                 rechts:tRefBinBaum
               end;
           
  var
    Wurzel : tRefBinBaum;
    blaetterSindMax : Boolean;

  function BlattMax ( inRefWurzel : tRefBinBaum; inPfadMax : tNatZahl) : Boolean;
    { prüft ob alle Blätter des Baumes die Maxima der Pfade zu ihnen sind }

  {Hier steht dann die Funktion. Meine Lösung steht weiter unten separat.}



  procedure BaumAufbauen (var outWurzel : tRefBinBaum) ;
    var 
      index,
      Zahl : integer;
      elter, neuerKnoten : tRefBinBaum;    
     
    function KnotenVonIndex (baum : tRefBinBaum; index : integer) : tRefBinBaum;
      var
        elter : tRefBinBaum;
      begin
        if (index = 1) then
          KnotenVonIndex := baum
        else
        begin
          elter := KnotenVonIndex(baum, index div 2);
          if ( (index mod 2 ) = 0 ) then
            KnotenVonIndex := elter^.links
          else
            KnotenVonIndex := elter^.rechts
        end;
      end;{ KnotenVonIndex }

    begin
        read (index);
        new (outWurzel);
        read (Zahl);
        outWurzel^.Wert := Zahl;
        outWurzel^.links := nil;
        outWurzel^.rechts := nil;
        read (index);
        while (index <> 0) do
        begin            
          elter := KnotenVonIndex(outWurzel, index div 2);
          new (neuerKnoten);
          read (Zahl);    
          neuerKnoten^.Wert := Zahl;  
          neuerKnoten^.links := nil;
          neuerKnoten^.rechts := nil;
          if ( (index mod 2 ) = 0 ) then
            elter^.links := neuerKnoten
          else
            elter^.rechts := neuerKnoten;
          read (index);      
        end;    
    end; { BaumAufbauen }

  begin
    writeln('Bitte Baum in level-order eingeben Eingabeformat: Immer erst der Index eines Knotens, dann dessen Wert:');
    BaumAufbauen (Wurzel);
    blaetterSindMax := BlattMax(Wurzel, 1);
    if blaetterSindMax then
      writeln ('Alle Blaetter sind groesser als alle Knoten auf den jeweiligen Pfaden zu ihnen.')
    else
      writeln ('Mind. ein Blatt ist nicht groesser als alle Knoten auf seinem Pfad.');

  end. { TesteBBKnotenzahl }

Hier ist meine aktuelle Lösung, auch mit Kommentaren, was ich mir da gedacht habe. Man kann es compilieren, aber es tut nicht, was es soll:

Code:

function BlattMax ( inRefWurzel : tRefBinBaum; inPfadMax : tNatZahl) : Boolean;
   { prüft ob alle Blätter des Baumes die Maxima der Pfade zu ihnen sind }
   
      begin   
         if inPfadMax = 1 then
               BlattMax := true;
         {meine Idee ist hier, BlattMax am Anfang einmal auf true zu setzen. 
         Später soll es dann auf false gesetzt werden sobald ein Blatt gefunden wird, für das die Bedingung nicht erfüllt ist.}
               
         if inRefWurzel^.Wert > inPfadMax then
            inPfadMax := inRefWurzel^.Wert;
         {inPfadMax soll immer das Maximum des bisherigen Pfades beinhalten. 
         Wenn die aktuelle Wurzel größer ist, dann wird inPfadMax auf den Wert der Wurzel gesetzt}
            
         while (inRefWurzel^.links <> nil) or (inRefWurzel^.rechts <> nil)   do   {solange aktueller Knoten kein Blatt ist...}
            
            if (inRefWurzel^.links = nil) and (inRefWurzel^.rechts <> nil) then 
            {nur linker Teilbaum vorhanden, dann gehe den linken Teilbaum weiter}
               BlattMax := BlattMax (inRefWurzel^.rechts, inPfadMax);
            
            if (inRefWurzel^.links <> nil) and (inRefWurzel^.rechts = nil) then
            {nur rechter Teilbaum vorhanden, dann gehe den rechten Teilbaum weiter}
               BlattMax := BlattMax (inRefWurzel^.links, inPfadMax);
            
            if (inRefWurzel^.links <> nil) and (inRefWurzel^.rechts <> nil) then 
            {linker und rechter Teilbaum vorhanden, dann gehe in beide Richtungen weiter}
               BlattMax := BlattMax (inRefWurzel^.links, inPfadMax);
               BlattMax := BlattMax (inRefWurzel^.rechts, inPfadMax);
            
                     
         if (inRefWurzel^.links = nil) and (inRefWurzel^.rechts = nil) then {wir haben ein Blatt erreicht}
            begin
               if inRefWurzel^.Wert <= inPfadMax then 
               {wenn jetzt der Wert des Blattes kleiner oder gleich dem bisherigen Pfadmaximum ist, 
               dann soll BlattMax auf false gesetzt werden}
                  BlattMax := false;
            end;
               
               
      end;

[Zacherl]

Eine

Delphi-Quellcode:

while

Schleife hat in einem rein rekursiven Algorithmus eher nichts zu suchen :stupid: An dieser Stelle fehlt außerdem ein

Delphi-Quellcode:

begin

..

Delphi-Quellcode:

end

Block, falls du vorhattest nicht nur die erste Bedingung in der Schleife auszuführen. Allgemein ist dein Code aber viel zu kompliziert gedacht:

Delphi-Quellcode:

type
  TNodeValue = 1..MAXINT;

  PTreeNode = ^TTreeNode;
  TTreeNode = record
  public
    Value: TNodeValue;
    L: PTreeNode;
    R: PTreeNode;
  end;

function BlattMax(Node: PTreeNode; MaxValue: TNodeValue): Boolean; overload;
begin
  if (not Assigned(Node^.L)) and (not Assigned(Node^.R)) then
  begin
    Result := (Node^.Value > MaxValue);
  end else
  begin
    if (Node^.Value > MaxValue) then
    begin
      MaxValue := Node^.Value;
    end;
    Result := true;
    if Assigned(Node^.L) then Result := Result and BlattMax(Node^.L, MaxValue);
    if Assigned(Node^.R) then Result := Result and BlattMax(Node^.R, MaxValue);
  end;
end;

[Michael II]

Zitat:

function BlattMax(Node: PTreeNode; MaxValue: TNodeValue): Boolean; overload;

Sehr schön :-).

Ich würde noch ein {$B-} .. {$B+} reinhängen, damit die in diesem Code ausgenützte Kurzschlussauswertung draussen in der Welt auch ganz sicher stattfindet. [Bei den allermeisten Usern ist {$B-} eh Standard.]

[himitsu]

Wozu

Delphi-Quellcode:

{$B+}

/

Delphi-Quellcode:

{$BOOLEVAL ON}

?

Damit der Code langsamer läuft, oder um sich beim Debuggen auch die "sinnlos" ausgewerteten Zweige anzugucken?

Delphi-Quellcode:

if Assigned(Node^.L) then Result := BlattMax(Node^.L, MaxValue) and Result;
if Assigned(Node^.R) then Result := BlattMax(Node^.R, MaxValue) and Result;

Achtung, bei "vielen" DBMS ist die Auswerungsreihenfolge nicht fest und der Optimierer kann das Tauschen, wenn er Bock drauf hat ... Pascal/Delphi macht das aber nicht.

[Michael II]

Zitat:

Damit der Code langsamer läuft, oder um sich beim Debuggen auch die "sinnlos" ausgewerteten Zweige anzugucken?

Nein natürlich nicht, dass der Code langsamer läuft; im Gegenteil:

Ich habe mich falsch ausgedrückt: Ich meinte nur (wollte meinen ;-)), dass man bei diesem Code darauf achten muss, dass B- [Standard] effektiv gesetzt ist. Wenn die Kurzschlussauswertung ausgeschaltet ist (B+), dann würde bei diesem Code immer der ganze Baum durchsucht.

(Man kann den Code natürlich leicht so umschreiben, dass auch bei B+ immer nur die nötigen Baumteile durchlaufen werden.)

Ich bin still.

[DesWeeedert]

Hallo zusammen und vielen Dank für eure Antworten =)

Die Schreibweise von Zacherl war mir in der Form noch unbekannt und ich habe seinen Code erstmal für mich übersetzt:

Code:

function BlattMax ( inRefWurzel : tRefBinBaum; inPfadMax : tNatZahl) : Boolean;
   { prüft ob alle Blätter des Baumes die Maxima der Pfade zu ihnen sind }
   
      begin 
         if (inRefWurzel^.links = nil) and (inRefWurzel^.rechts = nil) then
            BlattMax := (inRefWurzel^.Wert > inPfadMax)
         else
            begin
               if (inRefWurzel^.Wert > inPfadMax) then
                     inPfadMax := inRefWurzel^.Wert;
               BlattMax := true;
               if (inRefWurzel^.links <> nil) then
                  BlattMax := BlattMax and BlattMax(inRefWurzel^.Links, inPfadMax);
               if (inRefWurzel^.rechts <> nil) then
                  BlattMax := BlattMax and BlattMax(inRefWurzel^.rechts, inPfadMax);
            end;   
      end;

Jetzt ist es so, dass dieses Programm bei mir lokal auch compiliert wird.
Allerdings muss ich die Aufgabe online in ein Portal hochladen und dort wird das ganze dann automatisch compiliert.

Hier meckert der Compiler dann wegen den folgenden beiden Zeilen:

Code:

BlattMax := BlattMax and BlattMax(inRefWurzel^.Links, inPfadMax);
BlattMax := BlattMax and BlattMax(inRefWurzel^.rechts, inPfadMax);

Soweit ich das beurteilen kann ist der Grund, weil die Funktion BlattMax hier ohne "Argument" aufgerufen wird? Also der Ausdruck vor dem "and", dass da keine Klammer mit Angaben hinter dem BlattMax steht?
Kann mir vielleicht jemand dazu mehr sagen, was da für ein Problem auftritt?

Ansonsten bin ich dann (Dank dem Tipp von Zacherl mit der unnötigen While-Schleife) auch auf meine eigene Lösung gekommen:

Code:

begin
  if (inRefWurzel^.links <> nil) or (inRefWurzel^.rechts <> nil) then
  {wir befinden uns nicht an einem Blatt}
  begin
    
    if inRefWurzel^.Wert > inPfadMax then
      inPfadMax := inRefWurzel^.Wert;
      {aktualisiert das Maximum des bisher durchlaufenen Pfades}

    if (inRefWurzel^.links = nil) and (inRefWurzel^.rechts <> nil) then
    {nur ein rechter Teilbaum existiert}
      BlattMax := BlattMax(inRefWurzel^.rechts, inPfadMax);  
      {setzt die Funktion dann auf wahr, wenn der rechte Teilbaum die Bedingung erfüllt, unter Berücksichtigung des aktuellen Pfadmaximums}

    if (inRefWurzel^.links <> nil) and (inRefWurzel^.rechts = nil) then
    {nur ein linker Teilbaum existiert}
      BlattMax := BlattMax(inRefWurzel^.links, inPfadMax);
      {setzt die Funktion dann auf wahr, wenn der linke Teilbaum die Bedingung erfüllt, unter Berücksichtigung des aktuellen Pfadmaximums}

    if (inRefWurzel^.links <> nil) and (inRefWurzel^.rechts <> nil) then
    {es existieren ein linker und ein rechter Teilbaum}
      BlattMax := (BlattMax(inRefWurzel^.links, inPfadMax)) and (BlattMax(inRefWurzel^.rechts, inPfadMax));
      {setzt die Funktion dann auf wahr, wenn der linke UND der rechte Teilbaum die Bedingung erfüllen, unter Berücksichtigung des aktuellen Pfadmaximums}

  end;

  if (inRefWurzel^.links = nil) and (inRefWurzel^.rechts = nil) then
  {wir haben ein Blatt erreicht}
  begin
    BlattMax := inRefWurzel^.Wert > inPfadMax;
    {setzt die Funktion auf wahr, wenn der Wert des Blattes größer ist, als das Pfadmaximum. Ansonsten wird die Funktion auf falsch gesetzt}
  end;
end;

Ist natürlich schon bedeutend länger, aber immerhin hat es auch funktioniert (für mich schonmal ein Erfolg) =)

[Michael II]

Delphi-Quellcode:

BlattMax := BlattMax and BlattMax(inRefWurzel^.Links, inPfadMax);

Ersetze BlattMax durch Result. Also so:

Delphi-Quellcode:

Result := Result and BlattMax(inRefWurzel^.Links, inPfadMax);

Nebenbei: Es ist seit vielen Jahren üblich das Resultat einer Funktion via Result zurückzugeben.


Und wie bereits erwähnt: Der Code ist cool, wenn die Kurzschlussauswertung [Standard] eingeschaltet ist (d.h. in Delphi "Vollständige Boolesche Auswertung = AUS" ist).

Wenn die Kurzschlussauswertung eingeschaltet ist, dann berechnet Delphi den Ausdruck

Delphi-Quellcode:

Result and BlattMax(inRefWurzel^.Links, inPfadMax);

immer von links nach rechts nur solange bis das Resultat bekannt ist. Wenn also Result=false ist, dann ist bereits klar, dass

Delphi-Quellcode:

false and BlattMax(inRefWurzel^.Links, inPfadMax);

immer false ist (0 and x ist immer 0), unabhängig vom Wert von

Delphi-Quellcode:

BlattMax(inRefWurzel^.Links, inPfadMax);

. Delphi berechnet also

Delphi-Quellcode:

BlattMax(inRefWurzel^.Links, inPfadMax);

nicht.

Falls aber "Vollständige Boolesche Auswertung = EIN" ist, rechnet Delphi immer auch

Delphi-Quellcode:

BlattMax(inRefWurzel^.Links, inPfadMax);

Es wird bei diesem Code dann immer der ganze Baum durchlaufen. Abhilfe: Code anpassen.


Der Hinweis zur Kurzschlussauswertung betrifft auch deine rekursive Funktion; genauer diese Zeile:

Zitat:

Result := (BlattMax(inRefWurzel^.links, inPfadMax)) and (BlattMax(inRefWurzel^.rechts, inPfadMax));

[Zacherl]

Zitat:

Zitat von Michael II

Nebenbei: Es ist seit vielen Jahren üblich das Resultat einer Funktion via Result zurückzugeben.

Stimmt, das wollte ich zu deinem Code auch noch angemerkt haben.

Falls dein Lehrer/Prof. deshalb nachfragen sollte, kannst du ihm ja die offensichtlichen Vorteile präsentieren. Auf das erste Problem der alternativen Schreibweise bist du ja schon von selbst gestoßen: Man kann der Funktion über den konkreten Namen zwar ein Ergebnis zuweisen, nicht aber das momentane Ergebnis nochmal abfragen. Zweiter Vorteil von

Delphi-Quellcode:

Result

: Du kannst die Funktion jederzeit umbenennen, ohne sämtliche Vorkommen von Rückgabewertzuweisungen ebenfalls ändern zu müssen.