Abitur NRW: Klasse BinTree

Die offizielle Klasse BinTree

In einer Aufgabe des Zentralabiturs Informatik 2011 wurde den Schülern folgende "Dokumentation der Klasse BinTree" gegeben:

Dokumentation der Klasse BinTree

Mit Hilfe dieser Klasse sollten die Schüler dann die eigentliche Klausuraufgabe lösen, auf die ich aus Geheimhaltungsgründen hier nicht näher eingehen dar.

Implementierung einer BinTree-Klasse

In dem Schulbuch "Informatik 2" aus dem Schöningh-Verlag findet sich ein Abschnitt über binäre Bäume, der sehr ausführlich auf verschiedene Anwendungen von Binärbäumen eingeht, aber so gut wie gar nicht auf die Implementierung derselben. Im Zentralabitur NRW wird dies auch nicht gefordert; die Schüler sollen hauptsächlich die Methoden des Binärbaums kennen und damit arbeiten, eine Implementierung eines Binärbaums ist an keiner Stelle vorgesehen.

Im folgenden finden Sie einen selbst entwickelten Quelltext, der den obigen NRW-BinTree nach den Vorgaben in Java implementiert. Ich hoffe, der Quelltext enthält keine groben Fehler, sondern nur die üblichen...

import java.util.*;

public class BinTree
{
    Object value;
    BinTree left;
    BinTree right;
    
    public BinTree()
    {
        value  = null;
        left   = null;
        right  = null;
    }
    
    public BinTree(Object pObject)
    {
       value = pObject;
       left  = null;
       right = null;
    }
    
    public BinTree(Object pObject, BinTree pLeftTree, BinTree pRightTree)
    {
       value = pObject;
       left  = pLeftTree;
       right = pRightTree;
    }
    
    public boolean isEmpty()
    {
       return value == null;
    }
    
    public void clear()
    {
       value = null;
       left  = null;
       right = null;
    }
    
    public void setRootItem(Object pObject)
    {
       value = pObject;
    }
    
    public Object getRootItem()
    {
       return value;
    }
    
    public void setLeftTree(BinTree pBinTree)
    {
       left = pBinTree;
    }
    
    public void setRightTree(BinTree pBinTree)
    {
       right = pBinTree;
    }
    
    public BinTree getLeftTree()
    {
       return left;
    }

    public BinTree getRightTree()
    {
       return right;
    }
    
}

Anwendung eines BinTree-Objektes

In der Abituraufgabe von 2011 wurde ein BinTree zur Codierung/Decodierung eines einfachen Codes verwendet. Das zu erklären ist mir jetzt zu aufwändig. In dem Schulbuch des Schöningh-Verlags "Informatik 2" findet sich ein einfacheres und besseres Beispiel, und zwar soll der Stammbaum von Lisa Simpson (aus der Fernsehserie "Die Simpsons") mit Hilfe einesBinTree-Objektes dargestellt werden. Dazu muss man wissen, dass Lisa die Tochter von Marge und Homer ist. Marge ist die Tochter von Jacqueline und Clancy, und Homer ist der Sohn von Mona und Abraham. Hier nun meine "Implementierung" dieses Stammbaums:

public class BinTreeTest
{
  BinTree lisa;
  
  public BinTreeTest()
  {
      aufbauen();
  }
  
  public void aufbauen()
  {
     BinTree jacqueline = new BinTree(new String("Jacqueline"));
     BinTree clancy     = new BinTree(new String("Clancy"));        
     BinTree marge      = new BinTree(new String("Marge"),jacqueline,clancy);
     
     BinTree mona       = new BinTree(new String("Mona"));
     BinTree abraham    = new BinTree(new String("Abraham"));
     BinTree homer      = new BinTree(new String("Homer"),mona,abraham);
     
     lisa               = new BinTree(new String("Lisa"),marge,homer);
  }
}

Mit dem Objektinspektor kann man sich dann davon überzeugen, dass der Stammbaum tatsächlich so wie beschrieben aufgebaut wird. Hier wird der Baum "von unten nach oben" erzeugt. Zunächst also die Blätter - hier die Großeltern von Lisa. Wenn die Knoten jaqueline und clancy existieren, wird der knoten marge erzeugt. Wenn die Knoten mona und abraham existieren, wird der Knoten homer erzeugt. Dann kann schließlich auch der Knoten lisa erzeugt werden, der die Wurzel des Baumes ist.

Was ich hier gemacht habe - und was auch in dem besagten Schulbuch gemacht wird - entspricht in etwa dem Vorgehen, das ich auf der Seite "Binäre Suchbäume mit BlueJ" mit der Klasse BuildTree demonstriert habe.