Oppgave 1

Nivåorden:	A B C D E F G H I J K L M N O P Q R S T U V
Omvendt nivåorden:	V U T S R Q P O N M L K J I H G F E D C B A
Speilvendt nivåorden:	A C B G F E D N M L K J I H V U T S R Q P O
Preorden:	A B D H O I P Q E J R K S C F L M T U G N V
Omvendt preorden:	V N G U T M L F C S K R J E Q P I O H D B A
Speilvendt preorden:	A C G N V F M U T L B E K S J R D I Q P H O
Postorden:	O H P Q I D R J S K E B L T U M F V N G C A
Omvendt postorden:	A C G N V F M U T L B E K S J R D I Q P H O
Speilvendt postorden:	V N G U T M L F C S K R J E Q P I O H D B A

Oppgave 2

a)

  public void omvendtNivåorden(Oppgave<? super T> oppgave)
  {
    if (rot == null) return;  // tomt tre

    Stakk<T> s = new TabellStakk<>();

    Kø<Node<T>> kø = new TabellKø<>();
    kø.leggInn(rot);

    while (!kø.tom())
    {
      Node<T> p = kø.taUt();
      s.leggInn(p.verdi);

      if (p.venstre != null) kø.leggInn(p.venstre);
      if (p.høyre != null) kø.leggInn(p.høyre);
    }

    while (!s.tom()) oppgave.utførOppgave(s.taUt());
  } 

b)

  public void omvendtNivåorden(Oppgave<? super T> oppgave)
  {
    if (tom()) return;

    Liste<Node<T>> liste = new TabellListe<>();
    liste.leggInn(rot);

    for (int i = 0; i < liste.antall(); i++)
    {
      Node<T> p = liste.hent(i);
      if (p.venstre != null) liste.leggInn(p.venstre);
      if (p.høyre != null) liste.leggInn(p.høyre);
    }

    for (int i = liste.antall() - 1; i >= 0; i--)
    {
      oppgave.utførOppgave(liste.hent(i).verdi);
    }
  }

Oppgave 3

  private static <T> void
  speilvendtInorden(Node<T> p, Oppgave<? super T> oppgave)
  {
    if (p.høyre != null) speilvendtInorden(p.høyre,oppgave);
    oppgave.utførOppgave(p.verdi);
    if (p.venstre != null) speilvendtInorden(p.venstre,oppgave);
  }

  public void speilvendtInorden(Oppgave<? super T> oppgave)
  {
    if (rot != null) speilvendtInorden(rot,oppgave);
  }

Oppgave 4

  private static <T> void speilvendtPostorden(Node<T> p, Oppgave<? super T> o)
  {
    if (p.høyre != null) speilvendtPostorden(p.høyre,o);
    if (p.venstre != null) speilvendtPostorden(p.venstre,o);
    o.utførOppgave(p.verdi);
  }

  public void speilvendtPostorden(Oppgave<? super T> o)
  {
    if (rot != null) speilvendtPostorden(rot,o);
  }

Oppgave 5

  public void omvendtPreorden(Oppgave<? super T> o)
  {
    if (rot != null) speilvendtPostorden(rot,o);
  } 

Oppgave 6

  public void omvendtPostorden(Oppgave<? super T> o)
  {
    if (rot != null) speilvendtPreorden(rot,o);
  }

Oppgave 7

Ta utgangspunkt i treets konturkurve. Bruk f.eks. Figur 5.1.7 a). Vi får speilvendt postorden når vi følger kurven motsatt vei og setter opp nodeverdien når noden passeres for tredje gang. Men tredje gang når vi går motsatt retning svarer til, men i motsatt rekkefølge, første gang når vi går den normale retningen. Det betyr at speilvendt postorden og omvendt preorden blir det samme. Samme type argument kan vi bruke for å vise at speilvendt preorden er det samme som omvendt postorden.