Haskell - Binärbaum < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | Gegeben ist der HASKELL-Typ eines BinÄarbaumes data
BT = E | T Int BT BT. Dabei beszeichnet der
Konstruktor E einen leeren Baum und T i l r einen Baum, dessen Wurzel mit einer ganzen Zahl i markiert ist
und der den linken Unterbaum l und den rechten Unterbaum r hat.
1. eine HASKELL-Funktion prelin::BT->[Int], die alle Markierungen eines Binärbaumes in der Lineari-
sierung prälin (präorder) als Liste anordnet,
2. eine HASKELL-Funktion postlin::BT->[Int], die alle Markierungen eines Binärbaumes in der Lineari-
sierung postlin (preorder) als Liste anordnet,
3. eine HASKELL-Funktion bslin::BT->[Int], die alle Markierungen eines Binärbaumes in der Linearisie-
rung entsprechend der Breitensuche als Liste anordnet |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Hallo...
Ich wollte mal fragen wie man die Breitensuche (Aufgabe 3) implementieren kann?
1. und 2. hab ich schon aber bei 3. steh ich auf den Schlauch.
Ich weiss, das die Breitensuche bei der Wurzel beginnt zu zählen, also:
data BT = E | T Int BT BT
bslin::BT->[Int]
bslin E = []
bslin (T i l r) = [i] ++ ?? (ab dieser Stelle weiss ich nicht mehr weiter!)
Wie kann man sagen, das er jetzt die nächste Stufe des Baumes abzählen soll?
Hab schon viel ausprobiert und alles war falsch, bin am verzweifeln. Vielleicht hab ich auch einen Denkfehler, keine Ahnung.
Kann mir jemand helfen???
|
|
| |
|
Hallo und ![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]") ,
ich fürchte, mit diesem Ansatz kommst du nicht weit.
Hier brauchst du einen FIFO, in den du die Unterbäume des aktuell bearbeiteten Baums reinsteckst, damit die Reihenfolge erhalten bleibt.
Dazu würde ich eine Hilfsfunktion bsl anlegen und den Aufruf von bslin so gestalten:
bslin baum = bsl [baum]
Bei einem leeren FIFO (der auch nur eine Liste ist...) hört die Rekursion auf, leere Bäume im FIFO werden übergangen und "richtige" Bäume werden ihrer Zahl beraubt und ihre Unterbäume an den FIFO drangehängt, der rekursiv bearbeitet wird.
Gruß
Martin
|
|
|
| |
|
Okay, ich möchte nur sagen, das ich mit Haskell erst 2 Wochen arbeite und mich noch nicht so auskenne damit.
Was ist FIFO?
Eine Hilfsfkt, die man erst implementiert?
Sorry, steh heute ziemlich neben mir, kann dir aber wirklich nicht ganz folgen, aber danke für die Antwort.
|
|
|
| |
|
Hallo,
> Was ist FIFO?
> Eine Hilfsfkt, die man erst implementiert?
Nein, ein FIFO, auch Warteschlange oder Queue genannt, ist eine grundlegende Datenstruktur in der Informatik. Sie basiert auf dem "First In - First Out"-Prinzip, also wie bei einer echten Warteschlange: Das Element, das sich zuerst einreiht, wird zuerst verarbeitet.
In Haskell heißt das nur, dass immer ein Element vom Anfang der Liste verarbeitet wird, während neue Elemente hinten an die Liste angehängt werden und demzufolge auch zuletzt verarbeitet werden.
Bei der Breitensuche bewirkt man damit, dass die besuchten Teilbäume zuerst innerhalb einer Ebene abgearbeitet werden, während ihre Teilbäume hinten angestellt werden. Das Ganze wiederholt sich, bis der FIFO leer ist, weil nichts mehr reingesteckt wurde (leere Teilbäume).
Gruß
Martin
|
|
|
|
