Der Morsebaum
AFB I–IIIm Morsealphabet wird jeder Buchstabe durch eine Folge aus Punkten „.“ und Strichen „-“ dargestellt. Ein Programm zum Entschlüsseln speichert die Buchstaben in einem Objekt morse der Klasse BinTree<String> (Ergänzende Hinweise 2025). Beginnend an der Wurzel führt jeder Punkt in den linken, jeder Strich in den rechten Teilbaum; der erreichte Knoten enthält den Buchstaben.
- Beschreiben Sie den abgebildeten Baum mit den Fachbegriffen Wurzel, innerer Knoten, Blatt und Höhe. Geben Sie dazu die Anzahl der Knoten und der Blätter an. 4 BE
- Wenden Sie das Verfahren an: Geben Sie die Morsecodes von R und K an und entschlüsseln Sie die Folge
-.. / .. / . / ...(Buchstaben durch „/“ getrennt). 3 BE - Implementieren Sie die Methode
static String decodiere(BinTree<String> morse, String code), die den Buchstaben zum Morsecodecodeliefert. Führt der Code aus dem Baum heraus, soll"?"geliefert werden. 5 BE - Das vollständige Morsealphabet enthält 26 Buchstaben mit Codes aus höchstens vier Zeichen. Begründen Sie, dass dafür ein Binärbaum der Höhe 5 genügt, und geben Sie an, wie viele Knoten er höchstens haben kann. 3 BE
Insgesamt 15 BE
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
b durch den Baum. Vor jedem getLeft()/getRight() und vor getItem() muss geprüft werden, ob der Baum leer ist.Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Die Wurzel enthält keinen Buchstaben (leerer Text). Sie hat die Kinder E und T. Innere Knoten sind die Wurzel sowie E, T, I, A, N, M; Blätter sind S, U, R, W, D, K, G, O. Der Baum ist vollständig: Jede Ebene ist voll besetzt. Er hat 15 Knoten, davon 8 Blätter, und die Höhe 4.
Erwartungshorizont zu Aufgabe b)
R: .-. (links, rechts, links). K: -.-. Die Folge ergibt D, I, E, S — das Wort DIES.
Erwartungshorizont zu Aufgabe c)
static String decodiere(BinTree<String> morse, String code) {
BinTree<String> b = morse;
for (int i = 0; i < code.length(); i++) {
if (b.isEmpty()) {
return "?";
}
if (code.charAt(i) == '.') {
b = b.getLeft();
} else {
b = b.getRight();
}
}
if (b.isEmpty()) {
return "?";
}
return b.getItem();
}Geprüft mit dem abgebildeten Baum: ".-." → R, "-.-" → K, "..--" → ?. Eine rekursive Lösung ist gleichwertig.
Erwartungshorizont zu Aufgabe d)
Ein Code aus k Zeichen führt von der Wurzel k Kanten nach unten, also auf Ebene k + 1. Codes mit höchstens vier Zeichen enden spätestens auf Ebene 5 — Höhe 5 genügt. Auf den Ebenen 2 bis 5 ist Platz für 2 + 4 + 8 + 16 = 30 ≥ 26 Buchstaben. Mit der Wurzel hat der Baum höchstens \(2^5-1=31\) Knoten.
Die Ahnentafel
AFB II–IIIEine Ahnenforschungs-App speichert die Vorfahren einer Person als BinTree<String>: Die Wurzel ist die Person selbst, der linke Teilbaum steht für die Mutter mit ihren Vorfahren, der rechte für den Vater. Unbekannte Personen werden durch leere Bäume dargestellt. Die Generation der Wurzel hat die Nummer 0, die der Eltern die Nummer 1 usw.
Gegeben ist außerdem die Methode:
static int geheimnis(BinTree<String> b) {
if (b.isEmpty() || b.isLeaf()) {
return 0;
}
int z = 0;
if (b.getLeft().isEmpty() || b.getRight().isEmpty()) {
z = 1;
}
return z + geheimnis(b.getLeft()) + geheimnis(b.getRight());
}- Erläutern Sie, warum sich eine Ahnentafel als Binärbaum modellieren lässt, ein Stammbaum mit allen Nachkommen einer Person dagegen nicht. 3 BE
- Implementieren Sie die Methode
static int anzahlInGeneration(BinTree<String> b, int g), die die Anzahl der bekannten Vorfahren in Generationgliefert. Für Mias Ahnentafel liefertanzahlInGeneration(mia, 2)den Wert 3. 5 BE - Analysieren Sie die Methode
geheimnis: Ermitteln Sie ihren Rückgabewert für Mias Ahnentafel und geben Sie an, was sie im Sachzusammenhang berechnet. 4 BE - Eine Entwicklerin schlägt vor, die Ahnentafel stattdessen in einer dynamischen Reihung zu speichern: Die Person steht an Index 0, Mutter und Vater der Person an Index i stehen an den Indizes 2i + 1 und 2i + 2, Unbekannte als leerer Text. Beurteilen Sie diesen Vorschlag im Vergleich zum Binärbaum. 4 BE
Insgesamt 16 BE
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Jede Person hat genau zwei biologische Eltern — also höchstens zwei Kinder im Baum, und die Rollen „Mutter“ (links) und „Vater“ (rechts) sind fest. Bei den Nachkommen kann eine Person beliebig viele Kinder haben; dafür reichen zwei Teilbäume nicht, man bräuchte einen allgemeinen Baum.
Erwartungshorizont zu Aufgabe b)
static int anzahlInGeneration(BinTree<String> b, int g) {
if (b.isEmpty()) {
return 0;
}
if (g == 0) {
return 1;
}
return anzahlInGeneration(b.getLeft(), g - 1) + anzahlInGeneration(b.getRight(), g - 1);
}Für Mia: Generation 2 → Clara, David, Eva = 3; Generation 3 → Fritz = 1.
Erwartungshorizont zu Aufgabe c)
Leere Bäume und Blätter liefern 0. Für jeden inneren Knoten wird 1 gezählt, wenn genau ein Teilbaum leer ist (beide leer wäre ein Blatt). Mia, Anna: beide Eltern bekannt → 0. Ben: Vater unbekannt → 1. Clara: Mutter unbekannt → 1. Rückgabewert: 2. Die Methode zählt die Personen, von denen genau ein Elternteil bekannt ist.
Erwartungshorizont zu Aufgabe d)
Vorteile der Reihung: Generation g liegt geschlossen an den Indizes \(2^g-1\) bis \(2^{g+1}-2\); Mutter und Vater werden ohne Durchlaufen des Baums direkt über den Index erreicht. Nachteile: Für jede unbekannte Person muss ein leerer Platz reserviert werden — auch für alle ihre (ebenso unbekannten) Vorfahren. Bei 10 Generationen sind das \(2^{10}-1=1023\) Plätze, auch wenn nur 30 Personen bekannt sind. Der Binärbaum speichert nur bekannte Personen und lässt sich beliebig tief erweitern. Urteil: Für vollständig bekannte, wenige Generationen ist die Reihung geeignet; für typische, lückenhafte Ahnentafeln ist der Binärbaum speichersparender und flexibler.