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;