0 Daumen
370 Aufrufe

Hallo!

Ich versuche, preOrder (Zuerst wird die Wurzel betrachtet, dann rekursiv der linke und dann der rechte Teilbaum) und levelOrder (Die Knoten werden in aufsteigender Tiefe von links nach rechts betrachtet) zu implementieren.

Ich habe:

data BTree a = Nil | Node a (BTree a) (BTree a) deriving Show

preOrder :: BTree a -> [a]
preOrder Nil = []
preOrder (Node x lt rt) = x: ((preOrder lt) ++ (preOrder rt ))


es scheint zu funktionieren, aber ich mühe mich mit der levelOrder-Funktion, ich habe gerade:

levelOrder :: BTree a -> [a]
levelOrder Nil = []
levelOrder (Node x lt rt) =


Ich weiß nicht, was ich als nächstes tun soll, damit es funktioniert.

Avatar von

1 Antwort

0 Daumen

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.




Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community