Oppgavesett 7 - Binære søketrær

Oppgavene blir tema på øvingen fredag 9. mars. Innleveringen skal bestå av en pdf-fil med korte kommentarer og dokumentasjon (utskrifter etc.). Legg også ved godt dokumenterte java filer. Alt pakkes i en zipfil, med navn assignment07-*.zip der * er etternavnene til gruppemedlemmene. Javafilene skal tilhøre en pakke med navn package assignment07.

Fristen for innlevering er tirsdag 13.mars 09:00.

Alle oppgavene dreier seg om ulike aspekter av binære søketrær. Dere kan ta utgangspunkt i klassen Bst som vi programmerte i en forelesning.

Oppgave 1

A

Ved en inorder traversering av et tre får vi følgende rekkefølge:

                               D - E - B - F - C - A

Tegn et binærtre som kan generere denne sekvensen.

B

Legg til og implementer metodene void inOrder(Node n) og void postOrder(Node n) i klassen Bst, som printer ut treet i henholdsvis inorder og postorder. Dokumenter at de virker ved å bygge opp treet du har kommet fram til i forrige deloppgave.

C

I en levelorder traversering starter man i rota og beveger fra venstre til høyre i hvert nivå (første nivå er rota, neste nivå er barna til rota, og neste nivå deretter er alle barnebarna etc). Algoritmen bruker en kø, og går slik: Legg først rota i køen. Deretter gjør man følgende helt til køen er tom: Ta ut første element (og f.eks. skriv det ut), og legg de eksisterende barna i køen.

Legg til og implementer metoden void levelOrder(Node root) i klassen Bst, som printer ut innholdet i levelorder rekkefølge. Dokumenter at den virker.

*D

Modifiser metoden void levelOrder(Node root) i klassen Bst, slik at den printer ut hvert nivå på en linje, f.eks. slik:

Level 0: 42
Level 1: 21 76
...etc

Det kan være lurt å legge til et felt i nodeklassen som forteller hvilket nivå noden er på. Dokumenter at metoden virker.

Oppgave 2

Her er et binært søketre med heltallsverdier:

                                       62
                                     /    \
                                    /      \
                                   41       78
                                  / \      / \
                               29    53   67   82
                                     /
                                    43
                                     \
                                     46

A

Sett inn en node med verdi 42 i treet. Forklar framgangsmåten og tegn treet etter innsetting.

B

Bruk standard regler for fjerning av noder i et binært søketre, og slett noden med verdi 53 fra treet slik det var før innsettingen. Forklar framgangsmåten, illustrer de ulike trinnene, og tegn treet etter sletting. Gjør det samme med node 41 (bruk treet slik det var opprinnelig før innsetting/sletting).

*C

Implementer metoden void remove (Node root, int v) i klassen Bst, som fjerner en node med verdi v hvis den finnes, og ellers gjør ingenting.

* Oppgave 3

Høyden i et tre er definert som den største av avstandene fra rota til bladnodene. Høyden til et tre som består av kun rota er 0. Et perfekt binærtre (PBT) er et tre der alle nivåer er fylt opp helt (og er altså perfekt balansert). Mer presist har et PBT med høyde lik null ingen barn, og for et PBT med høyde h større enn null, er hvert subtre et PBT med høyde h-1,

I et komplett binærtre (CBT) er hvert nivå fyllt opp fra venstre, men det siste nivået behøver ikke være fyllt helt opp, slik det er tilfelle med et PBT. Mer presist betyr det at for et CBT med høyde 0, er det ingen barn. For et CBT med med høyde h større enn null, må et av to være tlfelle: 1) Venstre subtre er et PFT med høyde h-1, og høyre er et CBT med høyde h-1, eller 2) Venstre subtre er et CBT med høyde h-1, og høyre subtre er et PFT med høyde h-2.

Implementer metoden boolean complete(Node n) i klassen Bst som sjekker om treet er komplett eller ikke. Dokumenter at den virker!