Binärbaum

Binärbaum mit Knotentypen

Ahnenbaum: Justus und seine Vorfahren

Binärer Strukturbaum (12/4)+(2*3)

Diese Seite entspricht dem Abi 17 (und folgenden)

• Ein Binärbaum ist ein gewurzelter Baum, bei dem jeder Knoten keine (auch Blatt genannt), eine oder maximal zwei Teilbäume besitzt.
• Als Spezialfall des Binärbaumes gibt es den Binären Suchbaum.
• Wie Methoden für Binärbäume implementiert werden können, wird in folgendem Artikel erklärt: Binärbaum_(Methoden)

Erklärvideos

• Prinzip der Traversierungen Preorder und Inorder
• Levelorder-Traversierung: Prinzip und Implementierung

Fachbegriffe

Kante, Knoten, Wurzel, Blatt, Tiefe, Traversierung (Inorder, Preorder, Levelorder), Rekursion, Abbruchbedingung, rekursiver Aufruf, Sachlogik, Rahmenmethode

Schnittstelle des Zentralabiturs

Binärbaum Schnittstelle des Zentralabiturs(PDF)‎

Wichtiger Hinweis:

In der Schnittstelle des Zentralabiturs wird immer davon ausgegangen, dass unter den "sichtbaren" Knoten von Bäumen noch leere Knoten sind. Das hat den enormen Vorteil, dass man beim rekursiven Durchlauf durch einen Baum mit isEmpty() abbrechen kann.

Traversierung

Traversierungen sind Methoden, um alle Knoten eines Baumes in eine Liste zu übertragen.

Erklärvideo: Prinzip der Traversierungen Preorder und Inorder

Prinzip

• Preorder: Wurzel -> Links -> Rechts
• Inorder: Links -> Wurzel -> Rechts
  Für den Inorder-Durchlauf kann man den Baum "von links nach rechts" lesen.
  Inorder gibt in Bäumen mit Suchbaumstruktur die Knoten sortiert zurück.
• Postorder: Links -> Rechts -> Wurzel
• Levelorder: Der Baum wird "schichtenweise" in eine Liste übertragen.

Preorder, Inorder und Postorder sind Tiefendurchläufe. Levelorder dagegen ist ein Breitendurchlauf.

Beispiel: preorder-Traversierung

Bei der preorder-Traversierung handelt es sich (genauso wie bei inorder und postorder) um eine Tiefensuche. D.h. es wird erst ein Teil des Baums bis ganz nach unten durchsucht, bevor die anderen Zweige drankommen.

Preorder-Traversierung des Ahnenbaums:

Justus, Margit, Antonie, Robert, Werner, Elisabeth, Bernhard, Henry, Lotte, Heinz, Lotte

Implementierung:

public List<String> preorder(BinaryTree<String> pTree)
{
   List<String> ergebnis = new List<>();
   // Abbruchbedingung
   if (pTree.isEmpty()){
      return ergebnis;
   }

   // Wurzelelement auslesen
   String wurzel = pTree.getContent();
  
   // rekursiver Aufruf: erst fuer links, dann fuer rechts
   List<String> linkeListe = preorder(pTree.getLeftTree()); 
   List<String> rechteListe = preorder(pTree.getRightTree()); 
   
   // das ergebnis zusammenbauen
   ergebnis.append(wurzel);
   ergebnis.concat(linkeListe);
   ergebnis.concat(rechteListe);
   return ergebnis;
}

Levelorder-Traversierung (nur LK)

Ahnenbaum: Beispiel für Levelorder: Ahnenbaum

Bei der Levelorder-Traversierung wird ein Binärbaum schichtenweise durchlaufen, d.h.:

• erst die Wurzel
• dann die Wurzeln der beiden Teilbäume
• usw.

Für den Ahnenbaum ergibt sich folgende Levelorder-Reihenfolge:

Justus, Margit, Henry, Antonie, Werner, Lotte, Heinz, Robert, Elisabeth, Bernhard, Lotte.

D.h. man erhält die Vorfahren generationsweise.

Zur Implementierungsstrategie siehe Linearisierung im Artikel Binärbaum_(Methoden).

weitere Methoden

Implementierungen von weiteren Methoden finden sich hier:

Binärbaum_(Methoden) ab Abi 2017

Binärbäume, die Objekte enthalten

Implementationsdiagramm Personenverwaltung

In den Beispielen oben sind in Binärbäumen jeweils nur Objekte vom Typ String oder vom Typ int enthalten.

Häufig enthalten Binärbäume aber auch Objekte von selbstdefinierten Klassen. Wie man damit umgeht, soll anhand eines Binärbaumes dargestellt werden, der mit Objekten der Klasse Person gefüllt ist (vgl. Implementationsdiagramm rechts).

Beispiel: Suchen nach Geburtsjahrgang

Zu implementieren ist für die Klasse Personenverwaltung eine Methode personenAusJahr, der ein Jahr übergeben wird, und die dann aus dem Attribut personenBaum alle Personen dieses Jahrganges heraussucht und in einer Liste zurückgibt.

Die gewünschte Methode ist hier eine Rahmenmethode, die ihrerseits eine (private) rekursive Methode aufruft.

Rahmenmethode

Häufig gibt es den folgenden Fall:

• Ein Attribut einer Klasse muss rekursiv durchsucht werden, wie z.B. oben das Attribut personenBaum.
• Die gewünschte Methode ist aber nicht rekursiv ist (wie z.B. die Methode public List personenAusJahr(int pGeburtsjahr) ).

Dann macht man die gewünschte Methode zur Rahmenmethode, die ihrerseits eine private rekursive Methode aufruft.

Implementierung

public class Personenverwaltung{

 // Attribut zur Verwaltung der Personen
 private BinaryTree<Person> personenBaum;

 // *** Konstruktor
 public Personenverwaltung(){
    // hier wird personenBaum initialisiert
    // und mit Personen gefuellt
 }

 // Rahmenmethode
 public List<Person> personenAusJahr(int pGeburtsjahr){
   List<Person> ergebnis = personenAusJahr(personenBaum, pGeburtsjahr);
   return ergebnis;
 }

 // rekursive Methode
 private List<Person> personenAusJahr(BinaryTree<Person> pTree, int pGeburtsjahr){
   List<Person> ergebnis = new List<>();
   //Abbruchbedingung: leerer Baum
   if(pTree.isEmpty()){
      return ergebnis;
   }
   // die Wurzel des Baumes auslesen
   // und in ein Objekt vom Typ Person konvertieren
   Person wurzelPerson = pTree.getContent();
   // Sachlogik: Vergleich des Geburtsjahres der wurzelPerson mit pGeburtsjahr
   if(wurzelPerson.getGeburtsjahr() == pGeburtsjahr){
      ergebnis.append(wurzelPerson);
   }
   // rekursive Aufrufe
   List<Person> ergebnisLinks = personenAusJahr(pTree.getLeftTree(), pGeburtsjahr);
   List<Person> ergebnisRechts = personenAusJahr(pTree.getRightTree(), pGeburtsjahr);
   // die Ergebnisse anhängen
   ergebnis.concat(ergebnisLinks);
   ergebnis.concat(ergebnisRechts);
   return ergebnis;
 }