Uppgift 3 - PK3 VT-03

Uppgift 3 ska lämnas in senast torsdagen den 15:e maj 2003. Lämna in den med hjälp av inlämningssystemet i slutet av denna sida. Läs igenom kodkonventionerna innan du börjar. Dessa skall följas.

Efter denna uppgift ska du ha kunskap om

• Hur ett binärt träd kan representeras.
• Diverse funktioner för binära träd samt komplexiteten hos dessa.

Före uppgiften

• Läs igenom hela uppgiften
• För programmeringsuppgifter, skriv dokumentation, dvs skriv med ord vad funktioner ska göra och hur de ska göra det, samt specifikation för funktioner och eventuella hjälpfunktioner. Endast det sistnämnda (specifikation) måste (och förväntas) inkluderas i din redovisning och ska följa kodkonventionerna. Se detta steg som en hjälp i att lösa uppgiften på bästa sätt. Att hoppa över förarbetet bidrar oftast till mer jobb i efterhand.

Din inlämning

Överst i din fil ska följande finnas (inom kommentartecken):

• Ditt namn och gruppnummer.
• Filens namn (absolut sökväg).
• En kort beskrivning (en rad) av vad filen innehåller.

Se till att du hunnit ge ett svar på varje deluppgift.

Uppgift

Uppgiften består av följande delmoment:

1. Implementera funktionen nbLeaves som ska ta ett binärt träd som argument och returnera antalet löv i detta. Analysera komplexiteten hos nbLeaves.
   
   Körexempel:
   - nbLeaves smallIntTree;
   > val it = 3 : int
   
   
2. Implementera funktionen (ska vara stuvad) exists som ska ta ett element som "första" argument, ett binärt träd som "andra" argument, och returnera sant omm (om och endast om) elementet existerar i det binära trädet. Analysera komplexiteten hos exists och jämför denna med komplexiteten hos exists för binära sökträd. Vad beror en eventuell skillnad på?
   
   Körexempel:
   - exists 3 smallIntTree;
   > val it = true : bool
   - exists 33 smallIntTree;
   > val it = false : bool
   - exists "skalman" smallStringTree;
   > val it = false : bool
   
   
3. Implementera funktionen (ska vara stuvad samt ickerekursiv) equal som ska ta två binära träd som argument och returnera sant omm en inordertraversering av dessa resulterar i samma sekvens. Jämförelsen skall göras med '='-predikatet. Analysera komplexiteten hos equal.
   
   Körexempel:
   - equal smallIntTree anotherSmallIntTree
   > val it = false : bool
   
   
   
4. Implementera funktionen preorder som ska ta ett binärt träd som argument och returnera en preordertraversering av detta i en lista. Denna funktion ska inte använda sig av någon hjälpfunktion.
   
   Körexempel:
   - preorder bigStringTree;
   > val it = ["skalman", "bamse", "lilleskutt", "daredevil", "läderlappen", "rocky", "hermanhedning", "johnnypuma", "modestyblaise", "x9", "fantomen", "kerrydrake", "luckyluke", "asterix", "obelix", "idefix", "bautasten", "majestix"] : string list
   
   
5. Implementera funktionen preorder'. Funktionaliteten ska vara densamma som för preorder men denna ska använda sig av exakt en hjälpfunktion där tekniken med en ackumulator ska användas.
   
   
6. Implementera funktionen preorders som ska ta en lista med binära sökträd som argument och returnera konkateneringen av preordertraverseringen av vart och ett av dessa i en lista. Denna funktion ska inte använda sig av någon hjälpfunktion. Dessutom ska max ett rekursivt anrop för varje klausul användas. Det sistnämnda förtydligas enklast med ett exempel:
   

   fun fib 0 = 1
     | fib 1 = 1
     | fib n = fib (n-1) + fib (n-2)
   
   fun fac 0 = 1 
     | fac n = n * fac (n-1) 
   

   Fibonacci-funktionen överst har två rekursiva anrop i dess tredje klausul. Fakultet-funktionen däremot har endast ett rekursivt anrop i sin andra klausul.
   
   Körexempel:
   - preorders [smallIntTree, anotherSmallIntTree];
   > val it = [1, 2, 5, 7, 3, 6, 10, 13, 2, 1, 7, 5, 13, 3, 6, 10] : int list
   
   
7. Implementera funktionen preorder''. Funktionaliteten ska vara densamma som för preorder men denna ska inte vara rekursiv. Tips: Använd dig av preorders som hjälpfunktion.
   
   
8. Analysera komplexiteten hos preorder, preorder' och preorder''. Vad beror en eventuell skillnad på?

Inlämning

Hämta ett formulär för att lämna in uppgiften genom att fylla i fälten nedan.