Thomas Kramer

IT-COW | All posts tagged 'Java'

Der Reingold-Tilford-Algorithmus

By Administrator at Mai 12, 2011 18:51
Filed Under: Algorithmen, Programmierung allgemein, Studium, Java

Mittlerweile habe ich für die Visualisierung eines binären Suchbaumes statt meinem eigenen Algorithmus den Reingold-Tilford-Algorithmus implementiert. Im Studium wurden weder Processing noch der Reingold-Tilford-Algorithmus thematisiert, aber ich fand das interessant.

 

Orientiert habe ich mich bei meiner Implementierung an der sehr guten Beschreibung dieser Seite: Link. Die derart erstellten Bäume sind viel platzsparender als mein zuerst verwendeter Algorithmus. 

 

Bitte die drei unten angefügten Bilder beachten - für die Zukunft könnte ich irgendwann vielleicht auch noch den Walker-Algorithmus behandeln, aber für den Moment werde ich es dabei belassen. Erst einmal zur Vorgehensweise des Reingold-Tilford-Algorithmus:

 

1. Alle Knoten mit Initialisierungswerten für den Versatz versehen - ausgehend von der Wurzel mit 0, für jeden linken Sohn jeweils um eins verringernd, für jeden rechten Sohn jeweils um eins erhöhend (preorder-Reihenfolge).

2. Alle Knoten postorder besuchen und für jeden Knoten die linke und rechte Kontur bestimmen - dabei so tief gehen, wie für beide Konturen noch Knoten existieren. Von beiden Konturen den Versatz an der Stelle merken.

3. Den zusätzlichen Versatz ausrechnen. Folgende Formel gilt: (Versatz_links-Versatz_rechts)+2. Ist das Ergebnis ungerade, wird noch eins aufaddiert. Anschließend durch zwei dividieren.

4. Diesen Wert dem gesamten linken Unterbaum des aktuellen Knotens als negative Zahl aufaddieren, dem rechten Unterbaum als positive Zahl.

5. Den niedrigsten Versatz im Baum bestimmen und allen Knoten im Baum+1 aufaddieren. Auf diese Weise erhält man die Spaltenzahl für jeden Knoten im Baum, oder anders formuliert die x-Koordinaten.

 

Bei Regel Nr. 5 hatte ich einen Fehler gemacht, ich war vom Wurzelknoten soweit wie möglich links traversiert und hatte dann diesen Knoten genommen - das muss aber nicht zwingend der niedrigste Wert sein. Das habe ich nun korrigiert.

 

Ich hatte außerdem noch einen weiteren Fehler gefunden, bei der Konturenberechnung. Für die linke Kontur war ich vom übergeordneten Knoten einmal nach links, und dann so weit wie möglich rechts gegangen und für die rechte Kontur entsprechend umgekehrt. In einem von zehn Fällen hatte ich dadurch aber sich im Baum kreuzende Kanten oder zwei verschiedene Knoten, die an die gleiche Stelle gezeichnet wurden – durch die Kanten (Verbindungslinien zwischen den Knoten) konnte man das erkennen.  Diese Vorgehensweise wird wohl bei ausbalancierten AVL-Bäumen meistens funktionieren.

 

Vielmehr gibt es dafür keinen vorgezeichneten Weg und man implementiert das besser rekursiv – man sucht für die linke Kontur den maximalen Versatz und für die rechte Kontur den minimalen Versatz – aber jeweils nur bis zu der Ebene, in der bei beiden Konturen Knoten existieren. Daher muss man zuerst ausgehend vom übergeordneten Knoten die minimale Tiefe beider Konturen berechnen und dann den größten Versatz im linken Unterbaum sowie den kleinsten Versatz im rechten Unterbaum - bis zu dieser Ebene - suchen. 

 

Dieser Vorgang wird wie gesagt postorder für jeden Knoten im Baum durchgeführt. Ich habe dafür die beiden neuen Funktionen finde_Max_Ebene und finde_Versatz implementiert.

 

