Aufgabe 2 - Binärbäume und binäre Suchbäume · Abitur NRW Informatik LK · Nachtermin 2023

Aufgabenstellung

Ein Informatikkurs hat selbst eine Methode zur Verschlüsselung von Nachrichten entworfen: Jeder Buchstabe des Alphabets wird durch eine Folge aus Nullen und Einsen ersetzt (nachfolgend „Chiffre“ genannt). Die Länge dieser Chiffre kann variieren. Der Einfachheit halber werden in der Aufgabe nur die sieben Buchstaben A, E, H, L, O, T und W betrachtet.

Um ein fehlerfreies Ver- und Entschlüsseln zu gewährleisten, bilden sie die Chiffren der Buchstaben nach diesem Prinzip:

Genau ein Buchstabe gehört zu jedem Blatt eines Binärbaums. Von der Wurzel aus wird untersucht, ob der Weg zum gesuchten Buchstaben in den linken oder in den rechten Teilbaum führt. Der Weg in den linken Teilbaum wird mit 0, der in den rechten Teilbaum mit 1 codiert. Die Nullen und Einsen werden vereinfachend als Zeichenketten abgelegt.

Ein solcher Baum legt eindeutig fest, welche Chiffre zu welchem Buchstaben gehört. Da das Verfahren den Baum nicht vorgibt, ergeben verschiedene Bäume verschiedene Chiffren. Der Baum stellt somit den Schlüssel dar.

Jedem Buchstaben ist eine eigene Chiffre zugeordnet. Man kann alle Chiffren in einer Tabelle sammeln. Zum Schlüssel-Beispiel aus Abbildung 1 erhält man die folgende unvollständige Chiffrier-Tabelle:

Buchstabe · A · O · T · E · W · L · H

Chiffre · · · · · · 1101

Abbildung 2: unvollständige Chiffrier-Tabelle zum Beispiel aus Abbildung 1

Zur Nutzung dieses Verschlüsselungssystems wurde ein Softwaremodell entwickelt, das ausschnittsweise so dargestellt ist:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Chiffrierer

Ein Objekt der Klasse Chiffrierer verwaltet die Entschlüsselung und Verschlüsselung von Zeichenketten mittels eines Binärbaums und einer Tabelle.

Ausschnitt aus der Dokumentation der Klasse Chiffrierer

Chiffrierer()

Ein Objekt der Klasse existiert, es ist nicht initialisiert. Eine Chiffrier-Tabelle und ein Chiffrier-Baum existieren nicht, das Entschlüsseln und das Verschlüsseln sind noch nicht möglich.

void initialisiere(Schluessel pSchluessel, String pPasswort)

Wenn das übergebene Passwort zum übergebenen Schlüssel passt, werden mit diesen Parametern der Chiffrier-Baum und die Chiffrier-Tabelle initialisiert. Das Entschlüsseln und das Verschlüsseln sind dann möglich.

String verschluessele(String pKlartext)

Sofern das Chiffrierer-Objekt korrekt initialisiert ist, nicht null übergeben wird und die Verschlüsselung gelingt, wird der übergebene Klartext verschlüsselt und der entsprechende Geheimtext zurückgegeben.

String entschluessele(String pGeheimtext)

Sofern das Chiffrierer-Objekt korrekt initialisiert ist, nicht null übergeben wird und die Entschlüsselung gelingt, wird der übergebene Geheimtext entschlüsselt und der entsprechende Klartext zurückgegeben.

Dokumentation privater Methoden der Klasse Chiffrierer

void erstelleChiffrierTabelle()

Diese Methode soll in Teilaufgabe c) analysiert werden.

void ermittleChiffrierTabelle(BinaryTree<String> pBaum, String pChiffre)

Diese Methode soll in Teilaufgabe c) analysiert werden.

String entschluesseleBuchstaben(String pChiffre)

Sofern das Chiffrierer-Objekt korrekt initialisiert ist, wird der Klarbuchstabe zu der übergebenen Chiffre zurückgegeben. Andernfalls wird null zurückgegeben. Die Chiffre wird nicht auf Korrektheit geprüft.

Die Klasse Schluessel

Ein Objekt der Klasse verwaltet einen Chiffrier-Baum sowie den Zugriff auf den Chiffrier-Baum über ein Passwort.

Ausschnitt aus der Dokumentation der Klasse Schluessel

Schluessel(String pPasswort, BinaryTree<String> pChiffrierBaum)

Ein neues Objekt der Klasse wird mit den übergebenen Parametern initialisiert. Das Passwort wird nicht im Klartext gespeichert sondern ein Prüfwert.

BinaryTree<String> gibChiffrierBaum(String pPasswort)

