www.jammni.de

Gepostet:
24.02.2010 23:29

einfache Baumoperationen

Hallo,

Ich übe mich gerade in Haskell und versuche einen binären Baum aufzubauen und zunächst einfache Operationen darauf durchzuführen:

meinBaum sieht folgendermaßen aus:

data BTree a = Leaf a | Fork (BTree a) (BTree a)

nun als erstes habe ich das simpelste probiert, nämlich die Blattknoten zu zählen:

size :: BTree a -> Int
size (Leaf x) = 1
size (Fork xt yt) = size xt + size yt

funktioniert wunderbar :-)

auch die summe der Blattknoteninhalte habe ich:
summe :: BTree Int -> Int
summe (Leaf i) = i
summe (Fork xt yt) = summe xt + summe yt

meine nächstes würde ich gerne den größten blattknoten ermitteln hier stehe ich ein bisschen an:
getGreatest :: BTree Int -> Int

--als erstes behandle ich wieder wie schon vorher den fall wo man nur einen Blattknoten bekommt

getGreatest (Leaf i) = i

--Beim Fall, wo ich eine Verzweigung bekomme weiß ich allerdings nicht wie ich denn an die Werte von xt und yt überhaupt ran komme
--habe mir es so überlegt:

getGreatest (Fork xt yt)
| getGreatest xt > getGreatest yt = --und hier weiß ich nicht wie ich dann fortfahren soll.....?

wie komm ich an die konkreten werte ran die ich dann vergleichen kann? und muss ich mir hier vielleicht auch einen "Hilfsparameter" schreiben der mir den aktuell größten knoten zwischenspeichert?

lg c

Zum Seitenanfang

Siracusa

Gepostet:
25.02.2010 21:35

Hallo,

da du den Wert zweimal benutzt, einmal beim Vergleichen und einmal beim Zurückgeben, musst du ihn in einer Hilfsvariablen speichern (oder die Funktion zweimal ausführen, was allerdings ziemlich ineffizient ist):

getGreatest (Fork xt yt) =
  | greatestX > greatestY = greatestX
    where
        greatestX = getGreatest xt
        greatestY = getGreatest yt

Alternativ kannst du auch die Funktion max verwenden, damit ergibt sich als rechte Seite dann ... = max (getGreatest xt) (getGreatest yt) und die Hilfsvariablen werden nicht mehr gebraucht.

Viele Grüße,

Siracusa

Zum Seitenanfang

XeZZ

Gepostet:
26.03.2010 16:11

Ich hab ne Frage zu der Baumdeinition. ich hab die die du da verwendest schonmal gesehen und versteht leider nciht ganz wie die funktioniert. Ich hab außerdem eine ähnliche gesehen die so aussieht

data Tree a
        = Leafe a
        |Branch (Tree a) a (Tree a)

So nun meine Frage. Du hast nur 2 Teilbäume und an den Teilbäumen können Blätter hängen. Aber wie werden die inneren Knoten dargestellt? Oder ist die andere Definition nur so eine Eta-Reduktionsgeschichte wo das a was bei mir in der Mitte der Teilbäume steht so zu sagen am Ende steht?

Zum Seitenanfang

ICQ

Siracusa

Gepostet:
26.03.2010 21:35

Hallo,

also die Baumdefinition oben erlaubt nur das Speichern von Werten an Blättern, da gibt es keine inneren Knoten mit Werten, wohingegen bei deinem Baum in jedem Knoten ein Wert gespeichert wird. Eta-Reduktionen gibt es nur bei Funktionsanwendungen, nicht in der Definition von Datentypen.

Viele Grüße,

Siracusa

Zum Seitenanfang

Haskell-Forum