Ich habe danach gerade ca. 25mal Graphen erzeugen lassen und keine Fehler mehr entdeckt. Von der Performance her kann man das noch optimieren, da so für die Tiefenberechnung der Konturen und anschließender Suche des Versatzes bis zu dieser Ebene jeder Teilbaum jeweils zweimal besucht wird - aber solange ich keine Bäume mit Millionen Knoten erzeuge sollte das irrelevant sein. Eventuell könnte man dafür die Tiefe der linken und rechten Kontur beim Einfügen der Knoten bereits speichern, müsste das dann aber auch beim Löschen eines Knotens berücksichtigen - Einfachheit und Fehlerfreiheit haben Vorrang vor Performance.

 

Übrigens nicht wundern das in den Bildern unten doch noch recht viel freier Platz im Baum vorhanden ist, der Reingold-Tilford-Algorithmus geht - aus den Regeln folgernd - bei der Versatz-Berechnung in ganzen Schritten vor und behält die Symmetrie der jeweiligen Äste bei.

 

Update 14.05.2011: Quellcode besser dokumentiert.

 

Update 15.05.2011: Nun ist meine Webseite auf Seite 1 der Suchergebnisse bei Google zu dem Thema, sowohl bei den deutschen (254 Ergebnisse) als auch bei den weltweiten (5930 Ergebnisse). Zumindest auf deutsch wird im Internet zu dem Thema - wie man sieht - wenig publiziert (in Wikipedia übrigens auch nicht).

 

Update 16.05.2011: Wieder neue Version erzeugt, Quellcode unten erneuert. Zur Veranschaulichung habe ich alle drei Traversierungsmodi (InOrder, PreOrder, PostOrder) implementiert - der Traversierungsmodus lässt sich im Quellcode festlegen, mit den +/- -Tasten kann in der gewünschten Reihenfolge durch den Baum gegangen werden, der aktuelle Knoten wird jeweils rot hervorgehoben.

 

Dafür habe ich ein Pointer-Array als Hilfskonstrukt hinzugezogen, da die Traversierung in den Rekursionsroutinen selbst zu schnell durchlaufen würde.

 

Update 01.11.2011: Quellcode dahingehend überarbeitet als das jede Routine nur einen Ausgang haben sollte sowie die min/max-Befehle von Processing eingesetzt um if-Abfragen einzusparen.

 

Update 28.12.2011: Es werden nun einmalige Zufallszahlen generiert. Dazu verwende ich ein HashSet, welches die Eigenschaft hat keine doppelten Einträge aufnehmen zu können. Dieses fülle ich solange mit Zufallszahlen bis seine Größe der eingestellten Anzahl Knoten entspricht.

 

Danach gehe ich mit einem Iterator durch die Datenmenge im Hashset und erzeuge jedes Mal einen neuen Knoten mit dieser Zufallszahl.

 

Daher sollten nun immer soviele Knoten erzeugt werden wie eingestellt, weil doppelte Zufallszahlen nun vermieden werden. Voraussetzung ist aber dass die eingestellte Anzahl Knoten kleiner als das Zufallszahlen-Intervall ist. Zu diesem Zweck führe ich nun ganz zu Beginn eine Sicherheitsabfrage durch. Damit die Geschwindigkeit nicht zu sehr leidet sollte das Zufallszahlen-Intervall natürlich deutlich größer als die Knotenanzahl sein.

 

Die Modulo-Abfrage wird nun bitweise mit dem &-Operator durchgeführt, weil das so schneller ist - und ich habe eine Menge redundanter Berechnungen in der Draw-Routine entfernt. Eine Laufzeitanalyse des RT-Algorithmus findet sich nun in dem anderen Beitrag: Link. Eventuell werde ich Weiterentwicklungen nur noch in dem anderen Beitrag durchführen.

 

Mittlerweile habe ich auch mit über einer Million Knoten getestet und kann mit Gewissheit sagen, dass bei der Berechnung des Korrektur-Versatzes nicht die abs()-Funktion benutzt werden muss.

 

