Informatik 12/13 (G9)

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Zuletzt angesehen:
baeume:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung		Vorhergehende Überarbeitung
baeume:start [2024/10/18 05:53] – [Bäume] Martin Pabstbaeume:start [2024/10/18 08:41] (aktuell) – Martin Pabst
Zeile 1: Zeile 1:
-====== Bäume ======+====== 3.0 Bäume ======
 <WRAP center round info 80%> <WRAP center round info 80%>
-Bei den bisher behandelten Datenstrukturen [[datenstrukturen:warteschlange:start|Warteschlange]] und [[datenstrukturen:stapel:start|Stapel (Stack)]] 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]]**. \\ \\ +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**  Ein **Baum** 
   * besteht aus **Knoten**, in denen **Inhalte** abgelegt sind und **Kanten**, die jeweils zwei Knoten (genannt **Vorgänger** und **Nachfolger**) verbinden.    * besteht aus **Knoten**, in denen **Inhalte** abgelegt sind und **Kanten**, die jeweils zwei Knoten (genannt **Vorgänger** und **Nachfolger**) verbinden. 
Zeile 11: Zeile 11:
 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. \\ \\  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:** **Beispielbaum:**
-{{:baeume:pasted:20241018-075014.png?400}} \\ +{{ :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.// //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.//
  \\ \\   \\ \\ 
Zeile 24: Zeile 24:
 <WRAP center round info 60%> <WRAP center round info 60%>
 Verwendet man zur Implementierung eines Baumes das Entwurfsmuster Kompositum, so ergibt sich folgendes **Klassendiagramm**: Verwendet man zur Implementierung eines Baumes das Entwurfsmuster Kompositum, so ergibt sich folgendes **Klassendiagramm**:
-{{ :datenstrukturen:baeume:pasted:20210919-151857.png?400 }}+{{ :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). 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>
Zeile 36: Zeile 36:
 Ein **Binärbaum** ist ein Baum, bei dem jeder Knoten **maximal zwei Nachfolger** besitzt. 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: Das **Klassendiagramm** für die Implementierung eines Binärbaums unter Verwendung des Entwurfsmusters Kompositum ändert sich nur geringfügig:
-{{ :datenstrukturen:baeume:binaerbaum.png |}}+{{ :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. 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> </WRAP>
  
 **Beispiel:** **Beispiel:**
-{{ :datenstrukturen:baeume:pasted:20211018-120433.png?800 }}+{{ :baeume:pasted:20241018-075502.png?800 }}
  
 Oft legt man bei der Darstellung nur Wert auf die Baumstruktur selbst und zeichnet vereinfacht: Oft legt man bei der Darstellung nur Wert auf die Baumstruktur selbst und zeichnet vereinfacht:
-{{ :datenstrukturen:baeume:pasted:20211018-154625.png?800 }}+{{ :baeume:pasted:20241018-075526.png?800 }} 
baeume/start.1729230814.txt.gz · Zuletzt geändert: 2024/10/18 05:53 von Martin Pabst
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki