[Lehrstuhl A&D]  [Institut für Informatik]  [Universität Freiburg] 

Folien

Übungen

Programme

Bilder

< Zurück

Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 5: Bäume

Spektrum Verlag

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.
Algorithmen und Datenstrukturen

Stefan Edelkamp (edelkamp@informatik.uni-freiburg.de)