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

[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]

BlattMax := BlattMax and BlattMax(inRefWurzel^.Links, inPfadMax); Ersetze BlattMax durch Result. Also so:
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
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 false and BlattMax(inRefWurzel^.Links, inPfadMax); immer false ist (0 and x ist immer 0), unabhängig vom Wert von BlattMax(inRefWurzel^.Links, inPfadMax); . Delphi berechnet also BlattMax(inRefWurzel^.Links, inPfadMax); nicht.

Falls aber "Vollständige Boolesche Auswertung = EIN" ist, rechnet Delphi immer auch 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 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 Result : Du kannst die Funktion jederzeit umbenennen, ohne sämtliche Vorkommen von Rückgabewertzuweisungen ebenfalls ändern zu müssen.