Labb 3: Binära träd
- Inlämningsdatum 15 sep 2023 av 18:00
- Poäng 10
- Lämnar in en filuppladdning
- Filtyper py
Mål | Läs i kursboken |
implementation av binärt sökträd, rekursion, abstraktion |
Kapitel 7.2, 7.3, 7.5, 7.7, 7.13, 7.14 Links to an external site. |
Laborationens tema är binära sökträd.
- Första uppgiften är att skriva en klass för binära sökträd.
- Andra uppgiften är att bygga upp ett sökträd från en fil med svenska ord. Alla dubbletter ska skrivas ut.
- Tredje uppgiften är att kolla orden i en engelsk text mot det svenska sökträdet. Finns det några skenbart svenska ord ska dom skrivas ut, men bara den första förekomsten av varje svenskt ord. (För att veta vilka ord man redan hittat sparar man förstås dom i ett sökträd.)
□ Experimentera med binärträd
Gå in på Liangs binärträdsanimation Links to an external site. och gör följande:
- Skapa ett balanserat binärträd med sju noder
- Skriv ut trädet i inorder
- Skriv ut trädet i preorder
- Skriv ut trädet i postorder
□ Första uppgiften: Skriv en klass för binära sökträd
Nu ska du implementera ett binärt sökträd som en klass.
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 "gurka" in svenska: # Kolla om "gurka" finns i trädet
- - - # (Operatorn in anropar metoden __contains__ Links to an external site.
# som du ska implementera i din Bintree-klass) svenska.write() # Skriver alla trädobjektets ord i bokstavsordning
Skapa först en fil bintreeFile.py Här ska klassen Node, klassen Bintree och tre extra funktioner in.
Klassen Node
Trädet behöver noder! Börja med att definiera en klass Node i bintreefilen som innehåller tre attribut; ett värde och pekarna left och right (dom behöver inte vara privata). Den enda metod som behövs i Node-klassen är __init__.
Klassen Bintree
Fortsätt i samma fil med klassen Bintree. Klassen Bintree ska ha tre metoder:
- put(x) som sorterar in x i trädet
- __contains__(x) som kollar om x finns i trädet
- write() som skriver ut trädet i inorder
Så här ska klassens metoder se ut:
class Bintree: def __init__(self): self.root = None def put(self,newvalue):
# Sorterar in newvalue i trädet
self.root = putta(self.root,newvalue) def __contains__(self,value):
# True om value finns i trädet, False annars return finns(self.root,value) def write(self):
# Skriver ut trädet i inorder skriv(self.root) print("\n")
Tre extra funktioner
Men i filen bintreeFile.py ska du dessutom definiera tre hjälpfunktioner putta, finns och skriv. När trädobjektets put("gurka") anropas skickar trädet sin rotpekare och det nya ordet till funktionen putta som ser till att en ny nod skapas på rätt ställe. Analogt gör de övriga anropen.
def putta(p, newvalue):
# Funktion som gör själva jobbet att stoppa in en ny nod
def finns(p,value):
# Funktion som gör själva jobbet att söka efter ett värde
def skriv(p):
# Funktion som gör själva jobbet att skriva ut trädet
Tips: Läs om Search Tree Implementation Links to an external site. i kursboken. Föreläsningen och övningen om binära sökträd kan också ge en del tips!
Testa i Kattis
- Spara testprogrammet nedan som main.py
- Provkör!
- Logga sedan in på Kattis och skicka in både din klass bintreeFile.py och testprogrammet main.py. Problemet heter soktrad i Kattis.
from bintreeFile import Bintree
def makeTree():
tree = Bintree()
data = input().strip()
while data != "#":
tree.put(data)
data = input().strip()
return tree
def searches(tree):
findme = input().strip()
while findme != "#":
if findme in tree:
print(findme, "found")
else:
print(findme, "not found")
findme = input().strip()
def main():
tree = makeTree()
searches(tree)
main()
□ Andra uppgiften: Bygg träd och skriv ut dubbletter
Nu ska du läsa in ett ord i taget från filen word3.txt Download word3.txt och lägga in det ditt binära sökträd. Ord som förekommer flera gånger (dubbletter) ska skrivas ut istället för att läggas in i trädet.
from bintreeFile import Bintree svenska = Bintree() with open("word3.txt", "r", encoding = "utf-8") as svenskfil: for rad in svenskfil: ordet = rad.strip() # Ett trebokstavsord per rad if ordet in svenska: print(ordet, end = " ") else: svenska.put(ordet) # in i sökträdet print("\n") |
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
När du nu har ett sökträd med alla svenska trebokstavsord kan du blixtsnabbt kolla om ett givet ord finns med. Du ska nu läsa filen engelska.txt Download engelska.txt ord för ord och putta in orden i ett annat sökträd. Nu vill du inte ha dubbletterna utskrivna, så kolla först
if ordet in engelska:
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.
Har du gjort rätt kommer dom utskrivna orden att bilda ännu ett hemligt budskap!
Betyg
Denna labb kan endast ge betyg E. Du måste lämna in den och redovisa den i tid för att få göra labbarna för högre betyg nästa period.
Redovisning
Labben lämnas in indivuellt med "Lämna in uppgift"-knappen högst upp på sidan, och ska redovisas muntligt av bägge gruppmedlemmarna. Skriv gruppmedlemmarnas namn i kommentarsfältet!
Vid redovisningen ska du
- kunna rita och berätta hur binärträdet byggs upp,
- visa hur du testat din klass för binära träd,
- förklara varför det går snabbt att söka i ett binärträd,
- förklara idén bakom att ha put som anropar putta, etc