Update 29.12.2011: Eine Kontrollfunktion hinzugefügt die überprüft ob bereits ein Knoten an die gleiche Position gezeichnet wurde, entsprechende Knoten rot hervorhebt und auf der Konsole ausgibt. Außerdem wird nun aus Geschwindigkeitsgründen eine Warnung ausgegeben, falls die Knotenanzahl nicht mindestens 20% kleiner als das Zufallszahlen-Intervall ist.

 

Nun habe ich auch die Geschwindigkeit des Algorithmus verbessert, indem ich die Tiefe des linken und rechten Unterbaumes jedes Knotens bereits beim Erzeugen der Knoten speichere - natürlich muss das dann aber auch beim Löschen von Knoten berücksichtigt werden, daher habe ich die Routine finde_Max_Ebene() vorerst drin gelassen. Leider funktioniert das nicht entsprechend bei der Findung des minimalen und maximalen Versatzes - für diesen Fall wäre Multithreading-Programmierung einmal angebracht.

 

Update 31.12.2011: Der minimale Versatz im Baum wird nun ebenfalls bereits beim Erzeugen der Knoten zwischengespeichert - als Pointer (Werte werden ja nachfolgend noch korrigiert). Dadurch wurde aber praktisch keine Performance-Verbesserung erreicht, da das auch nachträglich bereits sehr schnell bestimmt wurde.

 

Als weitere sinnvolle Verbesserung kann nun im Zentrierungsmodus der Fokus mit den Cursortasten verschoben bzw. gescrollt werden. Da es in Processing keine Scrollbalken gibt habe ich damit die bislang fehlende Möglichkeit, große Bäume vollständig anzuschauen, trotzdem erreicht.

 

Nach der Nutzung dieser Möglichkeit ist das Bild natürlich nicht mehr zentriert, mit der Backspace-Taste kann aber der Ausgangszustand wieder erreicht werden.

 

Diese Möglichkeit habe ich nur in dieser Variante eingebaut, da ich in der anderen Version wegen der Laufzeitmessungen das wiederholte Zeichnen im Zentrierungsmodus abschalten lasse.

 

Update 02.01.2012: Es kann ein vollständiger Rekursionsdurchlauf eingespart werden wenn die Regel Nr. 5. beim RT-Algorithmus direkt in der Zeichnen-Routine geschieht - beim erneuten Zeichnen darf es dann aber natürlich nicht erneut aufaddiert werden. Das habe ich heute umgesetzt, Quellcode unten aktualisiert.

 

In dieser Schrift der FH Köln zum RT-Algorithmus sind übrigens zwei verschiedene Testverfahren für Algorithmen erwähnt worden die ich noch nicht kannte - auch nicht vom Studium her - den Power- und den Ratio-Test. Hier steht mehr zu dem Thema, demnach wird der Ratio-Test einfach folgendermaßen gebildet:

 

Ratio Test = Ergebnis / Theorethischen Erwartungswert für die Laufzeit des Algorithmus

 

Weitere Links: Visualisierung

 

  • Algorithmen zur Visualisierung von Graphen: Link
  • Der Reingold-Tilford-Algorithmus: Link
  • Visualisierung sehr großer Graphen: Link
  • ViA: Visualisieren von Algorithmen: Link
  • Entwicklung und Implementierung einer interaktiven AVL-Animation: Link
  • Eine Diplomarbeit der Uni Passau zum Thema Graphen: Link
  • Ein PDF aus der FH Köln zum Thema Graphen: Link
  • Ein PDF der Uni Heidelberg zum Thema Graphen: Link

 

/************************************************************************************
             Visualisierung eines binären Suchbaumes in Processing
                 mithilfe des Reingold-Tilford-Algorithmus
                             von Thomas Kramer
                          Version 1.37 - 02.01.2012
 ************************************************************************************/


