Binärbaum
- 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)
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.
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 wurzelObject = 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(wurzelObject);
ergebnis.concat(linkeListe);
ergebnis.concat(rechteListe);
return ergebnis;
}
Levelorder-Traversierung (nur LK)
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ärbäume, die Objekte enthalten
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 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;
}