www.jammni.de

Logo - Kleiner Drache
Login
Username:

Passwort:

Daten merken
Auto-Login
Registrieren
 
Online
niemand
 
Forumsuche
Suche nach:

Logo - DracheHaskell-Forum

franzigoth1

Gepostet:
06.12.2007 16:02

Baum in Liste umwandeln  
Hallo erstmal,

Ich wollte fragen wie man einen binären baum in eine Liste umwandeln kann, so das folgendes rauskommt:

eingabe: tr= T E (T (T E E) (T E E))

ausgabe: addr tr == ["eps","1","10","11"]

T ist ein Knoten der nicht leer ist, deshalb soll er 1 ausgeben und wenn der baum keinen Knoten hat E, dann soll er eine 0 ausgeben. eps steht für die Wurzel

Wie man einen Baum aus einer Liste erstellt weis ich, aber nicht wie man aus einen Baum eine Liste macht.

Hat einer eine Idee????
Zum Seitenanfang ICQ    
 
Siracusa

Gepostet:
06.12.2007 21:56

   
Hallo,

wenn ein Knoten einen leeren Unterbaum E hat wird keine weitere Adresse an die Liste angehängt, sondern "" zurückgegeben. Wenn es sich um einen Unterbaum T handelt, wird je nach der Position links bzw. rechts eine 0 bzw. eine 1 an die rekursiv berechnete Adresse des Unterbaums davor angefügt und diese Adresse an die Liste angehängt. Dann muß nur noch die Wurzel gesondert behandelt werden.


Viele Grüße,

Siracusa
Zum Seitenanfang    
 
franzigoth1

Gepostet:
25.12.2007 14:12

Lösungsansatz  
Hi....
hab mich damit mal beschäftigt und folgenden Ansatz implementiert:

data BT = E | T BT BT deriving(Show)
addr::BT->[[Char]]

addr E = []
addr (T E E) = ["eps"]
addr (T l r) = ["eps"] ++ f1

f1 (T E E) = ["0"]
f1 (T l r) = ["0" ++ f1 ]

flk E = []
flk (T E E) = ["0"]
flk (T l E) = ["0"] ++ ["00" ++ fl ]
flk (T E r) = ["0"] ++ ["01" ++ fr ]
flk (T l r) = ["0"] ++ ["00" ++ fl ] ++ ["01" ++ fr ]
frk E = []
frk (T E E) = ["1"]
frk (T l E) = ["1"] ++ ["11" ++ fl ]
frk (T E r) = ["1"] ++ ["11" ++ fr ] ++ ["10" ++ fr ]
frk (T l r) = ["1"] ++ ["11" ++ fr ] ++ ["10" ++ fl ]

fl E = []
fl (T l r) = "0" ++ fl ++ fr
fr E = []
fr (T l r) = "1" ++ fl ++ fr

Ich weiß nicht ob das so geht, aber Haskell sagt ständig:

ERROR file:.\P2.1.hs:10 - Type error in application
*** Expression : "0" ++ f1
*** Term : f1
*** Type : BT -> [[Char]]
*** Does not match : [a]

Ich weiß nicht, was genau ich falsch mache oder was ich ändern muss, hab so einiges ausprobiert, aber ich denke das mein Ansatz eigentlich richtig ist. Oder????
Zum Seitenanfang ICQ    
 
franzigoth1

Gepostet:
25.12.2007 20:20

Lösungsansatzt Zweiter Versuch  
data BT = E | T BT BT deriving(Show)
addr::BT->[[Char]]

addr E = []
addr (T E E) = ["eps"]
addr (T l r) = ["eps"] ++ flk ++ frk

flk E = []
flk (T E E) = ["0"]
flk (T l E) = ["0"] ++ ["00"] ++ fl
flk (T E r) = ["0"] ++ ["01"] ++ fr
flk (T l r) = ["0"] ++ ["00"] ++ fl ++ ["01"] ++ fr
frk E = []
frk (T E E) = ["1"]
frk (T l E) = ["1"] ++ ["10"] ++ fl
frk (T E r) = ["1"] ++ ["10"] ++ fr ++ ["11"] ++ fr
frk (T l r) = ["1"] ++ ["10"] ++ fr ++ ["11"] ++ fl

fl E = []
fl (T l r) = ["0"] ++ fl ++ fr -->Fehler (Zeile 27)
fr E = []
fr (T l r) = ["1"] ++ fl ++ fr

Hab es geschafft ersten Fehler zu beseitigen aber jetzt ist ein neuer Aufgetren:

ERROR file:.\P2.1.hs:27 - Type error in application
*** Expression : fl ++ fr
*** Term : fl
*** Type : BT ->
*** Does not match : [a]

