DATS 2300202009

Prev Up Next

Hei alle sammen!

 

Super innsats med oblig 2! Det er veldig mange av dere som har gjort en god innsats med bruk av git og levert gode obliger. 

Denne uken så skal vi gå gjennom binære trær, og dette er pensum som er svært relevant for mappeeksamen som kommer straks. I de forhåndsinnspilte forelesningene så går jeg gjennom en god del terminologi - hvordan vi snakker om og beskriver binære trær. I tillegg går vi gjennom traversering av disse trærne. 

 

Egenskaper ved binære trær

I denne videoen går vi gjennom en del definisjoner av binære trær: dybde, indre noder, blad noder mm. 

OBS: merk at i starten av videoen (ved 1:40 ca og utover), så har jeg byttet om fullt tre og komplett tre. Et fullt tre har hver node null eller to barn, mens et komplett tre har alle nivåer fylt opp bortsett fra siste (som er fylt inn fra venstre). I den neste videoen så er de korrekte begrepene brukt. 

Forskjellige typer nodeplasseringer

I denne videoen går vi gjennom hvordan vi med X noder kan ha forskjellige trær, og hvordan dette vokser som Catalan-rekken. 

Traversering av binære trær

I denne videoen går vi gjennom nivå orden, pre orden, in orden og post orden sortering / traversering av noder i det binære treet. Vi ser på "bredde først" søk mot "dybde først søk", og diskuterer litt fordeler og ulemper med de to. 

Bredde først-traversering

I denne videoen går vi gjennom hvordan vi kan traversere et binærtre nivå orden - først på papir, og så i kildekode. 

Dybde først-traversering

I denne videoen går vi videre fra forrige video (hvor vi gikk nivå orden, eller bredde først) og ser på hvordan vi rekursivt (og ved bruk av stack) kan traversere ett tre i pre-, in-, og post-orden.