Binäre Heap Trees sind vom Aufbau her nahezu identisch zu Suchbäumen, allerdings sind die Elemente inhaltlich anders angeordnet. Die Bedingung lautet, dass der Wert jedes Knotens kleiner gleich aller Werte aller Knoten der Unterbäume sein muss.
Die Anwendungen für einen so aufgebauten Baum sind anders als für einen Suchbaum: Zunächst einmal ist das Finden des kleinsten Elementes in konstanter Zeit zu erreichen, da es an der Spitze des Baumes steht. Außerdem können zwei Heap Trees recht schnell zusammengefügt werden, dies ist bei Suchbäumen eher kompliziert.
Da Heap Trees in einem anderen Vortrag genauer behandelt werden, soll dies zu diesem Thema genügen.
Auch die sogenannten Rose Trees sollen nur kurz angesprochen werden. Im Gegensatz zu den bisher vorgestellten Bäumen, sind sie allgemeiner definiert und besitzen mehr Verzweigungen als zwei, es sind also keine binären Bäume (zumindest nicht im Regelfall).
In Haskell werden sie auf folgende Weise definiert:
data Rose a = Node a [Rose a]
Externe Knoten (Blätter) werden durch eine leere Liste der Unterbäume charakterisiert. Da es in Haskell problemlos möglich ist, unendliche Listen zu erzeugen (siehe Ausarbeitung über Listen), lassen sich auch unendliche Bäume erzeugen.
r1 = Node 1 [ Node n [] | n <- [1..]]
Es gelten die gleichen Einschränkungen wie bei unendlichen Listen. Sie lassen sich problemlos definieren, allerdings dürfen nur stets Teile davon verarbeitet werden.