/* Konfiguration */
   int Baumelemente=10;
   /* wenn Zentrierung aktiviert wird, werden die Mausabfragen deaktiviert */
   boolean Zentrierung=true;
   /* Traversierung festlegen (für Zentrierungsmodus), 1=InOrder, 2=PreOrder, 3=PostOrder */
   int Traversierung=1;
  
   /* Zufallszahlen-Unter-/Oberwert festlegen */
   int unten=1;  
   int oben=65536;

   int AbstandOben=50;
   int AbstandLinks=10;
   int ZwischenAbstandOben=25;
   int ZwischenAbstandLinks=5;
   int Breite=150;
   int Hoehe=50;

   /* Farben festlegen (Schwarz, Weiss, Hintergrund-Farbe, Farbe für hervorgehobene Rahmen) */
   color c1 = color(0, 0, 0);
   color c2 = color(255, 255, 255);
   color c3 = color(193, 185, 185);
   color c4 = color(245, 7, 7);
/* Konfiguration-Ende */

public class tBaum
{
  /* in Inhalt wird der Zufallszahlen-Wert gespeichert */
  int Inhalt = 0;
  /* gibt die Ebene für jeden Knoten an */
  int Ebene = 0;
  /* Art gibt die Position des Knotens im Verhältnis zur Wurzel an
     -1 = linker Teilbaum, +1 = rechter Teilbaum */
 
  int Art = 0;
  int Versatz = 0;
 
  /* Pointer für das Traversieren */
  tBaum Vater = null;
  tBaum links = null;
  tBaum rechts = null;
 
  /* speichert die jeweilige Tiefe des linken und des rechten Unterbaumes */
  Integer linksEbenen = 0;
  Integer rechtsEbenen = 0;
};

/* weitere globale Variablen */
int Ebene=0;
int EbenenInsgesamt=0;
HashSet<Integer> Zufallszahlen = new HashSet<Integer>();
int[] ElementeProEbene=new int[Baumelemente+1];
tBaum Wurzel=null;
tBaum kleinster_Versatz=null;
tBaum groesster_Versatz=null;
tBaum aktueller_Knoten=null;
tBaum[] TraversierungsElemente=new tBaum[Baumelemente+1];
int Zaehler_Traversierung=0;
tBaum letzter_Knoten=null;

/* Variablen für das Zeichnen */
int MaxElemente = 0;
int MaxElementePlatz = 0;
int Breite_2 = Breite / 2;
int Hoehe_2 = Hoehe / 2;
int xVersatz = 0;
int yVersatz = 0;
int GesamtVersatz = 0;
boolean ausgegeben = false;

import java.util.HashMap;
import java.util.concurrent.TimeUnit;

