Diese Seiten können nicht richtig dargestellt werden, da Sie Ihren Internet Explorer mit aktivierter Kompatibiltätsansicht verwenden. Wir empfehlen 'fu-berlin.de' aus der Liste der Websites mit aktivierter Kompatibilitätsansicht zu entfernen:
- Blenden Sie bitte in Ihrem Internet Explorer die Menüleiste ein, indem Sie entweder 'Alt' drücken oder in der Adressleiste mit der rechten Maustaste klicken und dann 'Menüleiste' auswählen.
- Klicken Sie auf 'Extras' und wählen das Menü 'Einstellungen der Kompatibilitätsansicht' aus.
- Wählen Sie unter 'Zur Kompatibilitätsansicht hinzugefügte Websites' 'fu-berlin.de' aus.
- Klicken Sie auf 'Entfernen'.
Binärbaum (2. Semester)
Im Modul Algorithmen, Datenstrukturen und Datenabstraktion des Studienbereichs Algorithmen und Programmierung lernen die Studierenden viele verschiedene Datenstrukturen kennen, darunter den Graphen und dessen Variationen.
In der Graphentheorie versteht man unter einem Binärbaum eine spezielle Form eines Graphen. Er ist entweder leer oder er besitzt eine Wurzel, welche ganz oben dargestellt wird, und gegebenenfalls darunter weitere Knoten (siehe Abbildung unten). An jedem Knoten können maximal zwei Kindknoten hängen. Wenn zwei weitere Knoten daran hängen, bezeichnet man diesen als inneren Knoten. Sollte nur ein weiterer Knoten daran hängen, wird er als Halbknoten und falls kein weiterer Knoten daran hängt als Blatt bezeichnet.
Der unten abgebildete Baum soll so aufgebaut werden, dass alles, was lexikographisch gesehen kleiner als der aktuelle Knoten ist, links von diesem und alles, was größer ist, rechts von diesem abgelegt wird. Ein Wort ist lexikographisch kleiner als ein anderes, wenn es im Wörterbuch zuerst auftaucht.
Ordnen Sie die Wörter in lexikographischer Reihenfolge in den Binärbaum ein, sodass die oben beschriebene Vorschrift der Sortierung erfüllt ist. Ziehen Sie die Wörter per Drag & Drop in den Binärbaum.
Informatik
Logik
Studium
Programmieren
Information
Mathematik
Da bei einem sortierten Binärbaum das kleinste Element, in diesem Fall "Informatik", ganz links zu finden ist, ist es auch das erste Element, das einsortiert werden kann. Eine Ebene höher, neben "Informatik" findet man "Information". Rechts davon muss ein Element platziert werden, dass etwas größer ist, in diesem Fall "Logik". In die Wurzel (ganz oben) kommt dann "Mathematik", rechts davon "Programmieren" und rechts davon wiederum "Studium". Die Elemente können nur so in den Binärbaum einsortiert werden.
