Informatik · Klasse 12

Ideen für aktives Lernen

Binäre Bäume und Traversierung

Aktives Lernen eignet sich besonders für binäre Bäume und Traversierungen, weil Schülerinnen und Schüler durch Zeichnen, Bauen und Analysieren die abstrakten Strukturen greifbar machen können. Die visuelle und haptische Komponente hilft, die Unterschiede zwischen den Traversierungsverfahren zu verinnerlichen und Missverständnisse direkt zu korrigieren.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Strukturieren und Vernetzen
• KMK: Sekundarstufe II - Modellieren und Implementieren

• 15–30 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• Gruppenpuzzle
• 20 Min. · Partnerarbeit

Pärchenarbeit: Baum zeichnen

Schüler zeichnen gemeinsam einen binären Baum aus einer Zahlenfolge und markieren Traversierungsreihenfolgen. Sie diskutieren Vor- und Nachteile jeder Methode. Abschließend implementieren sie eine Traversierung in Pseudocode.

Wie lassen sich hierarchische Informationen effizient in Baumstrukturen abbilden?

Moderationstipp

Fordern Sie in der Pärchenarbeit klare Absprachen ein, wer zuerst zeichnet und wer die Schritte dokumentiert.

Worauf zu achten ist

Stellen Sie den Schülerinnen und Schülern eine Liste von Zahlen vor, z.B. 5, 3, 8, 1, 4, 7, 9. Bitten Sie sie, einen binären Suchbaum aus dieser Folge zu konstruieren und die Schritte zu dokumentieren. Überprüfen Sie die Korrektheit der Baumstruktur und die Einhaltung der Suchbaumeigenschaften.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Aktivität 02

• Gruppenpuzzle
• 30 Min. · Kleingruppen

Gruppenarbeit: Suchbaum bauen

In kleinen Gruppen konstruieren Schüler einen binären Suchbaum und testen Insertionen. Sie analysieren die Höhe und Balance. Eine Präsentation zeigt Eigenschaften.

Analysieren Sie die Vor- und Nachteile von Pre-order, In-order und Post-order Traversierungen.

Moderationstipp

Geben Sie der Gruppenarbeit beim Bauen des Suchbaums konkrete Zeitvorgaben, um Diskussionen zu fokussieren.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern eine kleine Baumstruktur vor. Fordern Sie sie auf, die Knoten in Pre-order, In-order und Post-order zu traversieren und die Reihenfolge aufzuschreiben. Diskutieren Sie anschließend: Wann wäre eine bestimmte Traversierungsreihenfolge für eine praktische Anwendung (z.B. Drucken des Baumes, Kopieren des Baumes) besonders vorteilhaft?

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Aktivität 03

• Gruppenpuzzle
• 25 Min. · Einzelarbeit

Individuelle Programmierung

Jeder Schüler implementiert Pre-, In- und Post-order in Python oder Java. Sie testen mit eigenen Bäumen und messen Ausgaben.

Konstruieren Sie einen binären Suchbaum aus einer gegebenen Zahlenfolge und erklären Sie seine Eigenschaften.

Moderationstipp

Bereiten Sie für die individuelle Programmierung Beispielcode vor, der gezielt auf häufige Fehler bei Rekursion hinweist.

Worauf zu achten ist

Bitten Sie die Schülerinnen und Schüler, auf einem Zettel zu erklären, warum die In-order-Traversierung eines binären Suchbaums die Elemente in sortierter Reihenfolge liefert. Geben Sie ihnen eine Beispiel-Baumstruktur zur Veranschaulichung.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Aktivität 04

• Gruppenpuzzle
• 15 Min. · Ganze Klasse

Klassenrunde: Vergleich

Die Klasse diskutiert Beispiele aus dem Alltag, wie Dateisysteme, und wendet Traversierungen an. Lehrer moderiert.

Wie lassen sich hierarchische Informationen effizient in Baumstrukturen abbilden?

Worauf zu achten ist

Stellen Sie den Schülerinnen und Schülern eine Liste von Zahlen vor, z.B. 5, 3, 8, 1, 4, 7, 9. Bitten Sie sie, einen binären Suchbaum aus dieser Folge zu konstruieren und die Schritte zu dokumentieren. Überprüfen Sie die Korrektheit der Baumstruktur und die Einhaltung der Suchbaumeigenschaften.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit analogen Methoden wie dem Zeichnen von Bäumen auf Papier, bevor sie zu digitalen Tools übergehen. Sie betonen von Anfang an die Unterschiede zwischen allgemeinen binären Bäumen und Suchbäumen, um Verwechslungen zu vermeiden. Wichtig ist, die Traversierungen nicht nur theoretisch zu erklären, sondern durch konkrete Anwendungen wie das Ausdrucken oder Kopieren von Bäumen nachvollziehbar zu machen.

Am Ende der Einheit können die Schülerinnen und Schüler binäre Bäume korrekt zeichnen und die drei Traversierungsverfahren anwenden. Sie erkennen, wann ein Baum ein Suchbaum ist und begründen, welche Traversierung für eine bestimmte Aufgabe sinnvoll ist.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Gruppenarbeit 'Suchbaum bauen' achten Sie darauf, dass Schülerinnen und Schüler nicht automatisch annehmen, jeder binäre Baum sei sortiert.

  Fragen Sie gezielt: 'Erfüllt euer Baum die Bedingung, dass alle linken Kinder kleiner und alle rechten größer als der Elternknoten sind?' und lassen Sie sie dies an ihrem Beispiel überprüfen.

• Während der Klassenrunde 'Vergleich' hören Sie sich an, ob Schülerinnen und Schüler glauben, alle Traversierungen würden dieselbe Reihenfolge erzeugen.

  Zeigen Sie an einem konkreten Baumbeispiel, wie Pre-order, In-order und Post-order unterschiedliche Knotenfolgen ergeben, und lassen Sie die Klasse diese selbst eintragen.

• Während der individuellen Programmierung beobachten Sie, ob Schülerinnen und Schüler Traversierungen nur auf Blätter beschränken.

  Fordern Sie sie auf, in ihrem Code alle Knoten zu markieren und die Traversierungsfunktion auf innere Knoten zu testen.

---

In dieser Übersicht verwendete Methoden

• Gruppenpuzzle