Zehn Übungen zu Wurzel, Blättern, Höhe und den Operationen des BinTree.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.
A1
Den Baum lesen
AFB I
Der Binärbaum b ist in der Abbildung dargestellt. Lies ab, welche Aussagen zutreffen.
Binärbaum b (kein Suchbaum)
Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Blätter sind 2, 1, 8 und 3. Die 4 hat einen rechten Teilbaum, ist also kein Blatt. Der längste Weg 5 – 9 – 7 – 1 hat vier Ebenen: Höhe 4. Die 6 liegt zwei Kanten unter der Wurzel: Tiefe 2.
Ansatz: Ein Blatt hat links und rechts nur leere Teilbäume.
Weiter: Höhe = Anzahl der Ebenen, Tiefe = Anzahl der Kanten ab der Wurzel.
A2
Fachbegriffe
AFB I
Nenne die passenden Fachbegriffe, indem du die Lücken füllst.
Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück.
Der oberste Knoten heißt . Ein Knoten ohne Kinder ist ein , jeder andere ein . Ein Knoten mit allem, was unter ihm hängt, bildet einen . Ein Baum ohne Inhalt und ohne Teilbäume ist ein .
„Kante“ und „Stapel“ bleiben übrig: Eine Kante verbindet Eltern und Kind, der Stapel ist eine lineare Struktur.
Ansatz: Denke an einen echten Baum, der auf dem Kopf steht.
Weiter: Zwei Wörter der Wortbank werden nicht gebraucht.
A3
Stimmt's? — BinTree
AFB I
Gib bei jeder Aussage zum BinTree nach den Ergänzenden Hinweisen 2025 an, ob sie stimmt.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Ansatz: Überlege bei jeder Aussage ein kleines Beispiel.
Weiter: Ein leerer Baum hat keinen Inhalt — was sollte getItem() da liefern?
A4
Kennzahlen des Baums
AFB II
Bestimme für den Binärbaum b aus A1 Schritt für Schritt die Kennzahlen.
Binärbaum b (kein Suchbaum)
Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
Anzahl der Knoten n
Anzahl der Blätter
Höhe h
Anzahl der leeren Teilbäume
n = 9 Knoten, davon 4 Blätter. Höhe 4 (z. B. 5 – 9 – 7 – 1). Leere Teilbäume: n + 1 = 10 — jedes Blatt hat zwei, dazu der linke Teilbaum von 4 und der rechte von 6.
Ansatz: Zähle zuerst alle Kreise, dann die ohne Kinder.
Weiter: Leere Teilbäume: An jeder Stelle, an der ein Kind fehlen könnte, sitzt einer — es sind immer n + 1.
A5
Welche Klasse bietet das?
AFB II
Im Kapitel kennst du vier Klassen. Ordne jede Operation der Klasse zu, zu der sie gehört.
Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1DynArray
2Stack
3Queue
4BinTree
isEmpty() fehlt absichtlich: Diese Operation haben alle vier Klassen. Nur DynArray kennt einen Index, nur BinTree Teilbäume.
Ansatz: Überlege: Welche Struktur hat einen Index, welche ein oberes Ende, welche einen Kopf?
Weiter: Teilbäume gibt es nur beim Baum; „head“ ist das vordere Ende der Schlange.
A6
Ohne Laufzeitfehler aufbauen
AFB II
Die Anweisungen bauen den Baum Kiel → rechts Lübeck → links Husum → links Eutin auf. Erstelle daraus eine Reihenfolge, die ohne Laufzeitfehler läuft.
Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
Jede Zeile greift auf einen Teilbaum zu, den erst die Zeile davor mit Inhalt gefüllt hat. getLeft() auf einem leeren Baum wäre ein Laufzeitfehler.
Ansatz: Welche Zeile braucht keinen vorhandenen Baum?
Weiter: setItem auf einem leeren Baum legt zwei neue leere Teilbäume an — erst danach gibt es getLeft()/getRight().
A7
Ausdrücke auswerten
AFB II
Ermittle für den Binärbaum b aus A1, was die Ausdrücke liefern.
Binärbaum b (kein Suchbaum)
Klicke links ein Element an und dann rechts das passende — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Lies jeden Ausdruck von links nach rechts als Weg: getLeft = nach links unten, getRight = nach rechts unten. Der Teilbaum ab 7 hat zwei Ebenen (7 und 1 bzw. 8).
Ansatz: Fahre den Weg mit dem Finger in der Abbildung nach.
Weiter: hoehe zählt Ebenen des Teilbaums, der mit dem angegebenen Knoten beginnt.
A8
Blätter zählen
AFB III
Die Methode soll die Anzahl der Blätter liefern. Überprüfe sie und markiere die fehlerhaften Zeilen.
In diesem Code stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Mit return 1 zählt jeder leere Baum als Blatt; mit * würde ein leerer Teilbaum (richtig: 0 Blätter) das ganze Ergebnis auf 0 setzen. Rekursive Zähl-Methoden addieren die Teilergebnisse.
Ansatz: Setze gedanklich einen leeren Baum und einen Knoten mit zwei Blättern ein.
Weiter: Wie viele Blätter hat ein leerer Baum? Und wie verrechnet man die Blätter zweier Teilbäume?
A9
Wie hoch kann er werden?
AFB III
Lisa behauptet: „Ein Binärbaum mit 6 Knoten hat höchstens die Höhe 3.“ Widerlege die Behauptung, indem du die größtmögliche Höhe angibst.
Rechne selbst und trage das Ergebnis ein — Enter prüft direkt.
Bei 6 Knoten ist die Höhe mindestens 3 — Lisa hat die Richtung verwechselt. Hat jeder Knoten nur ein Kind, entsteht eine Kette mit 6 Ebenen: Höhe 6.
Ansatz: Wie kann man 6 Knoten möglichst „lang“ anordnen?
Weiter: Jeder Knoten bekommt genau ein Kind — der Baum sieht aus wie eine Liste.
A10
Rekursion Schritt für Schritt
AFB III
Die Methode hoehe aus 5.3.1 wird für den Baum X mit linkem Kind Y (ein Blatt) und leerem rechten Teilbaum aufgerufen. Analysiere den Ablauf der Rekursion.
Spiele den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt dich weiter.
Insgesamt gab es 5 Aufrufe: X, Y, die zwei leeren Teilbäume von Y und den leeren rechten Teilbaum von X — also 2n + 1 bei n = 2 Knoten.
Ansatz: Beginne oben und notiere jeden Aufruf mit seinem Rückgabewert.
Weiter: Ein leerer Baum liefert 0, sonst 1 + das Maximum der beiden Teilhöhen.
