Ein
BinaryTree,
zu deutsch Binärbaum,
ist eine baumartige Datenstruktur, welche rekursiv definiert ist:
- Ein einzelner Knoten ist ein Binärbaum.
- Ein Knoten mit maximal zwei Teilbäumen ist ein Binärbaum.
Dabei wird ein terminaler Knoten, also ein Knoten ohne Teilbäume, oft als Blatt
(Blattknoten)
bezeichnet.
Der Knoten, der
nicht
Teil eines anderen, übergeordneten Knotens ist, wird als Wurzel
(Wurzelknoten)
bezeichnet.
Im Großen und Ganzen unterscheidet sich ein Binärbaum nur in einem Punkt vom allgemeinen
Baum:
kein einziger Knoten des Binärbaumes kann mehr als zwei Kindknoten haben.