Glanz: aiMOOC über GPT aiMOOC Action erstellt

2026-09-22T21:17:39Z

aiMOOC über GPT aiMOOC Action erstellt

Neue Seite

{{T}}

{{BR}}
= Baumstruktur =

{{BR}}
= Einleitung =
Eine '''Baumstruktur''' ist in der Informatik eine hierarchische [[Datenstruktur]]. Sie besteht aus '''Knoten''' und '''Kanten'''. Bei einem gewurzelten Baum gibt es genau eine '''Wurzel'''. Jeder andere Knoten besitzt genau einen Elternknoten, kann aber mehrere Kinder haben. Dadurch lassen sich verzweigte Beziehungen übersichtlich darstellen.

Dieser aiMOOC richtet sich an Lernende der '''Sekundarstufe II''' und der '''beruflichen IT-Ausbildung'''. Du lernst die Grundbegriffe, den [[Binärbaum]], den [[Binärer Suchbaum|binären Suchbaum]] und wichtige Arten der [[Traversierung]] kennen.

[[Datei:Baum Begriffe.svg|500px|rahmenlos|center]]

{{#ev:youtube| https://www.youtube.com/watch?v=wSH022YuRQk |500|center}}

{{BR}}
= Grundidee und Fachbegriffe =
Ein Baum beginnt an der '''Wurzel''' und verzweigt sich über Kanten zu weiteren Knoten. Ein Knoten ohne Kinder heißt '''Blatt'''. Ein Knoten zusammen mit allen darunterliegenden Knoten bildet einen '''Teilbaum'''.

{| class="wikitable"
! Begriff
! Bedeutung
|-
| Wurzel
| Oberster Ausgangsknoten eines gewurzelten Baums
|-
| Elternknoten
| Direkter Vorgänger eines Knotens
|-
| Kindknoten
| Direkter Nachfolger eines Knotens
|-
| Blatt
| Knoten ohne Kinder
|-
| Tiefe
| Anzahl der Kanten von der Wurzel bis zu einem Knoten
|-
| Höhe
| Länge des längsten abwärts führenden Pfads bis zu einem Blatt
|}

[[Datei:Binary tree structure.svg|500px|rahmenlos|center]]

{{BR}}
== Baum und Teilbaum ==
Die Struktur ist '''rekursiv''': Jeder Teilbaum ist selbst wieder ein Baum. Diese Eigenschaft macht Bäume besonders geeignet für rekursive [[Algorithmus|Algorithmen]]. Ein Baum mit nur einem Knoten besteht ausschließlich aus seiner Wurzel.

{{BR}}
= Binärbaum =
Ein '''Binärbaum''' ist ein Baum, bei dem jeder Knoten höchstens zwei Kinder besitzt. Meist spricht man vom '''linken''' und '''rechten''' Kind. Ein Binärbaum muss nicht vollständig und auch nicht automatisch sortiert sein.

[[Datei:CPT BinaryTree NumberEx1.svg|500px|rahmenlos|center]]

{{BR}}
== Binärer Suchbaum ==
Ein '''binärer Suchbaum''' ergänzt den Binärbaum um eine Ordnungsregel. In einer üblichen Variante liegen kleinere Schlüssel im linken und größere Schlüssel im rechten Teilbaum. Dadurch kann die Suche nach einem Wert schrittweise auf einen Teilbaum eingeschränkt werden.

[[Datei:Binary search tree.svg|450px|rahmenlos|center]]

{{#ev:youtube| https://www.youtube.com/watch?v=t7KZobZqm78 |500|center}}

Für die Laufzeit ist die '''Höhe''' entscheidend. Suchen benötigt im Wesentlichen Zeit proportional zur Baumhöhe. Bei einem balancierten Suchbaum ist die Höhe typischerweise logarithmisch zur Anzahl der Knoten. Ein stark entarteter Baum kann dagegen nahezu wie eine Liste aussehen und eine lineare Suchzeit verursachen.

{{BR}}
= Traversierung =
Unter '''Traversierung''' versteht man das systematische Besuchen aller Knoten eines Baums. Bei einem Binärbaum sind besonders vier Reihenfolgen wichtig:

{| class="wikitable"
! Verfahren
! Reihenfolge
! Idee
|-
| Preorder
| Knoten – linker Teilbaum – rechter Teilbaum
| Der aktuelle Knoten wird zuerst verarbeitet
|-
| Inorder
| Linker Teilbaum – Knoten – rechter Teilbaum
| Bei binären Suchbäumen entstehen die Schlüssel in sortierter Reihenfolge
|-
| Postorder
| Linker Teilbaum – rechter Teilbaum – Knoten
| Der aktuelle Knoten wird zuletzt verarbeitet
|-
| Levelorder
| Ebene für Ebene
| Die Suche erfolgt in die Breite
|}

[[Datei:Preorder-traversal.gif|400px|rahmenlos|center]]
[[Datei:Inorder-traversal.gif|400px|rahmenlos|center]]
[[Datei:Postorder-traversal.gif|400px|rahmenlos|center]]
[[Datei:Sorted binary tree breadth-first traversal.svg|500px|rahmenlos|center]]

{{#ev:youtube| https://www.youtube.com/watch?v=SWgwCbDmtGE |500|center}}

Eine vollständige Traversierung besucht jeden Knoten. Für einen Baum mit n Knoten liegt der Aufwand deshalb in Θ(n).

{{BR}}
= Anwendungen =
Baumstrukturen findest Du in vielen Bereichen der Informatik. Verzeichnisstrukturen werden häufig baumartig dargestellt. Auch das [[Document Object Model|DOM]] einer Webseite, Syntaxbäume in Programmiersprachen, Entscheidungsbäume und verschiedene Datenbankindizes nutzen hierarchische oder baumartige Strukturen.

{{BR}}
== Warum Baumstrukturen nützlich sind ==
Bäume bilden Hierarchien direkt ab und erlauben oft effiziente Such-, Einfüge- und Löschoperationen. Die konkrete Effizienz hängt jedoch von der Baumart und ihrer Form ab. Deshalb gibt es balancierte Suchbäume wie [[AVL-Baum|AVL-Bäume]] oder [[Rot-Schwarz-Baum|Rot-Schwarz-Bäume]] sowie mehrwegige Strukturen wie [[B-Baum|B-Bäume]].

{{BR}}
= Interaktive Aufgaben =

{{BR}}
== Quiz: Teste Dein Wissen ==

{{MC}}

'''Wie heißt der oberste Knoten eines gewurzelten Baums?'''
(Wurzel)
(!Blatt)
(!Kante)
(!Teilbaum)

{{E}}
<br>

{{MC}}

'''Wie heißt ein Knoten ohne Kinder?'''
(Blatt)
(!Wurzel)
(!Elternknoten)
(!Suchpfad)

{{E}}
<br>

{{MC}}

'''Wie viele Kinder kann ein Knoten in einem Binärbaum höchstens haben?'''
(Zwei)
(!Eins)
(!Drei)
(!Beliebig viele)

{{E}}
<br>

{{MC}}

'''Wie viele Elternknoten besitzt jeder Nichtwurzelknoten in einem gewurzelten Baum?'''
(Einen)
(!Keinen)
(!Zwei)
(!Beliebig viele)

{{E}}
<br>

{{MC}}

'''Welche Aussage beschreibt einen binären Suchbaum in einer üblichen Ordnung?'''
(Kleinere Schlüssel liegen links und größere rechts)
(!Alle Schlüssel liegen nur in den Blättern)
(!Jeder Knoten besitzt genau zwei Kinder)
(!Die Wurzel ist immer der kleinste Schlüssel)

{{E}}
<br>

{{MC}}

'''Welche Traversierung besucht beim Binärbaum zuerst den linken Teilbaum, dann den Knoten und danach den rechten Teilbaum?'''
(Inorder)
(!Preorder)
(!Postorder)
(!Levelorder)

{{E}}
<br>

{{MC}}

'''Welche Traversierung arbeitet Ebene für Ebene?'''
(Levelorder)
(!Inorder)
(!Postorder)
(!Preorder)

{{E}}
<br>

{{MC}}

'''Wovon hängt die Suchzeit in einem binären Suchbaum wesentlich ab?'''
(Von der Höhe des Baums)
(!Von der Farbe der Knoten)
(!Von der Bildschirmgröße)
(!Von der Dateiendung)

{{E}}
<br>

{{MC}}

'''Welchen Aufwand hat eine vollständige Traversierung mit n Knoten?'''
(Linear)
(!Konstant)
(!Quadratisch)
(!Unabhängig von der Knotenzahl)

{{E}}
<br>

{{MC}}

'''Was ist ein Teilbaum?'''
(Ein Knoten mit allen darunterliegenden Knoten)
(!Nur die Wurzel ohne Nachfolger)
(!Eine einzelne Kante)
(!Eine sortierte Liste ohne Verzweigung)

{{E}}
<br>

{{BR}}
== Memory ==
<div class="memo-quiz">
{|
|-
| Wurzel || Oberster Ausgangsknoten
|-
| Blatt || Knoten ohne Kinder
|-
| Kante || Verbindung zwischen Knoten
|-
| Tiefe || Abstand eines Knotens von der Wurzel
|-
| Teilbaum || Hierarchie unterhalb eines gewählten Knotens
|-
| Traversierung || Systematisches Besuchen von Knoten
|}
{{E}}
<br>

{{BR}}
== Drag and Drop ==
<div class="lueckentext-quiz">

{| class="wikitable"
! Ordne die richtigen Begriffe zu.
! Beschreibung
|-
| '''Wurzel'''
| Startpunkt eines gewurzelten Baums
|-
| '''Blatt'''
| Endknoten ohne Kinder
|-
| '''Preorder'''
| Knoten vor den beiden Teilbäumen
|-
| '''Inorder'''
| Knoten zwischen linkem und rechtem Teilbaum
|-
| '''Postorder'''
| Knoten nach den beiden Teilbäumen

|}
{{E}}

<br>
<br />

{{BR}}
== Kreuzworträtsel ==
<div class="kreuzwort-quiz">
{|
|-
| Wurzel || Wie heißt der oberste Knoten eines gewurzelten Baums?
|-
| Blatt || Wie heißt ein Knoten ohne Kinder?
|-
| Knoten || Wie heißt ein einzelnes Element eines Baums?
|-
| Kante || Wie heißt die Verbindung zwischen zwei Knoten?
|-
| Binärbaum || Wie heißt ein Baum mit höchstens zwei Kindern pro Knoten?
|-
| Traversierung || Wie heißt das systematische Besuchen aller Knoten?
|}
{{E}}
<br>

{{BR}}
== LearningApps ==
<iframe> https://learningapps.org/index.php?s=Baumstruktur </iframe>

{{BR}}
== Lückentext ==
<quiz display=simple>
{'''Vervollständige den Text.'''<br>
|type="{}"}
Eine hierarchische Datenstruktur mit Knoten und Kanten heißt { Baum }. Der oberste Ausgangsknoten wird { Wurzel } genannt. Ein Knoten ohne Kinder heißt { Blatt }. In einem Binärbaum besitzt jeder Knoten höchstens { zwei } Kinder. Ein binärer Suchbaum ordnet kleinere Schlüssel typischerweise im { linken } Teilbaum ein. Bei der { Inorder }-Traversierung wird der Knoten zwischen linkem und rechtem Teilbaum besucht. Die Levelorder-Traversierung arbeitet { ebenenweise }. Die Laufzeit einer Suche hängt wesentlich von der { Höhe } des Baums ab.
</quiz>

<br>

{{BR}}
= Offene Aufgaben =

{{BR}}
=== Leicht ===
# [[Baumdiagramm]]: Zeichne eine Baumstruktur mit mindestens acht Knoten und markiere Wurzel, Elternknoten, Kindknoten und Blätter.
# [[Dateisystem]]: Untersuche eine Ordnerstruktur auf Deinem Gerät und übertrage einen kleinen Ausschnitt als Baumdiagramm.
# [[Binärbaum]]: Erstelle einen Binärbaum aus frei gewählten Begriffen und prüfe, ob jeder Knoten höchstens zwei Kinder hat.
# [[Fachbegriffe]]: Gestalte eine Lernkarte, auf der Du Wurzel, Blatt, Tiefe, Höhe und Teilbaum mit eigenen Beispielen erklärst.

{{BR}}
=== Standard ===
# [[Binärer Suchbaum]]: Füge die Werte 8, 3, 10, 1, 6, 14, 4 und 7 nacheinander in einen binären Suchbaum ein und dokumentiere jeden Schritt.
# [[Traversierung]]: Bestimme für Deinen Suchbaum Preorder, Inorder, Postorder und Levelorder und vergleiche die Ergebnisse.
# [[Algorithmus]]: Formuliere in Pseudocode eine rekursive Preorder-Traversierung und erläutere den Abbruchfall.
# [[Vergleich von Datenstrukturen]]: Vergleiche eine lineare Liste mit einem balancierten Suchbaum für die Aufgabe, häufig Werte zu suchen.

{{BR}}
=== Schwer ===
# [[Laufzeitanalyse]]: Konstruiere zwei Suchbäume mit denselben Schlüsseln, aber sehr unterschiedlicher Höhe, und erkläre die Folgen für die Suche.
# [[AVL-Baum]]: Recherchiere, warum Balancierung bei Suchbäumen wichtig ist, und stelle das Prinzip eines AVL-Baums in einem eigenen Schaubild dar.
# [[DOM]]: Untersuche die DOM-Struktur einer einfachen Webseite mit Entwicklerwerkzeugen und dokumentiere einen Teilbaum mit mindestens drei Ebenen.
# [[Programmierung]]: Implementiere einen einfachen binären Suchbaum mit Einfügen, Suchen und Inorder-Traversierung in einer Programmiersprache Deiner Wahl.

{{:Offene Aufgabe - MOOC erstellen}}

{{BR}}
= Lernkontrolle =
# [[Modellierung]]: Eine Schule möchte Fächer, Kurse und Lernmaterialien hierarchisch organisieren. Entwirf eine passende Baumstruktur und begründe Deine Wahl der Knotenebenen.
# [[Fehleranalyse]]: Ein Suchbaum enthält links von einem Knoten einen größeren Schlüssel. Erkläre, welche Eigenschaft verletzt ist und welche Folgen das für die Suche haben kann.
# [[Effizienz]]: Vergleiche einen balancierten und einen stark entarteten Suchbaum mit gleich vielen Knoten. Erkläre ohne konkrete Messung, warum sich Suchzeiten unterscheiden können.
# [[Traversierung]]: Wähle für das Ausgeben aller Schlüssel eines binären Suchbaums in aufsteigender Reihenfolge eine Traversierung und begründe Deine Entscheidung.
# [[Transfer]]: Erkläre an einem selbst gewählten Beispiel außerhalb der Informatik, welche Beziehungen sich sinnvoll als Baum darstellen lassen und wo das Modell an Grenzen stößt.
# [[Algorithmisches Denken]]: Beschreibe, wie eine Breitensuche und eine Tiefensuche denselben Baum unterschiedlich erkunden und nenne je eine passende Anwendungssituation.

<br>
<br>

{{BR}}
= Lernnachweis =
Für einen Lernnachweis solltest Du zeigen, dass Du:
# die Grundbegriffe einer Baumstruktur sicher und an einem Diagramm erklären kannst,
# Binärbäume und binäre Suchbäume unterscheiden kannst,
# Suchpfade in einem binären Suchbaum nachvollziehen kannst,
# Preorder, Inorder, Postorder und Levelorder korrekt anwenden kannst,
# den Einfluss der Baumhöhe auf die Effizienz begründet einschätzen kannst,
# eine reale Hierarchie als Baum modellieren und die Grenzen des Modells benennen kannst.

<br>
<br>

{{BR}}
= OERs zum Thema =
<iframe> https://de.m.wikipedia.org/wiki/Baum_(Datenstruktur) </iframe>

<br>

{{BR}}
= Verknüpfte Lernbereiche =
{| align=center
{{:D-Tab}}
'''[[Baumstruktur]]'''
# [[Datenstruktur]]
# [[Binärbaum]]
# [[Binärer Suchbaum]]
# [[Traversierung]]
# [[Rekursion]]
# [[Algorithmus]]
# [[Graphentheorie]]
|}

[[Kategorie:Informatik]]
[[Kategorie:Datenstruktur]]
[[Kategorie:Algorithmen]]
[[Kategorie:Sekundarstufe II]]
[[Kategorie:Ausbildung]]

{{BR}}
= aiMOOC-Projekte =
[[Kategorie:AI_MOOC]] [[Kategorie:GPT aiMOOC]]
{{MT}}

Baumstruktur - Versionsgeschichte

Glanz: aiMOOC über GPT aiMOOC Action erstellt