Laboration 3 - OrdträdLaborationens tema är binära sökträd.
Skriv en klass för binära sökträdFörst måste du implementera ett binärt sökträd.Tänk dig först ett abstrakt binärt sökträd. Eftersom man med Python kan jämföra ord (bokstavsordning) så går det bra att lagra ord i sökträdet, t ex så här: svenska = Bintree() # Skapa ett trädobjekt svenska.put("gurka") # Sortera in "gurka" i trädet - - - if svenska.exists("gurka"): # Kolla om "gurka" finns i trädet - - - svenska.write() # Skriver alla ord i bokstavsordningKlassen Bintree ska alltså ha tre metoder:
bintreeFile.py ska du dessutom
definiera tre hjälpfunktioner.
När trädobjektets put("gurka") anropas skickar trädet sin
rotpekare och det nya ordet till en rekursiv funktion putta
som ser till att en ny nod skapas på rätt ställe. Analogt gör de
övriga anropen, alltså så här.
Här är klassen slut men sedan kommer definitionerna av funktionerna putta, finns och skriv .
Trädet ska bara lagra en upplaga av varje objekt som läggs
in.
Det finns förstås också en
Testa din klass
Andra uppgiften: Bygg träd och skriv ut dubbletter
Nu ska du läsa in ett ord i taget från filen word3 (ladda ner rätt version till höger) och lägga in det ditt binära sökträd. Ord som förekommer flera gånger (dubbletter) ska skrivas ut.
Om du gjort rätt kommer dom dubblettord som spottas ut att bilda ett viktigt budskap. Tredje uppgiften: Två binära sökträd med ordlistor
if engelska.exists(...) . Om ordet redan fanns gör du ingenting, men om det är nytt ska
du också kolla om det råkar finnas som svenskt ord. I så fall ska det
skrivas ut på skärmen.
Om du har gjort rätt kommer dom utskrivna orden att bilda ännu ett hemligt budskap!
RedovisningNär allt fungerar som det ska bör du ta en extra titt på koden. Är den kommenterad och begriplig?Kontrollera att du gjort alla uppgifterna ovan. Vid redovisningen ska du också
Den här labben ska redovisas tillsammans med labb 4 och 5. Frivilliga extrauppgifterSöt tös: Undersök vilka trebokstavsord som blir andra ord baklänges. Varje ordpar ska bara skrivas ut en gång och symmetriska ord inte alls.
Alpin pinal: Undersök vilka fembokstavsord som blir ett
annat ord när dom två första bokstäverna flyttas sist. Du kan använda
ordlistan word5.txt.
Genialt programmerat av ............................. anser........................ den .............. |