Datalogilaboration 5 - Binära träd med strängar

Inledning

Laborationens tema är binära sökträd och första uppgiften är att bygga upp ett binärt sökträd från en fil med svenska ord, spotta ut dubbletter. Sedan i andra uppgiften ska du skriva ett program som ska söka efter skenbart svenska ord i en engelsk textfil och skriva ut dom, dock endast första förekomsten av varje ord som finns i både engelska och svenska ska skrivas ut. Redan utskrivna ord sparas i ett annat sökträd, och dom båda sökträden är två olika objekt av klassen BinSearchTree.

Uppgift1: Ett sökträd med ordlista

Skriv följande kod i filen BinTree.py. Klassen BinTree är halvfärdig som du ska komplettera den till ett abstrakt binärsökträd.
	class BinTree:
    		root=None

    		def insert(self,newvalue):
        		self.root=self.put(self.root,newvalue)

    		def write(self):
        		self.skriv(self.root)
        		print
Klassen BinTree innehåller två definierade funktioner insert och write. De två funktionerna är hela och ska inte ändras men de anropar två andra funktioner put() och skriv() som däremot inte är definierade alls och din uppgift är att skriva definition för de funktioner. Båda funktioner måste vara rekursiva och har följande beskrivningar: Klassen BinTree kommer att använda sig av en klass BinaryNode. Varje instans av klassen är en post som innehåller ett ord och kan ha som max två barn, ett höger och ett vänster. BinaryNode motsvarar klassen Node som vi använde i Stack och Kö i laboration 4. Läs mer om dett på föreläsningen om binära träd. I filen lab51.py ska du slutligen skriva ditt program som använder klassen BinTree. Ditt program ska läsa in hela filen word3.txt i en instans av trädet och medan orden läggs i trädet skrivs ut de ord som är dubbletter. Om du gjort rätt kommer dom dubblettord som spottas ut att bilda ett viktigt budskap.

Uppgift2: Två binära sökträd som objekt

Skapa en ny fil BinSearchTree.py kopiera sedan klassen BinTree och klistra in i filen och döp om klassen till BinSearchTree, men gör följande förbättringar.
  1. Lägg till en funktion som ser ut som nedan:
    
        		def exists(self,value):
            		return self.finns(self.root,value)
    
    
  2. Skriv sedan rekursiva funktionen finns() som anropas i exists, funktionen får ett ord och en referens till ett binärsökträd som parameter och kontrollerar att ordet finns i trädet, funktionen returnerar True om ordet finns och False annars.
Sedan skapa en fil lab52.py och skriv den kod som göra följande först:

Om du har gjort rätt kommer dom utskrivna orden att bilda ännu ett hemligt budskap! När du mottagit det kan du försöka få underskrift av en lärare.

Genialt programmerat av ..................................... anser.............................. den .................


^ Upp till kurssidan.


Sidansvarig: <vahid@nada.kth.se>
Senast ändrad 19 november 2004
Tekniskt stöd: <webmaster@nada.kth.se>