2. Baumstrukturen
Bäume gehören zu den wichtigsten Datenstrukturen der Informatik. Sie finden Anwendung in vielen Bereichen, z.B. als Suchbäume zum schnellen Finden von Elementen in geordneten Mengen.
Binärbaum
Der Binärbaum wird in der Regel als rekursive Datenstruktur betrachtet: Ein Binärbaum besteht demnach aus einem Element (genauer einem Objekt einer zuvor festgelegten Klasse), einem linken und einem rechten Teilbaum. Eine Ordnung ist für einen Binärbaum nicht erforderlich.
Einen Binärbaum aufbauen
Für ein erstes Beispiel soll der folgende Baum aufgebaut werden:
Zur Vereinfachung wird als Grundklasse für den Baum die Klasse String definiert, d.h. die Elemente des Beispielsbaums werden als Zeichenketten gespeichert. Sicherlich wäre eine Modellierung als Zahl naheliegend, doch dann wäre der Einsatz der Wrapper-Klasse Integer (vgl. Abschnitt Objekte als Datenspeicher) oder der Entwurf einer neuen Klasse erforderlich.
Der folgende Quellcode baut den Baum bottom-up (d.h. von unten nach oben) auf. Eine andere Vorgehensweise ist nicht möglich, da beispielsweise der Gesamtbaum (vgl. Element 23) nur dann erzeugbar ist, wenn linker und rechter Teilbaum (vgl. Elemente 17 und 38) bereits existieren.
BinaryTree<String> k5 = new BinaryTree<String>("5");
BinaryTree<String> k14 = new BinaryTree<String>("14");
BinaryTree<String> k13 = new BinaryTree<String>("13",k5,k14);
BinaryTree<String> k19 = new BinaryTree<String>("19");
BinaryTree<String> k17 = new BinaryTree<String>("17",k13,k19);
BinaryTree<String> k39 = new BinaryTree<String>("39");
BinaryTree<String> k40 = new BinaryTree<String>("40",k39,null);
BinaryTree<String> k24 = new BinaryTree<String>("24");
BinaryTree<String> k38 = new BinaryTree<String>("38",k24,k40);
tree = new BinaryTree<String>("23",k17,k38);
Einen Binärbaum durchsuchen (Tiefensuche)
Beim Durchsuchen eines Binärbaums kommt zunächst die Tiefensuche in Betracht. Hier wird der Baum rekursiv durchsucht, wobei dem linken Teilbaum Vorrang vor dem rechten Teilbaum gegeben wird.
Der Zeitpunkt der Verarbeitung des aktuellen Elements (hier angedeutet durch den Ausdruck auf dem Bildschirm) vor dem ersten Rekursionsaufruf, zwischen den beiden Aufrufen oder nach dem zweiten Rekursionsaufruf beeinflusst zusätzlich die Reihenfolge der Verarbeitung. Die drei Varianten werden als PreOrder, InOrder bzw. PostOrder bezeichnet.
Die am häufigsten eingesetzte Variante ist der InOrder-Durchlauf, da er die Elemente in ihrer natürlichen Reihenfolge verarbeitet. Im obigen Beispiel, das eine Anordnung von Zahlen im Baum vorsieht, würden die Elemente deshalb auch in aufsteigender Reihenfolge abgearbeitet.
public void inorder(BinaryTree<String> tree) {
if (!tree.isEmpty()) {
inorder(tree.getLeftTree());
System.out.println(tree.getContent()); // Ausdrucken
inorder(tree.getRightTree());
}
}
Einen Binärbaum durchsuchen (Breitensuche)
Als Alternative zur Tiefensuche steht die Breitensuche zur Verfügung, die die Elemente ebenenweise abarbeitet.
Für den Beispielbaum würde die Reihenfolge der Verarbeitung dann 23, 17-38, 13-19-24-40, 5-14-39 lauten. Um die Ebenen abzubilden, wird eine Schlange als Hilfsdatenstruktur verwendet.
public void levelorder(BinaryTree<String> tree) {
Queue<BinaryTree<String>> q = new Queue<BinaryTree<String>>();
q.enqueue(tree);
while (!q.isEmpty()) {
BinaryTree<String> t = q.front();
q.dequeue();
System.out.println(t.getContent()); // Ausdrucken
if (!t.getLeftTree().isEmpty()) {
q.enqueue(t.getLeftTree());
}
if (!t.getRightTree().isEmpty()) {
q.enqueue(t.getRightTree());
}
}
}
Einen Binärbaum verarbeiten (mit Rückgabewert)
Zum Abschluss soll hier ein komplexeres Beispiel präsentiert werden. Zur Illustration dient der nachfolgende Baum. Die Aufgabe besteht darin, die Tiefe des Baums (d.h. die Anzahl der benutzten Ebenen, im Beispiel 4) zu berechnen.
Die kompakte rekursive Methode hat es durchaus in sich: Ist der aktuelle Teilbaum leer, so ist seine Tiefe 0. Ansonsten ist seine Tiefe um 1 größer als die maximale Tiefe des linken oder des rechten Teilbaums - je nachdem, welcher von beiden die größere Tiefe besitzt.
public int depth(BinaryTree<String> tree) {
if (tree.isEmpty()) {
return 0;
}
else {
int left = depth(tree.getLeftTree());
int right = depth(tree.getRightTree());
if (left>right) {
return left+1;
}
else {
return right+1;
}
}
}
Suchbaum
Der Suchbaum stellt einen guten Kompromiss aus den Datenstrukturen Feld und Liste dar: Er ist dynamisch, erlaubt also jederzeit nachträgliches Einfügen oder Löschen ohne zusätzlichen Speicherbedarf. Er ermöglicht zugleich eine schnelle Suche, da die Idee der binären Suche übertragbar ist, wodurch sich logarithmischer Suchaufwand ergibt.
Eine Klasse zum Suchen vorbereiten
Voraussetzung für den Aufbau eines Suchbaums ist eine Ordnung der zu verwaltenden Elemente. Für die Klasse BinarySearchTree wird die erforderliche Ordnung so realisiert, dass für die Basisklasse der zu speichernden Objekte gefordert wird, dass sie das Interface ComparableContent implementiert. In diesem Interface wird mit den drei Methoden isLess(), isGreater() und isEqual() die Vergleichbarkeit der Elemente verankert.
public interface ComparableContent<ContentType> {
public boolean isGreater(ContentType pContent);
public boolean isEqual(ContentType pContent);
public boolean isLess(ContentType pContent);
}
Die folgende Beispielklasse Entry speichert für jedes Objekt exemplarisch ein ganzzahliges Attribut, das über eine get-Methode abgefragt werden kann. In den drei Vergleichsmethoden muss ein Objekt die Frage beantworten, wie es sich selbst gegenüber einem zweiten Objekt (hier pContent) der gleichen Klasse einordnet.
public class Entry implements ComparableContent<Entry> {
private int wert;
public Entry(int pWert) {
this.wert = pWert;
}
public boolean isLess(Entry pContent) {
return wert < pContent.getWert();
}
public boolean isEqual(Entry pContent) {
return wert == pContent.getWert();
}
public boolean isGreater(Entry pContent) {
return wert > pContent.getWert();
}
public int getWert() {
return wert;
}
}
Einen Suchbaum aufbauen
Steht die Basisklasse, so steht dem Aufbau des Suchbaums nichts mehr im Wege. Im nachfolgenden Beispiel werden nacheinander die Elemente 45, 25 usw. in den Suchbaum eingefügt. Für das geordnete Einfügen sorgt die Methode insert.
Somit ergibt sich der folgende Beispielsuchbaum:
Entry int1 = new Entry(45);
Entry int2 = new Entry(25);
Entry int3 = new Entry(65);
Entry int4 = new Entry(15);
Entry int5 = new Entry(35);
tree = new BinarySearchTree<Entry>();
tree.insert(int1);
tree.insert(int2);
tree.insert(int3);
tree.insert(int4);
tree.insert(int5);
In einem Suchbaum suchen
Um nun ein Element im Suchbaum zu suchen, ist zunächst ein Such-Objekt der Basisklasse (in unserem Beispiel Entry) anzulegen. Kann die Methode search() ein passendes Objekt im Baum finden, so wird dieses Objekt zurückgegeben. Bleibt die Suche erfolglos, so gibt sie null zurück. Eine Fallunterscheidung kann die beiden Fälle trennen.
Entry suchitem = new Entry(77);
Entry ergitem = tree.search(suchitem);
if (ergitem!=null) {
System.out.println("Ja");
}
else {
System.out.println("Nein");
}
Einen Suchbaum durchlaufen
Analog zum Binärbaum kann auch der Suchbaum rekursiv durchsucht werden. Diese Möglichkeit ist aber vorrangig für Debugging-Zwecke (z.B. zum Ausdrucken des Suchbaum-Inhalts) interessant.