Baum

Ein Baum ist eine der am häufigsten verwendeten rekusiven Datanstrukturen. Die in dieser Veranstaltung behandelten Bäume sind alles binäre Bäume. Bäume eignen sich vor allem zum strukturierten Abspeichern von Daten. Die interne repräsentation hängt dabei von der Implementierung der Datanstruktur ab.

Repräsentierter Aufbau

Ein Baum ist entweder leer oder besteht aus einem einzelnen Knoten mit Unterbäumen. Die Unterbäume können selbst wiederrum leer oder ein Knoten mit Unterbäumen sein.

Ein Knoten gilt als Blatt, wenn er keine Unterbäume hat.

Ein Knoten ist immer Wurzel seines eigenen (Unter-)Baumes.

Implementierung

Ein Baum kann sowohl objektorientiert als Datenstruktur aufgebaut werden, als auch durch ein Array repräsentiert werden.