Zehn Übungen zum Einfügen, zur Einfügereihenfolge und zur Höhe des Baums.
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
Was beim Einfügen gilt
AFB I
Gib alle Aussagen an, die für das Einfügen in einen binären Suchbaum zutreffen.
Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Vorhandene Knoten bleiben, wo sie sind. Der neue Wert landet am Ende seines Suchpfads — dort, wo die erfolglose Suche einen leeren Baum erreicht.
Ansatz: Einfügen = suchen, bis ein leerer Baum erreicht ist.
Weiter: Wird beim Einfügen irgendein vorhandener Knoten verändert?
A2
Wo landet der Wert?
AFB I
Der Suchbaum wurde aus 60, 35, 80, 20, 45, 70 aufgebaut. Lies ab, wo ein weiterer Wert landen würde.
Suchbaum nach dem Einfügen von 60, 35, 80, 20, 45, 70
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5
Beim Einfügen wird nie ein Knoten verschoben — der neue Wert hängt immer unten an einem leeren Teilbaum.
Ansatz: Fahre den Suchpfad des neuen Werts nach.
Weiter: Wo die Suche auf einen leeren Baum trifft, ist der Platz.
A3
Einfügen in Java
AFB I
Nenne die fehlenden BinTree-Operationen der Methode einfuegen.
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.
if (b.()) b.(x);else if (x < b.()) einfuegen(b.(), x);else if (x > b.getItem()) einfuegen(b.(), x);
setItem auf dem leeren Baum legt nach den Ergänzenden Hinweisen 2025 zugleich zwei leere Teilbäume an — setLeft wird nicht gebraucht.
Ansatz: Die Methode hat drei Fälle: leer, kleiner, größer.
Weiter: Der Abbruchfall füllt den leeren Baum mit dem neuen Inhalt.
A4
Aufbauen und durchlaufen
AFB II
In einen leeren Suchbaum werden 30, 10, 50, 40, 20, 60 eingefügt. Erstelle den Baum auf einem Zettel und ordne die Karten zu seiner Preorder.
Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
130
210
320
450
540
660
Der Baum: 30 mit linkem Kind 10 (dessen rechtes Kind 20) und rechtem Kind 50 (Kinder 40 und 60). Preorder: 30 10 20 50 40 60 — nicht die Einfügereihenfolge, denn 20 liegt im linken Teilbaum.
Ansatz: Füge die Werte einzeln von der Wurzel aus ein.
Weiter: Preorder: Wurzel, dann der ganze linke Teilbaum, dann der rechte.
A5
Aufwand beim Aufbau
AFB II
Die Werte 15, 8, 23, 4, 12, 19, 27, 10 werden in dieser Reihenfolge eingefügt. Ermittle die Kennzahlen.
Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
Tiefe des Knotens 10
Vergleiche insgesamt beim Aufbau
Höhe des fertigen Baums
Die 10 wandert 15 → 8 → 12 und wird linkes Kind von 12: Tiefe 3. Vergleiche: 0 + 1 + 1 + 2 + 2 + 2 + 2 + 3 = 13 — jeder Wert braucht so viele Vergleiche, wie seine Tiefe angibt. Höhe 4.
Ansatz: Die Zahl der Vergleiche beim Einfügen ist gleich der Tiefe, in der der Wert landet.
Weiter: Addiere die Tiefen aller Werte; die Wurzel hat Tiefe 0.
A6
Welche Struktur passt?
AFB II
Ordne jede Situation der passenden Datenstruktur aus dem Kapitel zu.
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
2Schlange
3Stapel
4Suchbaum
Der Suchbaum lohnt sich, wenn oft gesucht und eingefügt wird — und die Inorder liefert die Werte gleich sortiert.
Ansatz: Frage: In welcher Reihenfolge werden die Daten wieder gebraucht?
Weiter: Suchbaum = schnelles Suchen nach einem Schlüssel; Index-Zugriff = DynArray.
A7
Reihenfolge und Höhe
AFB II
Wende das Einfügen gedanklich an und verbinde jede Einfügereihenfolge mit der Höhe des entstehenden Suchbaums.
Klicke links ein Element an und dann rechts das passende — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Sortierte oder umgekehrt sortierte Folgen erzeugen eine Kette: Höhe = Anzahl der Werte. Beginnt man mit einem mittleren Wert, wird der Baum breit.
Ansatz: Zeichne jeden Baum kurz auf.
Weiter: Eine sortierte Folge hängt jeden neuen Wert rechts an den letzten.
A8
Eingefügt und doch verloren
AFB III
Die Methode soll x in den Suchbaum b einfügen, doch nach dem Aufruf fehlen Werte. Ü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.
Ein neu erzeugtes Objekt muss mit setLeft/setRight eingehängt werden. Einfacher ist setItem auf dem vorhandenen leeren Teilbaum — der hängt schon im Baum.
Ansatz: Was ändert eine Zuweisung an einen Parameter außerhalb der Methode?
Weiter: Vergleiche die beiden rekursiven Aufrufe miteinander.
A9
Noch einmal die 20
AFB III
In einen leeren Suchbaum werden nacheinander 40, 20, 60, 20, 60, 10 eingefügt. Untersuche, wie viele Knoten der Baum danach hat.
Rechne selbst und trage das Ergebnis ein — Enter prüft direkt.
Vier Knoten: 40, 20, 60 und 10. Die zweite 20 und die zweite 60 werden gefunden und deshalb nicht noch einmal eingefügt — im Suchbaum ist jeder Schlüssel eindeutig.
Ansatz: Was macht einfuegen, wenn x schon im Baum steht?
Weiter: Zähle nur verschiedene Werte.
A10
Ausgeglichen aus sortierten Daten
AFB III
Die Werte 1 bis 7 liegen sortiert vor. Sortiert eingefügt würde der Baum zur Kette. Entwirf Schritt für Schritt eine Einfügereihenfolge, die einen möglichst niedrigen Baum ergibt.
Spiele den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt dich weiter.
Die Strategie „Mitte zuerst, dann rekursiv die Mitten der Hälften“ liefert einen ausgeglichenen Baum mit der kleinstmöglichen Höhe ⌈log2(n + 1)⌉.
Ansatz: Welcher Wert teilt die übrigen gerecht in links und rechts?
Weiter: Denke an die binäre Suche: Sie beginnt auch in der Mitte.
