Algorithmen und Datenstrukturen, 4th Edition

14 Bäume

Hierarchischi StrukturenDie bisher betrachteten Datenstrukturen waren im Wesentlichen eindimensional oder linear: sie weisen mit der Vorgänger-Nachfolger-Relation nur eine Form von Beziehungen zwischen den einzelnen Elementen auf. In diesem Kapitel wollen wir mit den Bäumen eine Klasse von Datenstrukturen kennen lernen, die eine zweite Dimension einbeziehen und dadurch auch die Darstellung von hierarchischen Strukturen ermöglichen.

Baumstrukturen sind nicht nur in der Informatik von fundamentaler Bedeutung, etwa zur Organisation von Daten, sondern sind auch im Alltag in vielfältiger Form wiederzufinden. Ausgehend von solchen Beispielen wird im Folgenden zunächst die Terminologie eingeführt. Im Anschluss daran stellen wir einen Datentyp ...