www.jammni.de

Gepostet:
22.06.2010 11:50

Prüfen ob Baum aufsteigend sortiert ist

wieder einmal eine Baumgeschichte.

die Baumdefinition: data NumTree a = Node Integer a (NumTree a) (NumTree a) (NumTree a) | Nil

Jetzt soll eine funktion "aufsteigend" implementiert werden die für einen konkreten Baum genau dann wahr ist wenn die folgenden drei Bedingungen gelten:
--In allen Knoten ist der Integer-Eintrag kleiner als die Integer-Eintraege der Unterbaeume.
--Alle Integer-Eintraege des ersten Unterbaumes sind kleiner als die des zweiten.
--Alle Integer-Eintraege des zweiten Unterbaumes sind kleiner als die des dritten.

okay... angefangen habe ich mal damit mir ne funktion zuschreiben die mir einfach den integer einens trees liefert (getFstInteger).



getFstInteger :: NumTree a -> Integer
getFstInteger Nil = {--was soll ich denn hier zurückliefen--}
getFstInteger (Node i _ _ _ _) = i

hier gibt es das problem, dass ich nicht weiß was ich zurückliefern soll wenn ein Nilknoten erreicht wird :/


valueLessThanSubtrees (Node i _ t1 t2 t3)
	| (i < getFstInteger t1) = valueLessThanSubtrees t1
	| (i < getFstInteger t2 ) = valueLessThanSubtrees t2
	| (i < getFstInteger t3 ) = valueLessThanSubtrees t3
	| otherwise = False
valueLessThanSubtrees (Nil) = True

Diese Methode versucht mal die erste regel abzudecken und verwendet die getFstInteger Methode von oben.
Jedoch funktioniert das ganze nicht so richtig wegen den Nilknoten

Zum Seitenanfang

Siracusa

Gepostet:
22.06.2010 17:30

> was soll ich denn hier zurückliefen

Gute Frage. ^^ Allgemein kann man diese Funktion nicht implementieren, normalerweise müsste da undefined zurückgegeben werden. Bei Int könnte man etwas tricksen und minBound zurückgeben, also die kleinstmögliche Int-Zahl. Das funktioniert bei Integer aber nicht. Also entweder überlegst du dir einen anderen Ansatz, oder du änderst den Rückgabetyp der Funktion, bspw. in Maybe Integer.

Geschickter wäre es aber vermutlich, erstmal alle Zahlen des Baums in eine Liste zu schreiben, und zwar in der Reihenfolge wie die Ordnung im Baum angestrebt ist (so wie ich das verstehe als Tiefensuche, d.h. immer erst einen Unterbaum bis ganz nach unten und dann zum nächsten). Dann bräuchtest du die Liste nur nochmal durchgehen und schauen, ob diese aufsteigend geordnet ist.

Viele Grüße,

Siracusa

Zum Seitenanfang

Haskell-Forum