void setup() {
  if (Baumelemente > abs(oben - unten))
    throw new IllegalArgumentException("Fehler! Es werden einmalige Zufallszahlen benötigt und die Anzahl Knoten ist größer als das Zufallszahlen-Intervall!");
   
  if ((Baumelemente * 1.2) > abs(oben - unten))
    println("Achtung, die Anzahl Baumknoten ist nicht mindestens 20% größer als das Zufallszahlen-Intervall, das kann die Geschwindigkeit deutlich herabsetzen!");

  /* Größe des Screens setzen */
  size(screen.width, screen.height);
 
  /* Bildschirm löschen */
  background(c3);
 
  /*-----------------------------------------------------------------------------
   *  einmalige Zufallszahlen erzeugen
   *-----------------------------------------------------------------------------*/
                   
  Zufallszahlen = new HashSet<Integer>();
  while (Zufallszahlen.size() < Baumelemente)
    Zufallszahlen.add((int) random(unten, oben));       

  /*-----------------------------------------------------------------------------
   *  Knoten erzeugen
   *-----------------------------------------------------------------------------*/
  
  int i = 0;
  Iterator it = Zufallszahlen.iterator();
 
  while (it.hasNext())
  {   
    if (i == 0)
    {
      Wurzel = Einfuegen(null, null, (Integer) it.next(), 0);     
      // Initialisierungswerte setzen
      kleinster_Versatz=Wurzel;
      groesster_Versatz=Wurzel;                     
    }
    else {
      Einfuegen(Wurzel, null, (Integer) it.next(), 0);
    }                       
   
    i++;
  }      

  /*-----------------------------------------------------------------------------
   *  Versatz berechnen
   *-----------------------------------------------------------------------------*/

  berechne_Versatz(Wurzel);
 
  /* kleinsten Versatz im Baum allen Knoten aufaddieren, danach hat man
     die konkrete Spaltenzahl (x-Koordinate) für jeden Knoten - beginnend mit 1 */

  GesamtVersatz=abs((kleinster_Versatz).Versatz)+1;
 
  /* das Aufaddieren geschieht jetzt direkt in der Zeichnen-Routine,
     dadurch wird aber ein Teil des RT-Algorithmus nicht mehr mitgemessen! */

  // setze_Wert(Wurzel, GesamtVersatz);   
 
  /*-----------------------------------------------------------------------------
   *  Variablen für das Zeichnen einmalig setzen
   *-----------------------------------------------------------------------------*/
    
  MaxElemente = (groesster_Versatz).Versatz + GesamtVersatz;
  MaxElementePlatz = (MaxElemente * Breite)+((MaxElemente - 1) * ZwischenAbstandLinks);         
 
  /*-----------------------------------------------------------------------------
   *  Traversierungsreihenfolge speichern
   *-----------------------------------------------------------------------------*/
 
  Zaehler_Traversierung=0;
  if (Traversierung==1)
  {
    InOrder_Traversierung(Wurzel);
  } else if (Traversierung==2) {
    PreOrder_Traversierung(Wurzel);     
  } else {
    PostOrder_Traversierung(Wurzel);
  }
  Zaehler_Traversierung=0;   

  /*-----------------------------------------------------------------------------
   *  Maus auf Mittelposition setzen (innerhalb des Fensters)
   *-----------------------------------------------------------------------------*/

  mouseX=(screen.width/2);
  mouseY=(screen.height/2);      
}

void draw()
{
  /*-----------------------------------------------------------------------------
   *  Hintergrundfarbe setzen, dabei wird auch der gesamte Bildschirm gelöscht
   *-----------------------------------------------------------------------------*/

  background(c3); 

  /*-----------------------------------------------------------------------------
   *  Überschriften setzen
   *-----------------------------------------------------------------------------*/

  fill(c2);
  textSize(20);
  text("Visualisierung eines binären Suchbaumes (Reingold-Tilford-Algorithmus) in Processing", ((screen.width)/2)-400, 50);
  textSize(15);
  text("von Thomas Kramer", ((screen.width)/2)-70, 80);
  text("(ESC zum Abbrechen)", ((screen.width)/2)-75, 110);
  textSize(13); 
 
  /*-----------------------------------------------------------------------------
   *  Baum grafisch ausgeben
   *-----------------------------------------------------------------------------*/

  ZeigeBaum(Wurzel, 0, 0);
  ausgegeben = true
 
  /*-----------------------------------------------------------------------------
   *  aktuelle Mauskoordinaten ausgeben
   *-----------------------------------------------------------------------------*/

  if (!Zentrierung)
  {
    fill(c3);
    rect(1, 0, 80, 60);
    fill(c2);
    text("x: " + mouseX, 20, 20);
    text("y: " + mouseY, 20, 40);
  }
}

void berechne_Versatz(tBaum Knoten)
{
  /* PostOrder-Druchlauf -> linker Teilbaum, rechter Teilbaum, Wurzel */
  if (Knoten!=null)
  {    
    berechne_Versatz(Knoten.links);                 
    berechne_Versatz(Knoten.rechts);     
    berechne_Konturen(Knoten);       
  }
}

