INF1020 ukeoppgaver uke 2 (5/9-9/9)
====================================


OPPGAVE 1:
----------

MAW oppgave 4.4, 4.6, 4.8, 4.9


OPPGAVE 2:
----------

Gitt et tre der nodene er av f?lgende klasse:
   class BinNode {
      int data;
      BinNode venstre;
      BinNode hoyre;
   }
(Et tomt tre representeres ved referansen null.)

a) Skriv en metode
      int antall(BinNode t)
   som returnerer antall noder i t.

b) Skriv en metode
      int sum(BinNode t)
   som returnerer summen av tallverdien til samtlige noder i t.


OPPGAVE 3
---------

Anta at nodene i et bin?rt tre har en peker til forelder (null i
roten), i tillegg til de vanlige venstre og hoyre. Skriv metoder 
lokalt i BinNode som finner (og leverer) neste node (relativt til
this) i henholdsvis infiks, prefiks og postfiks rekkef?lge. 
null returneres dersom this er siste node i den aktuelle
rekkef?lgen.


OPPGAVE 4
---------

Vi vil bruke et bin?rt s?ketre til ? lagre et antall objekter som
inneholder en "int verdi", samt en del andre data. Vi skal anta at
hver node har en venstre og en h?yre peker p? vanlig m?te. Det kan
imidlertid v?re flere objekter som har samme verdi (men gjerne med
forskjellig data), og disse skal alle lagres som separate objekter i
treet.

a) Vi kan l?se dette ved alltid ? g? helt til bunns n?r vi skal gj?re
   en innsetting, SELV OM vi treffer p? et objekt med samme verdi p?
   veien. Vi kan da velge alltid ? g? videre ned i h?yre subtre n?r vi
   passerer et objekt med samme verdi. Skriv en innsettingsmetode som
   f?lger denne filosofien, og tegn noen typiske tr?r denne kan gi
   oss.

b) I hvilken rekkef?lge vil vi f? ut objektene med lik verdi dersom vi
   skriver ut tr?rne produsert under a) i vanlig infiks rekkef?lge?
   Hvordan blir dette om vi g?r til venstre istedenfor til h?yre n?r
   vi treffer p? en node med lik verdi under innsettingen?

c) Dersom det er mange noder med like verdier, kan disse bidra til at
   treet blir un?dvendig dypt. Vi kunne da i stedet tenke p? ? lagre
   alle nodene med like verdier i en liste ut fra den f?rste noden med
   denne verdien. Dette ville imidlertid kreve at vi hadde en ekstra
   peker for denne listen, men vi kan klare oss som f?lger: N?r vi vil
   sette inn et objekt og det allerede finnes ett (men bare ett)
   objekt med denne verdien i treet, s? hekter vi det nye objektet inn
   mellom det gamle, og dets h?yre subtre. Dersom det senere kommer
   flere objekter med samme verdi, s? hektes disse inn p? en liste ut
   fra det ANDRE objektet, med venstre-pekeren som listepeker. TEGN
   eksempler, og skriv en innsettingsmetode som bruker denne
   filosofien.

d) Vis at dersom man skriver ut treet produsert under c) i innfiks
   rekkef?lge, s? kommer fremdeles nodene med like verdier samlet. Men
   i hvilken rekkef?lge kommer de? Skriv en modifisert utskriftsmetode
   som gj?r at noder med like verdier skrives ut i den rekkef?lge de
   ble satt inn.