MINT üben

Das Prinzip Binärbaum

Zwei Abituraufgaben zum Binärbaum — vom Morsealphabet bis zur Ahnentafel.

Dein Fortschritt:
0 / 0 Aufgaben
1

Der Morsebaum

AFB I–II

Im 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.

Material: Ausschnitt des Morsebaums (links = Punkt „.“, rechts = Strich „-“)
SIUERAW▪DNKTGMO
Die Wurzel (▪) enthält den leeren Text; jede Kante nach links steht für „.“, nach rechts für „-“.
  1. 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
  2. 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
  3. Implementieren Sie die Methode static String decodiere(BinTree<String> morse, String code), die den Buchstaben zum Morsecode code liefert. Führt der Code aus dem Baum heraus, soll "?" geliefert werden. 5 BE
  4. 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)
Zählen Sie Knoten pro Ebene; die Wurzel liegt auf Ebene 1.
Hinweis zu Aufgabe b)
Suchen Sie den Buchstaben im Baum und notieren Sie den Weg von der Wurzel aus.
Hinweis zu Aufgabe c)
Laufen Sie Zeichen für Zeichen mit einer Hilfsvariablen b durch den Baum. Vor jedem getLeft()/getRight() und vor getItem() muss geprüft werden, ob der Baum leer ist.
Hinweis zu Aufgabe d)
Ein Code der Länge k endet auf Ebene k + 1. Wie viele Knoten passen höchstens auf die Ebenen 2 bis 5?