void berechne_Konturen(tBaum Knoten)
{
   /* berechne Konturen, nur notwendig wenn aktueller Knoten zwei Söhne hat */  
  if (Knoten.links!=null && Knoten.rechts!=null)
  {
    int linke_Kontur=0;
    int rechte_Kontur=0;
  
    /* finde die maximalen Ebenen für die Unterbäume links und rechts, separat */
    /* übernimm davon den niedrigeren Wert */
    int minLevelinsgesamt=min(Knoten.linksEbenen, Knoten.rechtsEbenen);     
   
    /* bestimme den maximalen und minimalen Versatz jeder Kontur bis zu der bestimmten Ebene (einschließlich) */
    linke_Kontur  = finde_Versatz(Knoten.links, +1, minLevelinsgesamt, (Knoten.links).Versatz);   
    rechte_Kontur = finde_Versatz(Knoten.rechts, -1, minLevelinsgesamt, (Knoten.rechts).Versatz);                         
     
    /* Korrigierungs-Versatz berechnen */ 
    int Versatz=((linke_Kontur-rechte_Kontur))+2;  
    /* Ergebnis ist ungerade? */
    if ((Versatz & 1)!=0)
      Versatz+=1;
    /* Integer-Division */
    Versatz=(Versatz/2);
   
    /* Test-Ausgabe */
    if (Versatz <0)
      println("abs()-Funktion sollte doch verwendet werden!");
  
    /* diesen Versatz dem linken Teilbaum als negativen Wert aufaddieren, dem rechten Teilbaum
       als positiven Wert */

    setze_Wert(Knoten.links,Versatz*-1);
    setze_Wert(Knoten.rechts,Versatz);  
  }
}

/* berechne die Tiefe der jeweiligen Kontur des Knotens */
int finde_Max_Ebene(tBaum Knoten)
{
  if (Knoten == null)
    return 0;
   
  return max(finde_Max_Ebene(Knoten.links), finde_Max_Ebene(Knoten.rechts))+1;
}

/* finde den minimalen/maximalen Versatz für den jeweilig angegebenen
   Unterbaum (Kontur) heraus - bis zu einer bestimmten Ebene (einschließlich) */

int finde_Versatz(tBaum Knoten, int Richtung, int biszuEbene, int Versatz)
{
  int result=Versatz;
 
  if (Knoten!=null)
  {  
    /* Richtung: -1=suche Minimum, +1=suche Maximum */
    if (Richtung==-1)
    {
      result=min(Knoten.Versatz,result);
    } else
    {
      result=max(Knoten.Versatz,result);
    }  
  
    /* noch nicht in der letzten zu berücksichtigenden Ebene? */
    if (Knoten.Ebene<biszuEbene)
    {
      result=finde_Versatz(Knoten.links, Richtung, biszuEbene, result);
      result=finde_Versatz(Knoten.rechts, Richtung, biszuEbene, result);
    }  
  }
 
  return result;
}

/* addiere den nach der Formel korrigierten Versatz jedem einzelnen
   Knoten der angegebenen Kontur auf */

void setze_Wert(tBaum Knoten, float Wert)
{
  if (Knoten!=null)
  {
    Knoten.Versatz+=Wert;
 
    setze_Wert(Knoten.links,Wert);
    setze_Wert(Knoten.rechts,Wert);  
  }
}

