fork(6) download
copy 
  1. program TesteBlattMax (input, output);
  2.  
  3.  
  4.   type
  5.   tNatZahl = 1..maxint;
  6.   tRefBinBaum = ^tBinBaum;
  7.   tBinBaum = record
  8.                Wert:tNatZahl;
  9.                links:tRefBinBaum;
  10.                rechts:tRefBinBaum
  11.              end;
  12.  
  13.   var
  14.   Wurzel : tRefBinBaum;
  15.   blaetterSindMax : Boolean;
  16.  
  17.   function BlattMax ( inRefWurzel : tRefBinBaum;
  18.                         pfadMax : tNatZahl) : Boolean;
  19.   { prüft ob alle Blätter des Baumes die Maxima der Pfade zu ihnen sind }
  20.   { pfadMax uebergibt das jeweilige aktuelle Maxium aller [Knoten]^.Wert
  21.   * auf dem Weg zum Blatt an. [Blatt]^.Wert wird schliesslich mit 
  22.   * pfadMax verglichen, und wenn [Blatt]^.Wert >= pfadMax gibt die 
  23.   * function den Wert true zurueck. Beim ersten Aufruf der function
  24.   * (aus dem programm) muss pfadMax mit dem Wert inRefWurzel]^.Wert
  25.   * uebergeben werden oder aber dem kleinsten Wert tNatZahl = 1.
  26.   * Nebenbei: nach Muss Regel 9 muesste pfadMax eigentlich inPfadMax
  27.   * heissen }
  28.  
  29.       var
  30.     WegMax : tNatZahl;
  31.     BlattIstMax,
  32.     BlattIstMaxLinks,
  33.     BlattIstMaxRechts : boolean;
  34.  
  35.   begin    
  36.     WegMax := pfadMax;
  37.     if (inRefWurzel^.links = nil) and (inRefWurzel^.rechts = nil) then
  38.     begin { Blatt erreicht, Funktionswert für Blatt bestimmen }
  39.       if inRefWurzel^.Wert < WegMax then
  40.         BlattIstMax := false
  41.       else
  42.         BlattIstMax := true
  43.     end { Blatt getestet, Funktionswert für Blatt bestimmt }   
  44.     else
  45.     begin { Blatt nicht erreicht }
  46.       { Test ob aktueller Knoten das Maximum ist }
  47.       if inRefWurzel^.Wert > WegMax then
  48.         WegMax := inRefWurzel^.Wert;
  49.       { Unterbaeume testen, wenn sie existieren }  
  50.         if (inRefWurzel^.links <> nil) then
  51.           BlattIstMaxLinks := BlattMax(inRefWurzel^.links, WegMax);
  52.         if (inRefWurzel^.rechts <> nil) then
  53.           BlattIstMaxRechts := BlattMax(inRefWurzel^.rechts, WegMax);
  54.       { Kombination der Funktionswerte der Teilbaeume }
  55.       BlattIstMax := BlattIstMaxLinks and BlattIstMaxRechts    
  56.     end; { Blatt nicht erreicht }
  57.     BlattMax := BlattIstMax { Funktionswert uebergeben }
  58.   end; { BlattMax }
  59.  
  60.   procedure BaumAufbauen (var outWurzel : tRefBinBaum) ;
  61.  
  62.   var 
  63.     index,
  64.     Zahl : integer;
  65.     elter, neuerKnoten : tRefBinBaum;    
  66.  
  67.   function KnotenVonIndex (baum : tRefBinBaum; index : integer) : tRefBinBaum;
  68.  
  69.     var
  70.       elter : tRefBinBaum;
  71.     begin
  72.       if (index = 1) then
  73.         KnotenVonIndex := baum
  74.       else
  75.       begin
  76.         elter := KnotenVonIndex(baum, index div 2);
  77.         if ( (index mod 2 ) = 0 ) then
  78.           KnotenVonIndex := elter^.links
  79.         else
  80.           KnotenVonIndex := elter^.rechts
  81.       end;
  82.     end;
  83.  
  84.   begin
  85.     read (index);
  86.     new (outWurzel);
  87.     read (Zahl);
  88.     outWurzel^.Wert := Zahl;
  89.     read (index);
  90.     while (index <> 0) do
  91.     begin            
  92.       elter := KnotenVonIndex(outWurzel, index div 2);
  93.       new (neuerKnoten);
  94.       read (Zahl);    
  95.       neuerKnoten^.Wert := Zahl;  
  96.       if ( (index mod 2 ) = 0 ) then
  97.         elter^.links := neuerKnoten
  98.       else
  99.         elter^.rechts := neuerKnoten;
  100.       read (index);      
  101.     end;    
  102.   end; { BaumAufbauen }
  103.  
  104. begin
  105.   writeln('Bitte Baum in level-order eingeben Eingabeformat: Immer erst der Index eines Knotens, dann dessen Wert:');
  106.   BaumAufbauen (Wurzel);
  107.   blaetterSindMax := BlattMax(Wurzel, 1);
  108.   if blaetterSindMax then
  109.     writeln ('Alle Blaetter sind groesser als alle Knoten auf den jeweiligen Pfaden zu ihnen.')
  110.   else
  111.     writeln ('Mind. ein Blatt ist nicht groesser als alle Knoten auf seinem Pfad.');
  112. end. { TesteBBKnotenzahl }
  113.  
Success #stdin #stdout 0s 264KB
comments (?)
stdin
copy 
1
11
2
5
3
8
4
13
5
12
7
14
0
stdout
copy 
Bitte Baum in level-order eingeben Eingabeformat: Immer erst der Index eines Knotens, dann dessen Wert:
Alle Blaetter sind groesser als alle Knoten auf den jeweiligen Pfaden zu ihnen.
https://ideone.com/IYbPKO
language:
Pascal (fpc 3.0.4)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!