:wave:Hir bin ich schon wieder. Muss wieder Aufgaben abgeben und verstehe fast nichts. Diesmal sind es Programmieraufgaben in Haskell. Falls jemand so nett ist und mir helfen könnte. Hab ein falsches Nebenfach gewählt.:sudern:
Betrachten Sie die in der Vorlesung besprochenen Klasse
GenBinTree a von allgemeinen
binären Bäumen mit in den Knoten gespeicherten Elementen (Label)aus einem Ordnungstyp a.
(a)
Machen Sie die Klasse zur Instanz von Eq. Dabei sollen zwei Bäume
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) Ein Baum aus dieser Klasse heißt Suchbaum für die gespeicherten Objekte vom Typ a, falls für jedes Knotenlabel gilt, dass alle Label im linken Teilbaum unter dem Knoten kleiner gleich diesem Label sind, alle im rechten Teilbaum größer gleich. Zeichnen Sie 4 verschiedene Suchbäume für 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 auffallen. Formulieren und beweisen Sie diesen Fakt für beliebige Suchbäume. Definieren 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.
