Implementation binärer Suchbäume

Eine Klasse Element

Jetzt wird es wieder einmal Zeit, sich an den Computer zu setzen und ein bisschen praktisch zu arbeiten. Als erstes programmieren wir uns eine Klasse Element oder Knoten, und zwar auf die einfache Weise ohne Datenkapselung, also mit öffentlich (public) zugänglichen Attributen:

public class Element
{
   public int value;
   public Element left, right;

   public Element(int n)
   {
      value = n;
      left = null;
      right = null;
   }
   
   public void show()
   {
      System.out.println(""+value);
   }
}

Diese Klasse speichert nur int-Zahlen. Meistens möchte man aber Objekte in einem Binärbaum speichern, dann müsste man den Datentyp int durch den Datentyp Object ersetzen, und eine show-Methode wäre dann nicht mehr möglich, da die Klasse Element ja keine Vor-Ahnung davon hätte, auf welche Weise die Elemente angezeigt werden sollen. Beschränkt man sich dagegen auf int-Zahlen (oder einen anderen gängigen Datentyp wie zum Beispiel String), dann kann man natürlich die Klasse Element mit einer einfachen show-Methode ausstatten.

Auf die Datenkapselung verzichten wir hier, um später den Zugriff auf die einzelnen Attribute wie left und right zu vereinfachen. Sonst müssten wir eigene sondierende Methoden schreiben - was an sich ja das korrekte Vorgehen wäre.

Eine Klasse BuildTree

Zum Testen unserer Element-Klasse programmieren wir eine Klasse BuildTree, deren einzige Aufgabe es ist, aus drei Objekten der Klasse Element einen binären Suchbaum zu erstellen. Hier der vollständige Quelltext dieser Klasse:

public class BuildTree
{
   Element root;

   public BuildTree()
   {
      root = new Element(100);
      root.left = new Element(50);
      root.right = new Element(150);   
   }
}

Nun schauen wir uns mit dem Objektinspektor den erzeugten Baum einmal an. Der Baum wurde in der Tat genau so aufgebaut, wie es beabsichtigt wurde. Die Wurzel hat den Wert 100, der linke Nachfolger den Wert 50, und der rechte Nachfolger den Wert 150.

Hier sehen wir einen Screenshot mit vier Fenstern des BlueJ-Objektinspektors.

Anfangen können wir mit der Klasse BuildTree allerdings noch viel; die Klasse soll nur demonstrieren, wie man mit recht einfachen Java-Mitteln einen binären Baum aufbauen kann. Viel sinnvoller wäre es, wenn man eine Java-Klasse BinTree hätte, die einen echten binären Suchbaum implementiert, der neue Elemente automatisch in den vorhandenen Baum einfügt.