www.jammni.de

Gepostet:
01.12.2007 12:29

erzeugen eines Binärbaums

Hallo ihrs, ich hab ein Problem bei einer Aufgabe. Weis nämlich nicht was ganau ich machen soll. Vielleicht kann ja einer von euch mir helfen. Die Aufgabe lautet folgendermaßen:

Beschreiben Sie die HASKELL-Funktion erzeuge::Int->BT, wobei als Resultat von erzeuge n ein Binärbaum
mit n Knoten erzeugt wird, der wie bei einem heap gleichmässig gefüllt ist und dessen Knoten mit der
Nummer entsprechend der Breitensuche markiert sind. Die Wurzel soll die Markierung 1 erhalten.

Das heißt, es soll folgendes ausgeben:
Standard-Testfall
erzeuge 5 == T 1 (T 2 (T 4 E E) (T 5 E E)) (T 3 E E)

data BT = E | T Int BT BT deriving(Show)
erzeuge::Int->BT

Weiß einer wie das Funktionieren könnte.

Zum Seitenanfang

ICQ

Siracusa

Gepostet:
01.12.2007 21:31

Hallo Franzi,

deine drei Aufgaben kommen mir aber verdächtig bekannt vor! ;-)

Die Funktion soll einen Binärbaum erzeugen, wobei alle natürlichen Zahlen von 1 bis n als Knotenmarkierungen im Baum vorkommen. Ein Binärbaum kann in deinem Fall entweder leer sein, also E, oder ein Knoten mit einer Markierung k, einem linken Unterbaum tl und einem rechten Unterbaum tr sein, also T k tl tr. Die Aufgabe der Funktion ist nun einen Baum so zu konstruieren, daß zunächst ein Startknoten mit der Markierung 1 angelegt wird. Je nachdem wie groß n ist, werden nach und nach neue Unterbäume (Unterknoten) angehängt, und zwar immer von links nach rechts. Dabei steigen die Zahlen bei jedem weiteren Knoten um Eins an. Sind auf einer Tiefenstufe keine freien Plätze (also leere Bäume) für Unterknoten mehr vorhanden, wird wieder ganz links in der nächsten Tiefe begonnen. Dieser sog. Heap sieht dann als Baum für n = 6 bspw. so aus:

           T 1
         /     \
       /         \
     T 2         T 3
    /   \       /   \
  T 4   T 5   T 6    E
  / \   / \   / \
 E   E E   E E   E

Ein Lösungsvorschlag: Bei dem speziellen Binärbaum sollte dir aufgefallen sein, daß, wenn ein Knoten mit der Zahl i markiert ist, der Startknoten im linken Unterbaum dann mit 2*i und im rechten Unterbaum mit 2*i+1 markiert ist, sofern diese Werte nicht größer als die Zahl n beim Funktionsaufruf erzeuge n sind. Die erzeuge-Funktion läßt sich so also relativ einfach mit einer Hilfsfunktion erzeuge' implementieren, die als erstes Argument die Zahl n vom Aufruf erzeuge n erhält (also die größte Zahl im Binärbaum), und als zweites Argument eine Zahl i, die die aktuelle Knotenmarkierung darstellt. Diese Funktion erzeugt dann einen Baum, dessen Startknoten mit i markiert ist. Der linke Unterbaum soll ein Baum sein, dessen Startknoten mit 2*i markiert ist, der rechte Unterbaum ein Baum, dessen Startknoten mit 2*i+1 markiert ist. Die Unterbäume lassen sich also durch den rekursiven Aufruf von erzeuge' erzeugen. Fehlt nur noch ein Rekursionsende. Dies soll der leere Baum E sein, der immer dann zurückgegeben wird, wenn i>n ist. erzeuge n ruft dann nur erzeuge' mit n und der Markierung des Startknotens des Binärbaums, nämlich 1, auf.

Zum Seitenanfang

Haskell-Forum