Bäume

Bäume sind abstrakte Datenstrukturen zur Darstellung hierarchischer Beziehungen. Sie bestehen aus Knoten und Kanten zwischen den Knoten. Der oberste Knoten heißt Wurzelknoten, Knoten ohne Kindknoten heißen Blattknoten, dazwischenliegende Knoten sind gleichzeitig Kind- und Elternknoten. Bäume erweitern das Konzept der Liste: Während ein Listenknoten maximal einen Nachfolger hat, kann ein Baumknoten mehrere Nachfolger besitzen.

info

Unter der Tiefe eines Knotens versteht man die Länge des Pfades vom Knoten bis zum Wurzelknoten, unter der Höhe eines Baumes die maximale Tiefe eines seiner Knoten und unter dem Grad eines Knotens die Anzahl seiner Kindknoten.

Binärbäume

Bei Binärbäumen hat jeder Knoten maximal zwei Nachfolger. Hat jeder innere Knoten genau zwei Kinder, spricht man von einem vollen Binärbaum. Haben dabei alle Blattknoten dieselbe Tiefe, heißt er vollständiger Binärbaum.

Traversierung von Bäumen

Unter Traversierung versteht man das systematische Durchlaufen aller Knoten eines Baumes. Anders als bei Listen, wo die Reihenfolge eindeutig ist, gibt es bei Bäumen mehrere sinnvolle Durchlaufreihenfolgen:

• Beim Tiefendurchlauf wird ausgehend vom Wurzelknoten zuerst der linke, dann der rechte Teilbaum rekursiv besucht.
• Beim Breitendurchlauf werden alle Knoten ebenenweise von oben nach unten besucht.

Binäre Suchbäume in Java

Java verwendet binäre Suchbäume intern in den Klassen TreeSet<E> und TreeMap<K, V>. Ein binärer Suchbaum hält seine Elemente stets sortiert: Jeder Knoten ist größer als alle Knoten im linken Teilbaum und kleiner als alle Knoten im rechten Teilbaum. Dadurch ist die Suche, das Einfügen und das Löschen in 𝒪(log 𝑛) möglich.

Damit TreeSet und TreeMap Elemente vergleichen können, muss die gespeicherte Klasse entweder Comparable<T> implementieren oder beim Erzeugen der Sammlung ein Comparator<T> übergeben werden (siehe Komparatoren).

MainClass.java

public class MainClass {

   public static void main(String[] args) {
      TreeSet<Integer> numbers = new TreeSet<>();
      numbers.add(6);
      numbers.add(2);
      numbers.add(8);
      numbers.add(1);
      numbers.add(4);

      // Ausgabe erfolgt aufsteigend sortiert: 1 2 4 6 8
      numbers.forEach(System.out::println);
   }

}