Kmom07: Datastrukturen träd

By . Latest revision .

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.

Kursmomentet är under utveckling. Börja inte med materialet innan denna gula ruta är borta!

Gör dbwebb update innan du startar med kursmomentet.

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 Pythonkursen. Detta är för att friska upp 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 tidigare års 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

#Extra

Det finns inga extrauppgifter.

#Lämna in

Läs Lämna in och redovisa uppgift för att ta reda på hur ni lämna in era uppgifter när ni är klara.

#Revision history

  • 2022-02-18: (E, grm) Tog bort kapitlet om redovisning.
  • 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.