/* Einfügen der Knoten, Position wird in der Routine selbst bestimmt */
tBaum Einfuegen(tBaum Knoten, tBaum Vater, int Inhalt, int Versatz)
{
  if (Knoten==null)
  {
    /* angegebener Knoten existiert noch nicht (Position noch nicht belegt)
       --> neuen Knoten erzeugen */

  
    Knoten = new tBaum();
    Knoten.Vater = Vater;
    Knoten.links = null;
    Knoten.rechts = null;
    Knoten.Inhalt = Inhalt;
    Knoten.Ebene = Ebene+1;
    Knoten.linksEbenen = Knoten.Ebene;
    Knoten.rechtsEbenen = Knoten.Ebene;   
    /* Versatz mit Initialisierungswerten versehen */
    Knoten.Versatz = Versatz;
    if ((Ebene+1)>EbenenInsgesamt)
      EbenenInsgesamt=(Ebene+1);
  
    /* Position im Baum abhängig zur Wurzel bestimmen */
    Knoten.Art=0;  
    if (Wurzel!=null)
    {
      Knoten.Art=(Inhalt<Wurzel.Inhalt) ? -1 : +1;
     
      /* kleinsten/größten Versatz bestimmen */
      if (Knoten.Versatz < (kleinster_Versatz).Versatz)
        kleinster_Versatz = Knoten;
      if (Knoten.Versatz > (groesster_Versatz).Versatz)
        groesster_Versatz = Knoten;                
    }
     
    letzter_Knoten = Knoten;
  } else
  {
    Ebene+=1;
    if (Inhalt < Knoten.Inhalt)
    { /* kleineren Wert als den des aktuellen Knotens immer als linken Sohn einfügen */                 
      Knoten.links = Einfuegen(Knoten.links, Knoten, Inhalt, Versatz-1);  
      Knoten.linksEbenen = max(Knoten.linksEbenen, letzter_Knoten.Ebene);        
    }
    else if (Inhalt > Knoten.Inhalt)
    { /* größeren Wert als den des aktuellen Knotens immer als rechten Sohn einfügen */  
      Knoten.rechts = Einfuegen(Knoten.rechts, Knoten, Inhalt, Versatz+1);
      Knoten.rechtsEbenen = max(Knoten.rechtsEbenen, letzter_Knoten.Ebene);       
    }  
    Ebene-=1;
  }
 
  /* gib den aktuellen Knoten zurück */
  return Knoten;
}

