WikiDer > Baum (Datenstruktur)
EIN Baum oder Baumstruktur ist ein Datenstruktur in dem Informatik was ein Spezialfall von a . ist Anzahl ist. Ein Baum besteht aus a Knoten) oder Scheitel dass die Stamm (ebenfalls Wurzel) und welches der Einstiegspunkt für die im Baum gespeicherten Informationen ist. In diesem Wurzelknoten sitze null oder mehr Zeiger auf andere Knoten verweisen. Jeder Knoten außer der Wurzel hat genau a Elternteil und null oder mehr Kinder. Verweise gehen daher nie zwischen den Kindern selbst, sondern nur von Eltern zu Kind; in einer etwas umfangreicheren Version, eventuell auch vom Kind zum Elternteil (bidirektionaler Graph). Es gibt keine kreisförmigen Pfade in einem Baum und es gibt immer genau 1 Pfad von der Wurzel zu einem beliebigen Knoten. Ein Knoten, der keine eigenen Kinder hat, heißt a Blatt.
Binärbaum
EIN binär oder dichotom Baum ist eine Baumstruktur, bei der jeder Knoten maximal zwei Kinder hat. EIN kompletter Binärbaum ist eine Baumstruktur, bei der alle Ebenen außer möglicherweise der letzten vollständig gefüllt sind und alle Knoten der letzten Ebene links liegen. Jeder Baum kann ganz einfach in einen binären Baum umgewandelt werden. Ein Baum kann auch für jeden Graphen erstellt werden, der keine unzusammenhängenden Knoten hat. EIN bestellter Baum ist eine Baumstruktur, in der die Kinder eine definierte Reihenfolge haben.
Algorithmen
Für Baumstrukturen gibt es eine Vielzahl bekannter Algorithmen, um beispielsweise etwas in einem geordneten Baum nachzuschlagen, ein neues Element in einem geordneten Baum hinzuzufügen oder zu entfernen oder einen ungeordneten Baum zu sortieren (in einen geordneten Baum umzuwandeln). Besitzt ein Baum bestimmte Eigenschaften, können diese Algorithmen oft verfeinert (und daher meist auch beschleunigt) werden. Bäume können verwendet werden, um alle Arten von Problemen in der Informatik darzustellen.
Siehe auch
 | Siehe die Kategorie Baumstrukturen von Wikimedia Commons für Mediendateien zu diesem Thema. |