Die Einführung und der Schlussteil werden gemeinsam erstellt. Die einzelnen Kapitel sind Individualarbeiten. Timur, Teil 1 und 3; Björn, Teil 2 und 4.

• Ein Kapitel umfasst 20 - 90 Minuten Unterricht.
• Das gesamte Leitprogramm umfasst 3 - 10 Unterrichtslektionen.

Das Leitprogramm richtet sich an Fachhochschul-Studenten und Studentinnen im 2. Semester des Informatik- oder Elektrotechnikstudiums. Im Besonderen ist dieses Leitprogramm für den Einsatz im Modul «Programmieren II» der Hochschule für Technik und Architektur Luzern (HTA) ausgerichtet.

Dieses Leitprogramm erläutert die wichtigsten Begriffe, Definitionen und Eigenschaften von Bäumen in der Informatik. Grundverstäntnisse für die Anwendung und Vorzüge von Suchbäumen als Datenstrukturen werden geschaffen. Die vier grundlegenden Operationen Traversierung, Einfügen, Löschen und Suchen werden erklärt und in Übungen programmiert. Im weiteren wird die Notwendigkeit für die Balacierung aufgezeigt und anhand der AVL-Bäume eine konkrete Methode geschildert.

• Der Student beherscht die wesentlichen Aspekte einer Programmiersprache z.B. Java.
• Stack, (verkettete) Liste, Queue und Rekursion.

Bäume sind ein wichtiges Konzept der Informatik und tretten in den verschiedensten Bereichen auf. Im besonderen sind Bäume eine wichtige Datenstruktur für die effiziente Speicherung von Daten und deren schnelle Auffindung.

• Der Student weiss, für was Bäume (im Speziellen Binärbäume) in der Informatik bzw. Programmierung gut sind.
• Er lennt die wesentlichen Unterschiede zu anderen Datenstrukturen, wie Listen, Stacks und Queues.
• Der Student kann wesentliche Algorithmen (Suchen, Einfügen, Traversieren) implementieren.
• Im weiteren kennt er die Idee von balancierten Bäumen am Beispiel von AVL-Bäumen.
• Am Ende des Leitprogramms sind die Studenten in der Lage, sich selbständig in weiterführender Literatur über Bäume zu informieren.

• Die Studentin kann einen Binären Suchbaum programmieren, welcher die Methoden Suchen, Einfügen und die Traversierung korrekt implementiert.
• Der Student kann evaluieren ob ein Binärer Suchbaum für ein gegebenes Problem die geeignetste Datenstruktur ist.

Als Additum werden schwierigere Aufgaben z.B. das Löschen von Knoten und das implementieren von AVL-Bäume behandelt. Diese werden in den einzelnen Kapitel wiedergegeben und mit einem Stern markiert.

@book{goodrich,
	Address = {Hoboken},
	Author = {Michael T. Goodrich and Roberto Tamassia},
	Edition = {3.},
	Isbn = {0-471-46983-1},
	Publisher = {John Wiley & Sons, Inc.},
	Title = {Data Structures and Algorithms in JAVA},
	Year = {2004}}

@book{widmayer,
	Address = {Heidelberg, Berlin},
	Author = {Thomas Ottmann and Peter Widmayer},
	Edition = {4.},
	Publisher = {Spektrum, Akad. Verl.},
	Title = {Algorithmen und Datenstrukturen},
	Year = {2002}}

Die Einleitung zeigt Bäume als Strukturierungsmittel und erläutert diese mit Beispielen und Verwendungsmöglichkeiten.

~ 15 min.

Die ersten Begriffe werden umgangssprachlich eingeführt: Baum, Blätter, Knoten, Wurzel, Vater, Kind, Geschwister, Vorfahren, Nachkommen, Höhe, Tiefe und Grad. Im weiteren geordnete und ungeordnete Bäume.

~ 30 min.

Um sich mit Algorithmen und Anwendungen im Zusammenhang mit Bäumen zu befassen, ist es erforderlich, dass der Student die grundlegenden Begriffe und Definitionen im Gebiet der Bäume kennt.

