Problemstellung
Es soll ein binärer Suchbaum implementiert werden, in dem Objekte aller möglichen Klassen gespeichert werden können, also nicht nur int-Zahlen wie in der Folge 17 des Q1-Lehrgangs, sondern Objekte jeder denklichen Art.
Hier zunächst das BlueJ-Klassendiagramm eines solchen Projektes:
Das BlueJ-Klassendiagramm
Der Code für den eigentlichen Binärbaum steckt in der Klasse BinTree. Die Klasse BinTreeTest erzeugt eine Reihe von Objekten der Klasse Bruch und speichert diese in dem BinTree.
Ein binärer Suchbaum besteht aus vielen Knoten oder Elementen. Auch die Wurzel des Baums ist ein solches Element. Die Implementierung dieser Knoten oder Elemente erfolgt mit der Klasse Element. Diese hat hauptsächlich drei Attribute, nämlich den eigentlichen Wert sowie einen Zeiger auf den linken Nachfolger und einen Zeiger auf den rechten Nachfolger. Der eigentliche Wert ist hier keine int-Zahl (so wie in der Folge 17), sondern ein Objekt der Klasse Item. Dies ist nun eine ganz wichtige Klasse. Während man in einer Datenstruktur wie Stack, Queue oder List ganz einfach beliebige Objekte speichern kann, ist dies bei einem binären Suchbaum nicht möglich. Der Grund: Beim Einfügen in den Suchbaum müssen die neuen Elemente mit der Wurzel des Baumes verglichen werden. Ist der Wert des neuen Elementes kleiner als der Wert der Wurzel, wird das neue Element in den linken Unterbaum der Wurzel eingefügt, andernfalls in den rechten Unterbaum. Die Elemente müssen also vergleichbar sein (engl.: comparable). Aus diesem Grund erbt die Klasse Item bestimmte Methoden von der Klasse Comparable, zum Beispiel die Methode isLess. Gleichzeitig sollen die Knoten des Baumes ausgegeben werden können, also in der Konsole angezeigt werden können. Dazu benötigen sie eine Eigenschaft, die man als druckbar (engl.: printable) bezeichnen kann. Die Objekte der Klasse Item müssen auch diese Eigenschaft besitzen.
Nun gibt es in Java leider keine Möglichkeit der direkten Mehrfachvererbung, wie es zum Beispiel in C++ der Fall ist. Aber in Java hat man sich geholfen und die Interface-Technik entwickelt. Diese Interface-Technik erlaubt eine Art Mehrfachvererbung. So erbt die Klasse Item mehrere Methoden von dem Interface Comparable und mehrere Methoden von dem Interface Printable.
Implementation
Kommen wir nun zu den einzelnen Klassen.
BinTree
public class BinTree
{
Element root;
public BinTree(Item v)
{
root = new Element(v);
}
public void insert(Item v)
{
root = insertR(v,root);
}
public Element insertR(Item v, Element tree)
{
if (tree==null)
tree = new Element(v);
else if (v.isGreater(tree.value))
tree.left = insertR(v,tree.left);
else
tree.right = insertR(v,tree.right);
return tree;
}
public void show()
{
showR(root);
}
private void showR(Element p)
{
if (p != null)
{
showR(p.left);
p.show();
showR(p.right);
}
}
}
Der Quelltext dieser Klasse entspricht weitgehend dem, was wir in der Folge 17 des Q1-Kurses kennengelernt haben. Zur insert-Methode siehe Folge 17.4, und zur show-Methode siehe Folge 17.6. Allerdings sind die Werte, die in den Elementen des Baums gespeichert werden, keine einfachen int-Zahlen, wie in der Folge 17, sondern Objekte einer Klasse Item.
Hätten wir einen Stack oder eine Queue implementiert, so könnte man stattdessen auch einfach Objekte der Klasse Object verwenden. Die Reihenfolge des Einfügens ist bei einem Stack oder einer Queue per Definition vorgegeben; die Werte müssen dabei nicht verglichen werden. Siehe hierzu auch "Die Implementierung eines universellen Stacks" in der Folge 14.3.
Bei einem binären Suchbaum dagegen müssen Werte, die kleiner als die jeweilige Wurzel sind, in den linken Teilbaum eingefügt werden, und ansonsten in den rechten. Die Werte müssen also verglichen werden können. Dazu muss ein Objekt der Klasse Item Vergleichsoperationen zur Verfügung stellen. In unserer insertR-Methode wird konkret die Operation isGreater der Klasse Item genutzt.
Zurück zur Übersicht der Klassen
Die Klasse Element
Der binäre Suchbaum besteht aus einer endlichen Anzahl von Knoten, die in diesem Projekt als Elemente bezeichnet werden (ähnlich wie Arrayelemente oder Stackelemente).
public class Element
{
public Item value;
public Element left, right;
public Element(Item n)
{
value = n;
left = null;
right = null;
}
public void show()
{
value.println();
}
}
Ein Baumelement besteht aus dem eigentlichen Wert und zwei Referenzen (Zeigern) auf den linken und auf den rechten Nachfolger. Der Konstruktor erzeugt eine neues Baumelement und nimmt dabei den zu speichernden Wert als Parameter in Empfang. Die left- und right-Zeiger werden zunächst auf null gesetzt. Die show-Methode macht nichts anderes, als das Anzeigen an die show-Methode des Element-Objektes value zu delegieren.
Zurück zur Übersicht der Klassen
Die Klasse Item
Schauen wir uns nun die Klasse Item näher an. Sie ersetzt ja die simple int-Zahl, die wir bei der Einführung des Themas "binärer Suchbaum" in der Folge 17 noch verwendet hatten.
public class Item implements Comparable, Printable
{
public double getValue()
{
return 0;
}
public boolean isLess(Comparable c)
{
return c.getValue() < getValue();
}
public boolean isEqual(Comparable c)
{
return c.getValue() == getValue();
}
public boolean isGreater(Comparable c)
{
return c.getValue() > getValue();
}
public void println()
{
}
public void print()
{
}
}
Auffällig ist in der ersten Zeile, dass hier zwei Interfaces benutzt werden, nämlich Comparable und Printable. Die Interface-Technik ist ja ein Mittel, Mehrfachvererbung in Java zu realisieren. Tatsächlich "erbt" die Klasse Item die ersten vier Methoden von der Klasse Comparable und die beiden letzten Methoden von der Klasse Printable. Allerdings handelt es sich hierbei um keine echte Vererbung. Bei einer echten Vererbung würde die Tochterklasse nämlich auch die Implementation der Methoden erben. Bei der Interface-Technik werden lediglich die Signaturen der Methoden vererbt; die Tochterklasse erhält aber keine Implementation von den Mutterklassen, sondern muss diese selbst leisten.
Die die Klasse Item noch keine Kenntnis darüber hat, durch welche "echte" Klasse sie später mal ersetzt wird, kann auch noch keine getValue-Methode implementiert werden. Item weiß ja noch gar nicht, dass sie in unserem Projekt durch ihre Tochterklasse Bruch ersetzt wird, bei der man den Wert der Elemente durch die Division zaehler/nenner erhält.
Das Gleiche gilt für die beiden Ausgabe-Methoden println und print. Item hat keine Kenntnis darüber, welche ihrer späteren Tochterklassen tatsächlich eingesetzt wird, daher kann Item nur eine leere Implementation der beiden Methoden liefern.
Die drei genannten Methoden, also getValue, println und print, hätte man jetzt vielleicht als abstrakte Methoden deklarieren können; dann wäre jede Tochterklasse gezwungen, diese Methoden konkret zu überschreiben.
Zurück zur Übersicht der Klassen
Die Interfaces
public interface Comparable
{
public boolean isLess(Comparable c);
public boolean isEqual(Comparable c);
public boolean isGreater(Comparable c);
public double getValue();
}
public interface Printable
{
public void println();
public void print();
}
In einem Interface werden nur die Signaturen der Methoden aufgelistet, die später einmal implementiert werden sollen. Comparable stellt drei Vergleichs-Methoden zur Verfügung sowie eine Methode zur Ermittlung eines Zahlenwertes. Printable stellt zwei Methoden zur Ausgabe von Werten in die Konsole zur Verfügung, die auch noch implementiert werden müssen.
Theoretisch hätte man alle sechs Methoden in ein Interface packen können. Ich wollte mit diesem Beispiel aber zeigen, dass eine Klasse wie Item von zwei Mutterklassen gleichzeitig erben kann, um das Prinzip der Mehrfachvererbung zu demonstrieren.
Zurück zur Übersicht der Klassen
Die Klasse Bruch
Kommen wir nun endlich zu der Klasse Bruch. Das ist die Klasse, die tatsächlich in den binären Suchbaum eingefügt werden soll.
public class Bruch extends Item
{
int zaehler, nenner;
public Bruch(int pZaehler, int pNenner)
{
zaehler = pZaehler;
nenner = pNenner;
}
public double getValue()
{
double z,n;
z = (double) zaehler * 1.0;
n = (double) nenner * 1.0;
return z/n;
}
public void println()
{
System.out.println(zaehler+"/"+nenner+"\t = "+getValue());
}
public void print()
{
}
}
Die Methode getValue ist etwas komplexer geworden, als ich zunächst gedacht hatte. Wenn man zwei int-Zahlen dividiert, erhält man wieder eine int-Zahl, da eine ganzzahlige Division durchgeführt wird. Also habe ich die beiden Attribute zaehler und nenner zunächst in double-Variablen z und n überführt, mit denen dann die Division z/n durchgeführt wird, um eine double-Zahl zu erhalten. Vielleicht wäre es auch einfacher gegangen, darüber will ich jetzt gar nicht weiter nachdenken...
Die println-Methode der Mutterklasse Item wurde von Bruch überschrieben, und die print-Methode wurde nicht weiter vervollständigt, weil sie in unserem Projekt nicht benötigt wird.