Literatur

TreeSet

Ein weiterere Set-Klasse ist java.util.TreeSet. In diesem Set werden Objekte in einer Baumstruktur sortiert.

Zum besseren Verständnis wollen wir zunächst die Baumstruktur veranschaulichen:

Die oben abgebildete Baumstruktur besitzt drei Ebenen. Der Knoten in der ersten Ebene ist die Wurzel (root). Die Knoten in der zweiten Ebene werden als Äste (branches) bezeichnet, da sie noch Nachfolger haben. Die Knoten der dritten Ebene werden Blätter (leaves) genannt.

Da in dem obigen Bild jeder Vorgänger maximal zwei Nachfolger besitzt, spricht von von einem Binärbaum.

Alle Klassen, die in ein TreeSet eingefügt werden sollen, müssen das Interface Comparable und dessen Methode compareTo implementieren. Durch compareTo können Elemente miteinander verglichen werden. Damit ein Vergleich überhaupt möglich ist, müssen die Objekte im TreeSet vom selben Datentyp sein.

Schauen wir uns nun einmal folgende Beispielklasse an.

public class Punkt implements Comparable
{
    private int x;
  
    public int getX()
    {
        return x;
    }
   
    public void setX(int i)
    {
        x = i;
    }
 
    // Implementierte Methode aus dem Interface Comparable
    public int compareTo(Object compareObject)
    {
        // Rückgabewert
        int compareValue =-2;
        // Typumwandlung zur Klasse Punkt
        Punkt comparePunkt = (Punkt)compareObject;
        // Vergleich auf Gleichheit
        if(this.x == comparePunkt.getX())
        {
            compareValue = 0;
        }
        // Vergleich auf kleiner
        if(this.x < comparePunkt.getX())
        {
            compareValue = -1;
        }
        // Vergleich auf größer
        if(this.x > comparePunkt.getX())
        {
            compareValue = 1;
        }
        return compareValue;
    }
}

In dem obigen Beispiel haben wir unsere aus vorhergehenden Kapiteln bereits bekannte Klasse Punkt diesmal mit der Schnittstelle Comparable implementiert. Dadurch müssen wir die Methode compareTo implementieren. Da unsere Klasse Punkt nur ein einfaches Attribut x besitzt, kann man über den Wert dieses Attributs (gleich, größer oder kleiner) einfach  die Punkt-Objekte vergleichen. Die Implementierung der Methode compareTo ist natürlich abhängig davon, welche Objekte Sie vergleichen oder ablegen wollen.

Nun erstellen wir ein TreeSet, dem wir einige Punkte hinzufügen:

 
// neues TreeSet-Objekt    
TreeSet tree = new TreeSet();
// Fünf Punkte werden erzeugt  
Punkt p1 = new Punkt();
p1.setX(12);
Punkt p2 = new Punkt();
p2.setX(13);
Punkt p3 = new Punkt();
p3.setX(11);
Punkt p4 = new Punkt();
p4.setX(24);
Punkt p5 = new Punkt();
p5.setX(1);
Punkt p6 = new Punkt();
p6.setX(13);
 
// Punkte werden dem TreeSet hinzugefügt
tree.add(p1);
tree.add(p2);
tree.add(p3);
tree.add(p4);
tree.add(p5);
tree.add(p6);
 
System.out.println("Inhalt unseres TreeSets:");
 
Iterator it = tree.iterator();
 
while(it.hasNext())
{
      Punkt punkt = (Punkt) it.next();
      System.out.println(punkt.getX());
}
 

Hätten wir nicht das Interface Comparable innerhalb der Klasse Punkt implementiert, so wäre es nicht möglich, die Punkte dem TreeSet hinzuzufügen.

Wie Sie anhand der Ausgabe sehen werden, werden die Punkte im Tree nun absteigend nach Ihrem x-Wert ausgegeben. Wie Sie sehen, wird jedoch die "13" nur einmal ausgegeben, obwohl wir zwei Punkte mit einem x-Wert von 13 hinzugefügt haben. Dies liegt daran, dass beim Hinzufügen des sechsten Punktes über die compare-Funktion eine Gleichheit mit dem bereits vorhandenen Punkt festgestellt wird. Da in Sets jedoch jedes Element einzigartig sein soll, wird der Punkt nicht hinzugefügt.