TILDA, ÖVNING 3 ************************************************************** Binära sökträd 1 TRÄDBYGGEN * Hur ser det binärträd ut som skapas om man puttar in talen 4 2 1 6 3 7 5 i denna ordning? Och hur ser det ut om man sätter in dom i omvänd ordning, alltså 5 7 3 6 1 4 2? Är båda träden binära sökträd? Är de balanserade? 2 POSTORDERTRÄD * Skriv ut något av träden i inordning och bygg upp ett nytt träd från denna talföljd. Skriv sedan ut dom i preordning och bygg upp nya träd från dessa talföljder. Skriv slutligen ut dom i postorder och bygg upp nya träd från dessa talföljder. 3 REKURSIV TRÄDSUMMA * Ge en rekursiv tanke för summan av alla talen i trädet och programmera den så att anropet tree.sum() ger rätt svar. 4 REKURSIVT LÖVANTAL * Ge en rekursiv tanke för antalet löv i trädet. (Ett löv är en nod utan barn.) Programmera den så att anropet leaves(root) ger rätt svar. 5 REKURSIV TRÄDHÖJD * Ge en rekursiv tanke för höjden av ett träd. (Höjden definieras konstigt nog som antalet nivåer - 1. Ett tomt träd får höjden -1.) ************************************************************** Problemträd, breddenförst, djupetförst 6 STRYKORD Ordet orkan är ett strykord eftersom man kan stryka sista bokstaven om och om igen och bara få riktiga ord. orkan - orka - ork - or - o Uppgiften är att finna det längsta strykordet i svenska språket. Ordlistan finns på fil. Rita problemträdet och jämför olika tänkbara algoritmer. 7 SJUOR TILL HUNDRA Det gäller att skriva talet 100 med enbart sjuor och dom fyra räknesätten, till exempel så här. 7 +7 /7 *7 *7 =98 Det var ett gott försök som inte nådde ända fram. För att man ska få använda / måste divisionen gå jämnt ut. Rita problemträdet och diskutera bästa algoritm för att avgöra OM problemet är lösbart. Om man dessutom vill veta hur lösningen ser ut krävs en mer komplicerad datastruktur. Beskriv den och skissa ett program. 8 LABYRINT En svartvit grafikskärm kan beskrivas som en boolesk 1000x1000-matris, där true betyder en svart bildpunkt. På skärmen finns en labyrint. Ge en algoritm som finner en väg från övre vänstra till nedre högra hörnet och som bara går till vågrätt och lodrätt liggande vita grannpunkter. ************************************************************** LÖSNING 1 TRÄDBYGGEN Insättning av 4 2 1 6 3 7 5 ger trädet 4 2 6 1 3 5 7 Binärt sökträd: ja. Balanserat: ja Insättning av 5 7 3 6 1 4 2 ger trädet 5 3 7 1 4 6 2 Binärt sökträd: ja. Balanserat: nej 2 POSTORDERTRÄD Inordning + nybygge -------------------- Båda träden ger 1 2 3 4 5 6 7 8 i inordning Nya trädet bli en tarm, ytterst obalanserat. 1 2 3 4 5 6 7 Preordning + nybygge --------------------- Första trädet i preordning ger 4 2 1 3 6 5 7 och nytt träd blir 4 2 6 1 3 5 7 (samma som ursprungsträdet) Andra trädet i preorder ger 5 3 1 2 4 7 6 och nytt träd blir 5 3 7 1 4 6 2 (samma som ursprungsträdet) Postorder + nybygge ---------------------- Första trädet i postorder ger 1 3 2 5 7 6 4 och nytt träd blir 1 3 2 5 4 7 6 Andra trädet i postorder ger 2 1 4 3 6 7 5 och nytt träd blir 2 1 4 3 6 5 7 3 REKURSIV TRÄDSUMMA Rekursiv tanke: Summan är rottalet plus vänsterträdets summa plus högerträdets summa ... men tomt träd har summan noll. def summa(p): # Om den står utanför klassen slipper man self if p==None: return 0 return int(p.value)+summa(p.left)+summa(p.right) class Bintree - - - def sum(self): return summa(self.root) 4 REKURSIVT LÖVANTAL Rekursiv tanke: Antalet löv är antalet löv i vänsterträdet plus antalet löv i högerträdet ...men en ensam rotnod är ett löv ...och ett tomt träd har noll löv. def leaves(p): if p==None: return 0 if p.left==None and p.right==None: return 1 return leaves(p.left)+leaves(p.right) 5 REKURSIV HÖJD Rekursiv tanke: Höjden är 1 + max(höjden av vänsterträdet, höjden av högerträdet) ...men tomt träd har höjden -1. def height(p): if p==None: return -1 h1=height(p.left) h2=height(p.right) if h1>h2: return 1+h1 return 1+h2 ************************************************************** 6 STRYKORD Tomt ord är stamfar, söner får man genom att lägga på en bokstav och kolla i ordlistan. Eftersom man inte är ute efter kortaste strykord utan tvärtom längsta är breddenförst inte nödvändigt. Rekursiv djupetförst som går igenom hela trädet och noterar längdrekord är kanske bäst, särskilt eftersom letandet i ordlistan då hela tiden går framåt! Här har jag lagt alla svenska ord i ett binärträd - det tar förstås mycket minne och är onödigt. Man kan i stället läsa filen ord för ord eftersom man aldrig behöver backa. # coding:iso-8859-1 def byggut(ord): global rekord if len(ord)>len(rekord): rekord=ord for tkn in alfabet: if svenska.exists(ord+tkn): byggut(ord+tkn) from bintree import Bintree alfabet="abcdefghijklmnopqrstuvwxyzåäö" rekord="" svenska=Bintree() svenskfil = open("words.txt") for rad in svenskfil.readlines(): svenska.put(rad.strip()) # Strippa returtecknet byggut("") print "Längsta strykord:",rekord 7 SJUOR TILL HUNDRA Som gjort för breddenförst med heltalskö. # coding:iso-8859-1 from queue import Queue q=Queue() def makesons(tal): if tal==100: print "Hundra!" q.put(tal+7) q.put(tal-7) q.put(tal*7) if(tal%7==0): q.put(tal/7) q.put(0) while not q.isempty(): makesons(q.get()) Om man ska skriva ut lösningen: # coding:iso-8859-1 class Node: tal=0 far=None from queue import Queue from sys import exit q=Queue() def insert(tal,far): nod=Node() nod.tal=tal nod.far=far q.put(nod) def makesons(far): tal=far.tal if tal==100: writechain(far) exit() insert(tal+7,far) insert(tal-7,far) insert(tal*7,far) if(tal%7==0): insert(tal/7,far) def writechain(p): if p is None: return writechain(p.far) print p.tal q.put(Node()) while not q.isempty(): makesons(q.get()) 8 LABYRINT Problemträdet har (0,0) som stamfar och tillåtna grannpunkter ger söner. I en dumsonsmatris markerar man vilka punkter man redan besökt. Breddenförst fungerar då bra och ger kortaste vägen. # coding:iso-8859-1 from queue import Queue from sys import exit q=Queue() M=10 N=10 def makesons(koordinatpar): (xx,yy)=koordinatpar if xx==M-1 and yy==N-1: print "Ute!" for dx in [-1,0,1]: for dy in [-1,0,1]: x=xx+dx; y=yy+dy if 0<=x