/* Baum visuell ausgeben */
void ZeigeBaum(tBaum Knoten, int StartPosKanteLinks, int StartPosKanteOben)
{
  if (Knoten == null)   
    return;        
   
  if (!ausgegeben)
  {
    Knoten.Versatz += GesamtVersatz;
  }

  int GesamtPositionLinks = 0;
  int GesamtPositionLinks_2 = 0;
  int GesamtPositionOben = 0; 
  int GesamtPositionOben_2 = 0;
  int Zentri_Space = 0;
  int BenutzteFelder = (Knoten.Versatz - 1 ) * (Breite + ZwischenAbstandLinks);
  boolean Fehler = false;
 
  if (Zentrierung)
  {
    Zentri_Space = (screen.width - AbstandLinks - MaxElementePlatz) / 2;
    GesamtPositionLinks = Zentri_Space + AbstandLinks + BenutzteFelder + xVersatz;  
    GesamtPositionOben=AbstandOben + (Knoten.Ebene * Hoehe) + (Knoten.Ebene * ZwischenAbstandOben) + yVersatz;
  }
  else {
    GesamtPositionLinks=((screen.width / 2) - mouseX) - AbstandLinks + BenutzteFelder;
    GesamtPositionOben=((screen.height / 2) - mouseY) - AbstandOben + (Knoten.Ebene * Hoehe) + (Knoten.Ebene * ZwischenAbstandOben);
  }
  GesamtPositionLinks_2 = GesamtPositionLinks + Breite_2;
  GesamtPositionOben_2 = GesamtPositionOben + Hoehe_2;

  /* wird nur ausgeführt, wenn Zentrierung aktiviert */
  if (Zaehler_Traversierung>0)
  {
    fill(c1);
    if (Traversierung==1)
      text("InOrder-Traversierung (L,W,R)",50,50);
    if (Traversierung==2)
      text("PreOrder-Traversierung (W,L,R)",50,50);
    if (Traversierung==3)
      text("PostOrder-Traversierung (L,R,W)",50,50);     
  }
 
  /* Erkennen, ob schon ein Knoten an die Stelle gezeichnet wurde */
  color cp = get(GesamtPositionLinks + 1, GesamtPositionOben + 1);
  if (cp == c2)
  {
    println("Fehler! Es wurde schon ein Knoten an diese Stelle gezeichnet!");
    println("betreffend Knoten: " + Knoten.Inhalt);
   
    Fehler = true;
  }

  /* Rahmen zeichnen */
  if ((Knoten==TraversierungsElemente[Zaehler_Traversierung]) || (Fehler))
    fill(c4);
  else
    fill(c2);  
  rect(GesamtPositionLinks,
  GesamtPositionOben,
  Breite,
  Hoehe);

  /* Inhalte einzeichnen */
  fill(c1);          
  text(Knoten.Ebene+". Ebene=" +Knoten.Inhalt + ", " + Knoten.Versatz,
  GesamtPositionLinks + 5,
  GesamtPositionOben + 15);
  line(GesamtPositionLinks,
  GesamtPositionOben_2,
  GesamtPositionLinks + Breite,
  GesamtPositionOben_2);
  line(GesamtPositionLinks_2,
  GesamtPositionOben_2,
  GesamtPositionLinks_2,
  GesamtPositionOben + Hoehe);      
  if (Knoten.links != null)
    text((Knoten.links).Inhalt,
    GesamtPositionLinks + 5,
    GesamtPositionOben_2 + 15);             
  if (Knoten.rechts!=null)
    text((Knoten.rechts).Inhalt,
    GesamtPositionLinks_2 + 5,
    GesamtPositionOben_2 + 15);                  
  if (Knoten.Ebene != 1)
    line(StartPosKanteLinks, StartPosKanteOben, GesamtPositionLinks_2, GesamtPositionOben);  

  /* Rekursionsaufrufe */
  if (Knoten.links != null
    ZeigeBaum(Knoten.links, GesamtPositionLinks_2, GesamtPositionOben + Hoehe);
  if (Knoten.rechts != null)   
    ZeigeBaum(Knoten.rechts, GesamtPositionLinks_2, GesamtPositionOben + Hoehe);             
}

void keyPressed()
{
  if (Zentrierung)
  {
    if (key=='+')
    {
      if (Zaehler_Traversierung<Baumelemente)       
        Zaehler_Traversierung+=1; 
    }
    if (key=='-')   
    {
      if (Zaehler_Traversierung>1)     
        Zaehler_Traversierung-=1;     
    }
    if (key=='0')
      Zaehler_Traversierung=1;
     
    if (keyCode == RIGHT)
    {
      xVersatz -= 1;
    } else if (keyCode == LEFT)
    {
      xVersatz += 1;
    } else if (keyCode == UP)
    {
      yVersatz += 1;
    } else if (keyCode == DOWN)
    {
      yVersatz -= 1;
    } else if (keyCode == BACKSPACE)
    {
      xVersatz = 0;
      yVersatz = 0;
    }     
  }
}

void InOrder_Traversierung(tBaum Knoten)
{
  /* L,W,R */
  if (Knoten==null)
    return;
 
  InOrder_Traversierung(Knoten.links);
 
    Zaehler_Traversierung+=1;
    TraversierungsElemente[Zaehler_Traversierung]=Knoten;   
   
  InOrder_Traversierung(Knoten.rechts);      
}

void PreOrder_Traversierung(tBaum Knoten)
{
  /* W,L,R */
  if (Knoten==null)
    return;

  Zaehler_Traversierung+=1;
  TraversierungsElemente[Zaehler_Traversierung]=Knoten; 
 
  PreOrder_Traversierung(Knoten.links);
  PreOrder_Traversierung(Knoten.rechts);      
}

void PostOrder_Traversierung(tBaum Knoten)
{
  /* L,R,W */
  if (Knoten==null)
    return;
 
  PostOrder_Traversierung(Knoten.links);
  PostOrder_Traversierung(Knoten.rechts);      
 
  Zaehler_Traversierung+=1;
  TraversierungsElemente[Zaehler_Traversierung]=Knoten;   
}

 

Untitled1

Untitled2

Untitled3

 

Tag-Wolke

Monats-Liste