Kmom06: Datastrukturen träd

By . Latest revision .

Gör dbwebb update innan du startar med kursmomentet.

Vi jobbar vidare med datastrukturer, algoritmer och rekursion genom att kolla på träd strukturer. Mer specifikt ska vi lära oss skapa ett Binärt sökträd och skapa algoritmer som kan traversera trädet rekursivt.

Ett binärt sökträd.

Ett binärt sökträd.

Det finns två valfria delar i detta kmom som är repetition av Dictionaries från den första Python kursen. Detta är för att uppfriska minnet av hur man jobbar med key/value par i datastrukturer och för projektet i kmom10 kan man välja mellan att använda sig av listor eller dictionaries. Tidigare år har det framkommit att många inte känner sig säkra på Dictionaries och därför valde alla att använda listor. Därför har jag lagt till material så man kan friska upp sitt minne av dictionaries, vilket förhoppningsvis gör att ni kan välja den metod som ni tycker verkar bäst/lättast och inte bara välja listor för att ni inte kommer ihåg dictionaries.

(Detta är instruktionen för kursmomentet och omfattar det som skall göras inom ramen för kursmomentet. Momentet omfattar cirka 20 studietimmar inklusive läsning, arbete med övningar och uppgifter, felsökning, problemlösning, redovisning och eftertanke. Läs igenom hela kursmomentet innan du börjar jobba. Om möjligt – planera och prioritera var du vill lägga tiden.)

#Läsanvisningar

(ca: 1 studietimmar)

#Kurslitteratur

Läs följande:

Inget att läsa.

#Artiklar

  1. Läs vilka fördelar som finns med BST över hash tables.

  2. Läs om de olika fördelarna med som finns för olika datastrukturer.

#Video

Titta på följande:

  1. Kolla på de video som börjar med kmom06 i spellistan.

#Lästips

  1. Förra årets föreläsning. Pratar allmänt om programmering, bl.a. att plugga programmering VS. jobba med programmering.

  2. How to use the Python debugger. Lär er använda Pythons debugger för att stega igenom koden.

  3. Python debugger i atom. Installera Pythons debugger i atom så du kan stega igenom koden i atom istället för i terminalen. (Har inte testat den än. Om du testar skriv i redovisningstexten om den funkade bra).

#Övningar & Uppgifter

(ca: 19 studietimmar)

#Övningar

  1. Valfritt, friska upp minnet av dictionaries med övningen Dictionaries och tuple i Python.

  2. Gör övningen Träd datastrukturer.

#Uppgifter

Dessa uppgifter skall utföras och redovisas.

  1. Valfritt, gör labben “Dictionaries i Python

  2. Gör uppgiften “Skapa ett Binary Search Tree

# Ställ dig i kurskatalogen
dbwebb publish flask

#Extra

Det finns inga extrauppgifter.

#Resultat & Redovisning

(ca: 1-2 studietimmar)

Läs instruktionen om hur du skall redovisa.

Se till att följande frågor besvaras i redovisningstexten.

  • Vad är ett Binärt sökträd?
  • Hur gick det att skriva de rekursiva funktionerna?
  • Vad är Inorder, Preorder och Postorder när man pratar om traversera träd?
  • Vad är en Hash table?
  • Kan du jämföra och resonera kring de olika datastrukturerna vi gått igenom i kursen? Vilken passar till vad?
  • Gick det bra att utföra kursmomentet?

#Revision history

  • 2020-02-21: (D, aar) Added optional dictionary material.
  • 2019-02-22: (C, aar) Changed to be about Binary Search Tree.
  • 2018-02-12: (B, aar) First version v2.
  • 2017-11-10: (PB1, mos) Utkast till v2.
  • 2017-02-14: (A, lew) First version.

Document source.