markierte Binärbaum < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | Gegeben ist der Haskell-Datentyp
data Bt = E | K Int Bt Bt
zur Definition markierter Binärbäume. Definieren Sie eine Funktion count :: Bt -> (Int, Int),
wobei count(b) = (x, y) die Summe x der Markierungen sowie die Anzahl y der Blätter im Binärbaum
b berechnet. |
Wie kann ich testen, ob der Punkt dem ich gerade bin ein Blatt ist und ob dieser schon markiert ist
count :: Bt -> (Int, Int)
count E =(0,0)
count (K b _ _) |knoten blatt? (_,bl+1)
|ist markierung?(ma+1,_)
where
bl count b
ma count b
ist das überhaubt die richtige Herangehensweise?
Gruß und Dank für Tipps
|
|
| |
|
Hallo,
so wie ich das verstehe hat ein Blatt die Unterbäume E E, falls E tatsächlich für Empty steht. Also weißt du, dass jedes (K i E E) ein Blatt ist.
Alle Knoten des Baums sind markiert, da musst du nichts unterscheiden. Du musst nur ihre Werte aufaddieren.
Das gleichzeitige Zählen und Summieren birgt eine kleine Schwierigkeit, aber die kann man mit einer geeigneten where-Klausel umgehen.
Ich würde Folgendes vorschlagen:
count :: Bt -> (Int, Int)
count E = (0,0)
count (K i E E) = (i,1)
count (K i l r) = (i + lM + rM, lB + rB) where
(lM, lB) = count l
(rM, rB) = count r
Gruß
Martin
|
|
|
| |
|
count (K i l r) = (i + lM + rM, lB + rB)
(lB + rB)<-- meine Frage ist hier, du addierst hier blätter, woher weißt du das es blätter sind und nicht weitere Knoten?
Gruß niesel
|
|
|
| |
|
Hallo,
ich addiere die Funktionswerte, die in der where-Klausel rekursiv berechnet werden. Beim Absteigen in die Unterbäume addiere ich sonst nichts dazu.
Ich addiere an dieser Stelle also nur die Anzahl der Blätter im linken Teilbaum und die Anzahl der Blätter im rechten Teilbaum. Durch den rekursiven Aufruf steigen wir immer weiter hinab (zählen dabei nichts mit) und landen irgendwann bei dem Konstruktor "K i E E", welcher in der Zeile "count (K i E E) = (i,1)" behandelt wird. Erst hier sind wir bei einem Blatt (einer Verzweigung mit leeren Teilbäumen E) angelangt und sagen, dass wir 1 Blatt gezählt haben. Durch die Rekursion wird dann jede 1 sozusagen durch die einzelnen Aufrufe hochpropagiert bis zur Wurzel des Baums.
Na ja, Haskell ist eine wunderschöne Sprache, aber manchmal...
Am besten ist, du zeichnest dir ein kleines Bäumchen dieser Art und versuchst die einzelnen Funktionsaufrufe mit ihrem Rückgabewerten nachzuvollziehen.
Gruß
Martin
|
|
|
|
