|
Folien
Übungen
Programme
Bilder
 Zurück
|
Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 5: Bäume
|
|
|
Bäume gehören
zu den wichtigsten in der Informatik auftretenden Datenstrukturen. Entscheidungsbäume,
Syntaxbäume, Ableitungsbäume, Codebäume, spannende Bäume, baumartig
strukturierte Suchräume, Suchbäume und viele andere belegen die Allgegenwart
von Bäumen.
Bäume sind
verallgemeinerte Listenstrukturen. Ein Element ---üblicherweise
spricht man von Knoten --- hat nicht, wie im Falle linearer
Listen, nur einen Nachfolger, sondern eine endliche, begrenzte Anzahl von
sogenannten Söhnen. In
der Regel ist einer der Knoten als Wurzel des Baumes ausgezeichnet.
Das ist zugleich der einzige Knoten ohne Vorgänger. Jeder andere
Knoten hat einen (unmittelbaren) Vorgänger, der auch Vater des
Knotens genannt wird.
Eine Folge von Knoten eines Baumes heißt Pfad. Jeder von der Wurzel verschiedene Knoten eines Baumes ist
durch genau einen Pfad mit der Wurzel verbunden. Man kann Bäume als
spezielle planare, zyklenfreie Graphen auffassen. Die Knoten des Baumes
sind die Knoten des Graphen; je zwei Knoten p und q sind
durch eine Kante miteinander verbunden,
wenn q Sohn von p (und damit p Vater von q)
ist.
Ist unter
den Söhnen eines jeden Knotens eines Baumes eine Anordnung definiert, so
dass man vom ersten, zweiten, dritten
usw. Sohn eines Knotens sprechen kann, so nennt man den Baum geordnet.
Dies darf man nicht mit der Ordnung
eines Baumes verwechseln. Darunter versteht man nämlich die
maximale Anzahl von Söhnen eines Knotens. Besonders wichtig sind geordnete
Bäume der Ordnung 2; sie heißen auch binäre Bäume oder Binärbäume.
Statt vom ersten und zweiten Sohn spricht man bei Binärbäumen vom linken
und rechten Sohn eines Knotens. Wir werden in diesem Kapitel nur
geordnete Bäume betrachten.
|
|
Bei Fragen zu
dem Inhalt des Buches senden Sie bitte eine Email an ad-buch@informatik.uni-freiburg.de.
|
|