Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== 3.0 Bäume ======
<WRAP center round info 80%>
Bei der Datenstruktur Liste hatte jedes Element nur einen Nachfolger (das letzte Element gar keinen). Lässt man mehrere Nachfolger zu, so erhält man die Datenstruktur **[[https://de.wikipedia.org/wiki/Baum_(Graphentheorie)|Baum]]**. \\ \\ 
Ein **Baum** 
  * besteht aus **Knoten**, in denen **Inhalte** abgelegt sind und **Kanten**, die jeweils zwei Knoten (genannt **Vorgänger** und **Nachfolger**) verbinden. 
  * Jeder Knoten hat dabei **maximal einen Vorgänger** 
  * (es gibt **genau einen Knoten ohne Vorgänger**, der als **Wurzel** bezeichnet wird) und 
  * **beliebig viele Nachfolger**. 
  * Knoten ohne Nachfolger heißen **Blatt**. 
  * Knoten, die **weder die Wurzel noch Blätter** sind heißen **innere Knoten**.
Baumstrukturen finden an vielen Stellen in der Informatik Verwendung, beispielsweise bei der Speicherung des Datenbestands von Datenbanken. Sie sorgen für effiziente Möglichkeiten zur Ablage und zum Abrufen von Daten. \\ \\ 
**Beispielbaum:**
{{ :baeume:pasted:20241018-075014.png?400 }} \\ 
//Oft stellt man den Baum so dar, dass die Kanten nach unten hin zu den Nachfolgerknoten zeigen. So spart man sich das Zeichen von Pfeilen.//
 \\ \\ 
**Abgrenzung zur allgemeineren Datenstruktur Graph:** \\ 
Ein Baum ist ein **zusammenhängender** **zyklenfreier** **ungerichteter** Graph. \\ \\ 
**Spezialfall Binärbaum:** \\ 
Ein **Binärbaum** ist ein Baum, in dem jeder Knoten **maximal zwei Nachfolger** hat.

</WRAP>

===== Umsetzung mittels Kompositum =====
<WRAP center round info 60%>
Verwendet man zur Implementierung eines Baumes das Entwurfsmuster Kompositum, so ergibt sich folgendes **Klassendiagramm**:
{{ :baeume:pasted:20241018-075355.png?400 }}
Sowohl die Wurzel, als auch innere Knoten und Blätter sind als Knoten angelegt. Die Klasse Abschluss kommt an den Stellen zum Einsatz, an denen es keine Nachfolger gibt. Die Ablage der Nachfolger kann beispielsweise über ein Array oder eine Liste geschehen. In vielen Anwendungsfällen ist die Speicherung in einem Array durchaus üblich (insbesondere da die Höchstzahl der Nachfolger häufig beschränkt wird).
</WRAP>
<WRAP center round hint 60%>
Die Implementierung  der Datenstruktur Baum in ihrer allgemeinen Form (d.h. Knoten haben **beliebig** viele Nachfolger) ohne weiteres Ordnungskriterium (s.u.) ist nicht prüfungsrelevant, daher gehen wir gleich zum Binärbaum über. 
</WRAP>


===== Binärbaum =====
<WRAP center round info 60%>
Ein **Binärbaum** ist ein Baum, bei dem jeder Knoten **maximal zwei Nachfolger** besitzt.
Das **Klassendiagramm** für die Implementierung eines Binärbaums unter Verwendung des Entwurfsmusters Kompositum ändert sich nur geringfügig:
{{ :baeume:pasted:20241018-075442.png }}
Die Kardinalität 2 anstelle von 0..2 im Klassendiagramm trifft (aus technischer Sicht) daher zu, als bei fehlenden Nachfolgeknoten Abschlussobjekte ihren Platz einnehmen.
</WRAP>

**Beispiel:**
{{ :baeume:pasted:20241018-075502.png?800 }}

Oft legt man bei der Darstellung nur Wert auf die Baumstruktur selbst und zeichnet vereinfacht:
{{ :baeume:pasted:20241018-075526.png?800 }}