• Der Student kann die wesentlichen Elemente eines Baumes erkennen und umgangssprachlich beschreiben.
• Am Ende dieses Kapitels sind die Studenten in der Lage, sich selbständig in weiterführender Literatur über Bäume zu informieren.

• Am Schluss dieses Kapitels kann der Student drei Beispielanwendungen von Bäumen aufzählen.
• Der Student kann die Definition von Bäumen, Elementen und Eigenschaften korrekt wiedergeben.

• Erkennen, Erläutern und Anwenden der Elemente und Eigenschaften von Bäumen.

• Kennenlernen verschiedener Bäume
• Idee der Darstellung aller Bäume in Form von Binärbäumen

Der Binäre Suchbaum wird implementiert und traversiert.

~ 60 min

Um Binärbäume korrekt in einem Programm als Datenstruktur anzuwenden, ist es erforderlich, dass der Student den Aufbau und die Implementierung eines Binärbaumes und dessen Methoden kennt.

• Der Student weiss wie der Binärbaum als Datenstruktur anzuwenden ist.
• Ausserdem kennt er die drei verschiedenen Traversierungsarten und deren Eigenschaften.

• Der Student kann die wichtigsten vier Operationen (Methoden) eines Binärbaumes als Datenstruktur und deren Bedeutung auflisten.
• Er kann die Strukturen bzw. Klassen implementieren die für die Repräsentation eines Binärbaumes nötig sind.
• Ebenfalls kann er die Operation traversieren() schreiben, welche den Baum in den drei verschiedenen Arten traversiert.
• Die Studentin kann für jede der drei Traversierungsarten eine Beispielanwendung angeben mit ensprechender Begründung, weshalb diese Traversierungsart angewendet wird.

• Grundstruktur der Bäume programmieren.
• Implementieren und aufzeichnen der Traversierungsarten.

• keine

Der Student lernt die Theorie zum Einfügen und Suchen eines Elements kennen und kann diese dann gleich in die Praxis umsetzen. Das etwas schwierigere Löschen wird nur erläutert.

~ 120 min

Die wichtigsten Operationen Suchen, Einfügen und Löschen sind für den Einsatz von Suchbäumen als Datenstruktur unerlässlich. Für eine bestmögliche Anwendung der Bäume ist die Kenntnis über die Implementierung dieser Operationen nötig.

• Der Student kann in einem Baum Suchen, Einfügen und Löschen.
• Er kann die Algorithmen für das Suchen und Einfügen implementieren.
• Der Student weiss wieso das Löschen schwierig sein kann.

• Der Student kann die Methoden Suchen und Einfügen vollständig und korrekt ausprogrammmieren.
• Er kann den Algorithmus zum Löschen eines Elementes graphisch an einem gegebenen Beispiel aufzeigen.

• Programmierung von Suchen und Einfügen.
• Aufzeigen von Löschen.

• Programmierung von Löschen.

Was heisst balanciert? Was sind die Vorteile? Nachteile? Verstehen des Konzeptes von balancierten Bäumen anhand von AVL-Bäumen.

~ 90 min

Für die effiziente Anwendung von Binärbäumen als Datenstruktur ist ein balacierungs Kriterium notwendig, damit die Suchbäume ihre leistungsfähige Struktur langzeitig beibehalten.

• Die Studenten wissen wozu die Balancierung notwendig ist.
• Sie sind in der Lage sich selbständig in weiterführender Literatur über weitere Balancierungsarten und die Balacierung selbst zu informieren.

• Der Student kann die Balancierungsart der AVL-Bäume anhand von Beispielen erläutern.
• Er kann für gegebene unbalacierte Bäume grafisch eine Balacierung nach der AVL-Methode durchführen.

• Übungen für die Anwendung und das Konzept der AVL-Balacierung.

• Graphisches Durchspielen der AVL-Methode anhand von Beispielen.
• Implementierung eines AVL-balacierten Binärensuchbaumes.