www.jammni.de

Gepostet:
20.01.2011 18:46

Hilfe :)

Hallo, grüß euch, ich brauch hilfe mit der folgenden Fragen. Danke .
Betrachten Sie die in der Vorlesung besprochenen Klasse GenBinTree a von allgemeinen
binaren Baumen mit in den Knoten gespeicherten Elementen (Label) aus einem
Ordnungstyp a.
(a) (3 Punkte) Machen Sie die Klasse zur Instanz von Eq. Dabei sollen zwei Baume
t1,t2 als gleich gelten, wenn sie nach einer Reihe von Flipoperationen identisch
sind. Flipoperation bezeichnet hier das Vertauschen eines linken mit dem rechten
Unterbaum eines Knotens.
(b) (5 Punkte) Ein Baum aus dieser Klasse heißt Suchbaum fur die gespeicherten Objekte
vom Typ a, falls fur jedes Knotenlabel gilt, dass alle Label im linken Teilbaum
unter dem Knoten kleiner gleich diesem Label sind, alle im rechten Teilbaum großer
gleich. Zeichnen Sie 4 verschiedene Suchbaume fur die Labelmenge {12; 3; 7; 8; 1; 5} von ganzen Zahlen und geben Sie jeweils das Ergebnis des Preorder-Durchlaufs
und des Inorder-Durchlaufs an. Bei den Inorder{Ergebnissen sollte Ihnen etwas
aufallen. Formulieren und beweisen Sie diesen Fakt fur beliebige Suchbaume. De-
nieren Sie eine Funktion isSearchTree, die entscheidet, ob ein Baum Suchbaum
ist und eine Funktion find, die entscheidet, ob ein Anfrage-Label in einem Suchbaum
vorkommt.

Zum Seitenanfang

Landei

Gepostet:
21.01.2011 10:20

Es wäre schön, wenn du ein wenig Code bringen würdest...

(a)


data Tree a = Empty | Node (Tree a) a (Tree a)

instance Eq a => Eq (Tree a) where 
   Empty == Empty = True
   (Node left1 v1 right1) == (Node left2 v2 right2) = 
      v1 == v2 &&   
      ((right1 == right2 && left1 == left2) || 
      (right1 == left2 && left1 == right2))    -- das wäre der "flip"

Zum Seitenanfang

Siracusa

Gepostet:
21.01.2011 17:29

Hallo,

@Landei: Ich bitte dich keine fertigen Lösungen zu posten, sondern nur Hilfestellungen zu geben.

@jarsofclay:
Zu b) Für die find-Funktion kannst du die Eigenschaft des Suchbaums nutzen, dass im linken Unterbaum die kleineren und im rechten die größeren Werte stehen. find x t schaut sich dann im Baum t bei einer Verzweigung die Zahl an, die an dieser Verzweigung steht (= y) und sucht entsprechend im linken Unterbaum weiter wenn x<=y und im rechten wenn x>=y. Bei einem Blatt wird dann x schlicht mit dem Wert am Blatt verglichen.

Für isSearchTree wäre es hilfreich zunächst eine Funktion zu schreiben, die alle im Baum gespeicherten Werte ermittelt. Beim rekursiven Durchgehen durch einen Baum mit isSearchTree wird diese Funktion dann benutzt um alle Werte im linken xs und alle Werte im rechten ys Unterbaum zu ermitteln. Wenn dann für einen Baum gilt, dass alle Zahlen in xs kleiner gleich dem Wert am obersten Knoten sind, alle Zahlen in ys größer gleich dem Wert am Knoten ist und auch beide Unterbäume Suchbäume sind, dann handelt es sich um einen Suchbaum.

Ansonsten bitte Code posten, an welchen Stellen du nicht weiterkommst.

Viele Grüße,

Siracusa

Zum Seitenanfang

Haskell-Forum