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 Datenträger) 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 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;
      }
    }
}

results matching ""

    No results matching ""