Sofern das Passwort korrekt ist, wird eine Referenz auf den gespeicherten Chiffrier-Baum zurückgegeben. Andernfalls wird null zurückgegeben.

Dokumentation privater Methoden der Klasse Schluessel

boolean pruefePasswort(String pPasswort)

Die Methode liefert true, wenn die Zeichenkette pPasswort dem beim Erzeugen des Objekts übergebenen Passwort entspricht. Andernfalls liefert sie false.

Die Klasse ChiffrierTabelle

Ein Objekt der Klasse verwaltet die Chiffren zu den Buchstaben analog zum Chiffrier-Baum.

Ausschnitt aus der Dokumentation der Klasse ChiffrierTabelle

ChiffrierTabelle()

Ein neues Objekt der Klasse wird initialisiert. Es ist keine Kombination aus Buchstabe und Chiffre gespeichert.

void fuegeHinzu(String pBuchstabe, String pChiffre)

Die Kombination aus dem Klartext-Buchstaben und der Chiffre für diesen Buchstaben wird gespeichert. Ist für den Buchstaben bereits eine Chiffre vorhanden, wird die vorhandene gelöscht und die zuletzt übergebene gespeichert.

String gibChiffre(String pBuchstabe)

Sofern für den übergebenen Buchstaben eine Chiffre existiert, wird diese zurückgegeben. Andernfalls wird null zurückgegeben.

Die generische Klasse BinaryTree<ContentType>

Mithilfe der generischen Klasse BinaryTree können beliebig viele Objekte vom Typ ContentType in einem Binärbaum verwaltet werden. Ein Objekt der Klasse stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der generischen Klasse BinaryTree sind.

Dokumentation der Klasse BinaryTree<ContentType>

BinaryTree<ContentType>()

Nach dem Aufruf des Konstruktors existiert ein leerer Binärbaum.

BinaryTree<ContentType>(ContentType pContent)

Wenn der Parameter pContent ungleich null ist, existiert nach dem Aufruf des Konstruktors der Binärbaum und hat pContent als Inhaltsobjekt und zwei leere Teilbäume. Falls der Parameter null ist, wird ein leerer Binärbaum erzeugt.

BinaryTree<ContentType>(ContentType pContent, BinaryTree<ContentType> pLeftTree, BinaryTree<ContentType> pRightTree)

Wenn der Parameter pContent ungleich null ist, wird ein Binärbaum mit pContent als Inhaltsobjekt und den beiden Teilbäume pLeftTree und pRightTree erzeugt. Sind pLeftTree oder pRightTree gleich null, wird der entsprechende Teilbaum als leerer Binärbaum eingefügt. Wenn der Parameter pContent gleich null ist, wird ein leerer Binärbaum erzeugt.

boolean isEmpty()

Diese Anfrage liefert den Wahrheitswert true, wenn der Binärbaum leer ist, sonst liefert sie den Wert false.

void setContent(ContentType pContent)

Wenn der Binärbaum leer ist, wird der Parameter pContent als Inhaltsobjekt sowie ein leerer linker und rechter Teilbaum eingefügt. Ist der Binärbaum nicht leer, wird das Inhaltsobjekt durch pContent ersetzt. Die Teilbäume werden nicht geändert. Wenn pContent null ist, bleibt der Binärbaum unverändert.

ContentType getContent()

Diese Anfrage liefert das Inhaltsobjekt des Binärbaumes. Wenn der Binärbaum leer ist, wird null zurückgegeben.

void setLeftTree(BinaryTree<ContentType> pTree)

Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls erhält der Binärbaum den übergebenen Baum als linken Teilbaum. Falls der Parameter null ist, ändert sich nichts.

void setRightTree(BinaryTree<ContentType> pTree)

Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls erhält der Binärbaum den übergebenen Baum als rechten Teilbaum. Falls der Parameter null ist, ändert sich nichts.

BinaryTree<ContentType> getLeftTree()

Diese Anfrage liefert den linken Teilbaum des Binärbaumes. Der Binärbaum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurückgegeben.

BinaryTree<ContentType> getRightTree()

Diese Anfrage liefert den rechten Teilbaum des Binärbaumes. Der Binärbaum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurückgegeben.

Die Klasse String

Ein Objekt der Klasse String kann eine Zeichenkette, die eine URL repräsentieren soll, auf Korrektheit geprüft werden.

Ausschnitt aus der Dokumentation der Klasse String

char charAt(int index)

Die Methode liefert das Zeichen an dem angegebenen Index index. Der Index reicht von 0 einschließlich bis zur length() - 1. Das erste Zeichen besitzt den Index 0, das nächste den Index 1 und so weiter.

