engl.: binary tree

Binärbäume sind

• entweder leer oder
• bestehen aus einem markierten Knoten mit zwei Unterbäumen.

Ein Blatt ist dann ein Knoten mit zwei leeren Unterbäumen.

Ein Binärbaum heißt strikt, wenn jeder Knoten ein Blatt ist oder zwei nicht-leere Unterbäume besitzt.

Ein Binärbaum der Höhe h heißt vollständig, wenn er strikt ist und alle Blätter die Tiefe h − 1 haben.

• Man spricht auch von einem Binärbaum, wenn jeder Knoten maximal zwei Kinder hat.