Benutzer:Mischa004/baum
Ein Baum ist in der Informatik eine wichtige Datenstruktur. Ihr Vorteil gegenüber anderen Datenstrukturen liegt darin, dass bei der Speicherung von Daten in Bäumen sowohl die Operationen Suchen und Durchsuchen sowie die Operationen Einfügen und Löschen mit geringer Komplexität durchgeführt werden können.
Ein Baum besteht aus einer Menge von Knoten, die durch Kanten miteinander verbunden sind. Der erste Knoten hat keinen Vaterknoten und wird als Wurzelknoten bezeichnet. Die letzten Knoten eines Baumes haben hingegen keine Nachkommen und werden Blätter genannt.
Die häufigste Art der Datenstruktur Baum ist der Binärbaum, in welchem jeder Knoten nur höchstens zwei Nachkommen haben darf.
Implementierung[Bearbeiten | Quelltext bearbeiten]
Erstellung[Bearbeiten | Quelltext bearbeiten]
↑J ist ein Zeiger auf den Knoten J, der die Wurzel des Baumes bildet. ↑F ist ein Zeiger auf den linken Nachfolger F und ↑P ein Zeiger auf den rechten Nachfolger P. P hat keine weiteren Nachfolger, die Zeiger zeigen auf 0.Bäume können in allen wichtigen Programmiersprachen hergestellt und verwaltet werden. Der beispielsweise in Pascal angewandte Vorgang zur Erstellung eines Baumes beginnt mit dem Reservieren von Speicherplatz für genau einen Verbund (record) im dynamischen Speicher. Dafür wird einfach ein neuer Zeiger auf einen Verbund erstellt: new (ZeigerAufRecord). Anschließend wird der Verbund bearbeitet, auf den dieser Zeigt zeigt. In eine Komponente des Verbunds schreibt man Daten: ZeigerAufRecord^.Name := Franz, in andere Komponenten schreibt man wiederum Zeiger, welche den Verbund mit anderen Verbünden verknüpfen und somit zu Knoten eines Baumes machen: ZeigerAufRecord^.LinkerNachfolger := VerbundXY und ZeigerAufRecord^.RechterNachfolger := VerbundXY.
Durchlauf[Bearbeiten | Quelltext bearbeiten]
Um sämtliche in einem Binärbaum gespeicherte Daten zu erhalten, müssen alle Knoten durchlaufen werden. Für die Reihenfolge in der die Knoten durchlaufen werden, haben sich vier Möglichkeiten durchgesetzt: der Durchlauf in Preorder, Postorder, Inorder und Levelorder.
Literatur[Bearbeiten | Quelltext bearbeiten]
- Hartmut Ernst, Jochen Schmidt, Gerd Beneken: Grundkurs Informatik. Grundlagen und Konzepte für die erfolgreiche IT-Praxis – Eine umfassende, praxisorientierte Einführung, 5. Auflage, Springer, Wiesbaden 2015, S. 523–596