int compareTo(String anotherString)

Die Methode vergleicht zwei Zeichenketten lexikografisch. Sie liefert einen Integerwert kleiner als 0, wenn der String lexikografisch vor der übergebenen Zeichenkette anotherString anzuordnen ist. Sie liefert einen Integerwert größer als 0, wenn der String lexikografisch nach der der übergebenen Zeichenkette anotherString anzuordnen ist. Sind beide Zeichenketten identisch, wird der Wert 0 zurückgegeben.

boolean equals(Object anObject)

Die Methode liefert genau dann true, wenn der Parameter anObject nicht null ist und wenn das übergebene Objekt anObject vom Typ String ist und die gleiche Zeichenkette repräsentiert.

int indexOf(String str)

Die Methode liefert den Index des ersten Zeichens beim ersten Vorkommen der übergebenen Zeichenkette str. Kommt die übergebene Zeichenkette nicht vor, wird -1 zurückgegeben.

int length()

Die Methode liefert die Länge der Zeichenkette.

boolean startsWith(String prefix)

Die Methode liefert genau dann den Wert true, wenn die Zeichenkette mit dem angegebenen Präfix prefix beginnt. Andernfalls liefert sie den Wert false. Wird eine leere Zeichenkette oder die identische Zeichenkette übergeben, liefert die Methode dementsprechend ebenfalls den Wert true.

String substring(int beginIndex)

Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Ende der Zeichenkette. Der Wert des Parameters beginIndex darf nicht größer als die Länge der Zeichenkette sein. Ist er gleich der Länge der Zeichenkette, so wird die leere Zeichenkette "" zurückgegeben.

String substring(int beginIndex, int endIndex)

Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis ein Zeichen vor endIndex. Der Wert des Parameters endIndex darf nicht größer als die Länge des Strings sein. Der Wert des Parameters beginIndex muss größer oder gleich 0 sein und darf nicht größer als der Wert von endIndex sein.

c)

Die privaten Methoden erstelleChiffrierTabelle und ermittleChiffrierTabelle der Klasse Chiffrierer stellen eine zentrale interne Funktionalität der Klasse zur Verfügung.

1 private void erstelleChiffrierTabelle() {

2 chiffrierTabelle = new ChiffrierTabelle();

3 ermittleChiffrierTabelle(chiffrierBaum, "");

4 }

5

6 private void ermittleChiffrierTabelle(

7 BinaryTree<String> pBaum, String pChiffre) {

8 if (pBaum.getLeftTree().isEmpty()

9 && pBaum.getRightTree().isEmpty()) {

10 chiffrierTabelle.fuegeHinzu(pBaum.getContent(), pChiffre);

11 } else {

12 ermittleChiffrierTabelle(pBaum.getLeftTree(),

13 pChiffre + "0");

14 ermittleChiffrierTabelle(pBaum.getRightTree(),

15 pChiffre + "1");

16 }

17 }

Anhand der Beispieldaten aus Abbildung 1 sollen die Methoden untersucht werden. Hierfür wird die parameterlose Methode erstelleChiffrierTabelle (Zeilen 1 bis 4) aufgerufen. Das Objekt der Klasse Chiffrierer hält unter dem Bezeichner chiffrierBaum den in Abbildung 1 dargestellten Chiffrier-Baum.

Analysieren Sie die Methoden erstelleChiffrierTabelle und ermittleChiffrierTabelle und erläutern Sie, wie sie funktionieren.

Wenden Sie die Methoden erstelleChiffrierTabelle und ermittleChiffrierTabelle auf die Beispieldaten aus Abbildung 1 an und dokumentieren Sie, in welcher Reihenfolge die Methode ermittleChiffrierTabelle aufgerufen wird, indem Sie jeweils den übergebenen Parameter pChiffre angeben.

d)

Die private Methode entschluesseleBuchstaben der Klasse Chiffrierer entschlüsselt mithilfe des verwalteten Chiffrier-Baums einen übergebenen Geheimtext und liefert den zugehörigen Buchstaben als Zeichenkette, falls ein gültiger Schlüssel gesetzt ist. Andernfalls ist der Rückgabewert null. Die private Methode wird von der öffentlichen Methode entschluessele benutzt. Ihr Methodenkopf lautet:

private String entschluesseleBuchstaben(String pChiffre)

Implementieren Sie die Methode entschluesseleBuchstaben.

Ergänzen Sie Ihren Quellcode um Kommentare.

Hinweis: Nehmen Sie an, dass pChiffre eine zum gespeicherten Chiffrier-Baum passende gültige Chiffre ist, falls dieser vorhanden ist.