Die levelOrder-Funktion kann mithilfe einer Warteschlange implementiert werden. Eine Warteschlange ist eine Datenstruktur, in der Elemente in der Reihenfolge hinzugefügt und entfernt werden, in der sie hinzugefügt wurden (FIFO - First In, First Out).
Die Idee hinter der Verwendung einer Warteschlange bei der levelOrder-Traversierung ist, dass Sie zuerst die Wurzel hinzufügen und dann die Kinder jedes Knotens in der Reihenfolge hinzufügen, in der sie betrachtet werden sollen (links zuerst, dann rechts). Wenn Sie einen Knoten aus der Warteschlange entfernen, fügen Sie seine Kinder hinzu und speichern Sie den Wert des Knotens in einer Ergebnisliste.
Hier ist eine mögliche Implementation:
levelOrder :: BTree a -> [a]
levelOrder Nil = []
levelOrder (Node x lt rt) = levelOrder' [Node x lt rt]
where
levelOrder' [] = []
levelOrder' q = x:(levelOrder' (q' ++ children))
where
Node x lt rt = head q
q' = tail q
children = [lt, rt]
In dieser Implementation habe ich eine Helferfunktion namens levelOrder' erstellt, die als Argument eine Warteschlange entgegennimmt, die in diesem Fall die Wurzel des Baums ist. Die Helferfunktion verwendet eine Schleife, um die Knoten in der Warteschlange zu betrachten, bis die Warteschlange leer ist. Innerhalb der Schleife entferne ich den Kopf der Warteschlange und speichere seinen Wert in der Ergebnisliste. Ich füge dann die Kinder des Knotens der Warteschlange hinzu, damit sie in der nächsten Runde betrachtet werden können.
Es ist wichtig darauf hinzuweisen, dass die Warteschlange hier durch eine Liste implementiert wird, die nicht zwingend die beste Wahl für diese Aufgabe ist, da es spezielle Datenstrukturen für Queue existieren und die Implementierung kann je nach Programmiersprache variieren.