Hab keine Ahnung, was ich falsch mache, hat einer von euch eine Idee
Zum Seitenanfang ICQ    
 
Siracusa

Gepostet:
27.12.2007 16:00

   
Hallo,

er beschwert sich, daß du versuchst eine Liste mit einer Funktion zu verknüpfen. fl ist der Name einer Funktion, die noch ein Argument erwartet. Du muß die ganzen f-Funktionen jeweils mit dem Restbaum der linken Seite aufrufen, also E, l oder r.


Viele Grüße,

Siracusa
Zum Seitenanfang    
 
franzigoth1

Gepostet:
28.12.2007 12:43

Ach so...  
Ach so, kein Wunder, danke, hoffentlich wird es jetzt funktionieren
Zum Seitenanfang ICQ    
 
Mireille

Gepostet:
29.12.2007 14:08

bei mir klappts nicht  
hallo ihr

also ich hab mich auch an diesem programm versucht aber bei mir will es partout nicht laufen -.- ich habe schon stunden damit verbracht irgendwas zu löschen, hinzuzufügen, zu verändern,... aber alles bringt nix. hatte es einmal geschafft, dass der standarttestfall ausgegeben wird aber alle anderen bäume hatten nicht funktioniert. Leider hab ich durch vieles rumprobieren meinen quelltext wieder so verändert, dass er jetzt nicht mal mehr das machet -.-
bitte helft mir. Ehrlich gesagt verliere ich langsam den überblick über das programm...

data BT = E | T BT BT deriving(Show)
addr::BT->[[Char]]

addr E = []
addr (T E E) = ["eps"]
--addr (T E r) = ["eps"] ++ links l ++ links r
--addr (T l E) = ["eps"] ++ links l ++ links r
addr (T l r) = ["eps"] ++ links l ++ links r ++ rechts l ++ rechts r

links E = []
links (T E E) = ["0"]
links (T l E) = ["0"] ++ ["00"] ++ links l
links (T E r) = ["0"] ++ ["01"] ++ links r
links (T l r) = ["0"] ++ ["01"] ++ links l ++ links r ++ rechts l ++ rechts r

rechts E = []
rechts (T E E) = ["1"]
rechts (T l E) = ["1"] ++ ["10"] ++ rechts l
rechts (T E r) = ["0"] ++ ["10"] ++ rechts r
rechts (T l r) = ["1"] ++ ["10"] ++ links l ++ links r ++ rechts l ++ rechts r
Zum Seitenanfang    
 
Siracusa

Gepostet:
29.12.2007 15:57

   
Hallo,

also eure Quelltexte sehen sich aber erstaunlich ähnlich. ;-)

Das Problem bei euch ist, daß ihr vor die Unterbäume keine 0 oder 1 davorhängt. Für die oberen Knoten gebt ihr die Adressen explizit an, die unteren konstruiert ihr aber nicht, sondern verwendet wieder nur die oberen. Besser wäre etwa folgendes Vorgehen (als Beispiel):

links E = []
links (T l r) = setzeDavor "0" (links l ++ rechts r)

setzeDavor :: String -> [String]
setzeDavor = ...


setzeDavor fügt dann vor alle Strings aus der Liste den einen String davor an. Denn alle Adressen aus den Unterbäumen bekommen ja eine 0 davorgesetzt und sind dann die neuen Adressen für den linken Knoten. Das gleiche macht ihr bei den rechten Knoten mit der 1 davor. Dann müßt ihr auch nicht so viele Fallunterscheidungen machen.


Viele Grüße,

Siracusa
Zum Seitenanfang    
 
franzigoth1

Gepostet:
03.01.2008 17:11

hab da mal ne Frage...  
Hallo...

Hab das mal mit der Hifsfunktion setzeDavor ausprobiert... nur sagt haskell ständig, das er setzeDavor "0" mit (links l ++ rechts r) nicht verbinden kann.

Fehlt dazwischen etwas (bei dem Beispiel): links (T l r) = setzeDavor "0" (links l ++ rechts r), oder mach ich da irgendwas falsch????


Auch bei der Implementierung von setzteDavor tu ich mich schwer:

setzeDavor :: String -> [String]
setzeDavor ("genau hier muss doch auch was hin, oder?") = ...
Zum Seitenanfang ICQ    
 
Siracusa

Gepostet:
03.01.2008 20:40

   
Huch, da hab ich mich in der Eile etwas vertan! Der Typ für die Funktion stimmt noch nicht ganz, es fehlt noch der Resultattyp. Und ja, da müssen noch die Variablen für die Musteranpassung hin.
setzeDavor :: String -> [String] -> [String]
setzeDavor s lst = ...

s ist der String der davorgesetzt werden soll, lst die Liste mit den Adressen.


Viele Grüße,

Siracusa
Zum Seitenanfang