Oppgave 1A

Etter de første innleggingene inneholder køen 5, 3, 1. Deretter tas den første ut og legges med en gang bakerst. Dette skjer 5 ganger. Dermed blir utskriften lik 1 5 3

Oppgave 1B

  public static <T> void kopier(Kø<T> A, Kø<T> B)
  {
    int antall = A.antall();

    for (int i = 0; i < antall; i++)
    {
      T verdi = A.taUt();  // tar ut den første
      B.leggInn(verdi);    // legger den inn i B
      A.leggInn(verdi);    // legger den bakerst i A
    }
  }

Oppgave 2A

  public void leggInnSist(T verdi)
  {
    if (tom()) hode = new Node<>(verdi,null);
    else
    {
      Node<T> p = hode;
      for (int i = 1; i < antall; i++) p = p.neste;
      p.neste = new Node<T>(verdi,null);
    }
    antall++;
  }

Oppgave 2B

Oppgaveteksten sier at: «I metoden skal det hverken forsvinne noder eller lages nye noder.» Det betyr at metoden leggInnFørst ikke kan brukes siden den alltid oppretter en ny node.

1. versjon. Vi kan plassere én og én node først. Den andre noden legges foran den første. Den tredje noden legges foran den som nå er først, osv. Dette får vi til ved å omdirigere pekere. Det trengs ingen hjelpestrukturer:

  public void snu()
  {
    if (antall() <= 1) return;

    Node<T> p = hode.neste;
    hode.neste = null;  // dette blir nå den siste noden

    while (p != null)
    {
      Node<T> q = p.neste;
      p.neste = hode;
      hode = p;  // nå ligger p først i listen
      p = q;
    }
  }

2. versjon. Vi kan legge én og én node på en stakk og så bygge opp listen ved å ta fra stakken.

  public void snu()
  {
    Stakk<Node<T>> s = new TabellStakk<>();

    Node<T> p = hode;
    while (p != null)
    {
      s.leggInn(p);  // // legger nodene på en stakk
      p = p.neste;
    }

    hode = p = s.taUt();  // nytt hode

    while (!s.tom())
    {
      p = p.neste = s.taUt();
    }

    p.neste = null;  // p er siste node
  }

3. versjon. Vi kan legge én og én verdi på en stakk. Deretter oppdaterer vi nodeverdiene ved å hente fra stakken. Da er det ingen endringer i nodenes nestepeker.

  public void snu()
  {
    Stakk<T> s = new TabellStakk<>();

    Node<T> p = hode;

    while (p != null)
    {
      s.leggInn(p.verdi);
      p = p.neste;
    }

    p = hode;

    while (p != null)
    {
      p.verdi = s.taUt();
      p = p.neste;
    }
  }

Oppgave 3A

Preorden: 8 3 2 1 6 5 4 5 7 9 12 10 10 13

Oppgave 3B

  public T sistePreorden()
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    Node<T> p = rot;

    while (true)
    {
      if (p.høyre != null) p = p.høyre;
      else if (p.venstre != null) p = p.venstre;
      else return p.verdi;
    }
  }

Oppgave 3C

Hvis den neste ligger et sted nærmere roten, kan vi finne den ved å starte i roten og gå nedover. Da søker vi oss ned til p ved å søke etter p.verdi. Vi vet at p må være en bladnode. Det kan være duplikater i treet. Vi må derfor forsette søkingen selv om vi finner en node med samme verdi som den p har. Vi bruker to hjelpepekere. Pekeren q skal gå ned til p. Pekeren r settes lik q.høyre når sammenligingen sier at vi skal til venstre for q samtidig som q.høyre ikke er null. Oppgaven sier at vi kan anta at p ikke er null.

Generelt har vi at hvis p er en bladnode, så må vi finne den næremste noden q på veien mot roten som er slik at p er i det venstre subtreet til q og q har et høyre barn. Dette høyrebarnet er den neste i preorden. Hvis p er den siste i preorden, så finnes ingen slik q. Da sier vi at det er null som er den neste.

  private Node<T> nestePreorden(Node<T> p)
  {
    if (p.venstre != null) return p.venstre;

    if (p.høyre != null) return p.høyre;

    Node<T> q = rot, r = null;  // starter i roten

    while (q != p)  // leter etter p
    {
      if (comp.compare(p.verdi,q.verdi) < 0)
      {
        if (q.høyre != null) r = q.høyre;  // oppdaterer r
        q = q.venstre;
      }
      else q = q.høyre;
    }
    return r;  // den neste i preorden
  }

Metoden public void preorden(Oppgave<T> oppgave) lages ved å gjøre gjentatte kall på metoden nestePreorden:

  public void preorden(Oppgave<T> oppgave)
  {
    Node<T> p = rot;

    while (p != null)
    {
      oppgave.utførOppgave(p.verdi);
      p = nestePreorden(p);
    }
  }

Metoden public void preorden(Oppgave<T> oppgave) kan brukes slik:

  int[] a = {8,3,6,9,12,2,5,10,7,13,1,4,10,5};
  Comparator<Integer> c = Komparator.naturlig();  // en komparator

  SBinTre<Integer> tre = new SBinTre<>(c);        // et tre
  for (int k : a) tre.leggInn(k);                 // bygger treet

  tre.preorden(new KonsollUtskrift<Integer>());

  // Utskrift: 8 3 2 1 6 5 4 5 7 9 12 10 10 13

Oppgave 3D

Den bladnoden som bestemmer den lengste grenen slik som det er definert i oppgaveteksten, er den noden som kommer sist i nivåorden. En mulig løsning er derfor å traversere i nivåorden til vi kommer til den siste. Deretter starter vi i rotnoden og leter oss ned til denne noden. På veien nedover legger vi nodeverdiene inn i en liste. Til slutt bruker vi listens toString-metode. Vi bruker en kø til å traversere i nivåorden:

  public String lengstgren()
  {
    if (tom()) return "[]";

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

    Node<T> p = null;

    while (!kø.tom())  // traverserer i nivåorden
    {
      p = kø.taUt();
      if (p.venstre != null) kø.leggInn(p.venstre);
      if (p.høyre != null) kø.leggInn(p.høyre);
    }

    // p er nå den siste i nivåorden

    Liste<T> liste = new TabellListe<>();

    Node<T> q = rot;

    while (q != null) // finner veien ned til p
    {
      liste.leggInn(q.verdi);
      if (comp.compare(p.verdi, q.verdi) < 0) q = q.venstre;
      else q = q.høyre;
    }
    return liste.toString();
  }

Det er også mulig å gjøre det rekursivt. Da kan vi f.eks. traversere i preorden samtidig som vi kontinuerlig holder tak i nodeverdiene fra roten og ned til den noden vi er på. Hver gang vi kommer til en bladnode som ligger dypere enn den vi hadde sist, registrerer vi nodeverdiene. Siden vi skal finne den som ligger lengst til høyre, kan vi traversere i speilvendt preorden. Obs: Denne løsninsgteknikken er maken til den som ble brukt i Oblig 3.

  // privat rekursiv hjelpemetode
  private void lengstgren(Node<T> p, int[] nivå, String[] s, Toveiskø<T> gren)
  {
    gren.leggInnSist(p.verdi);  // legger inn verdien

    if (p.høyre == null && p.venstre == null)
    {
      if (gren.antall() > nivå[0]) // en dypere bladnode enn sist
      {
        nivå[0] = gren.antall();   // registrerer dybden
        s[0] = gren.toString();    // registerer nodeverdiene
      }
    }
    else
    {
      if (p.høyre != null) lengstgren(p.høyre, nivå, s, gren);
      if (p.venstre != null) lengstgren(p.venstre, nivå, s, gren);
    }
    gren.taUtSist();  // fjerner
  }

  public String lengstgren()
  {
    if (tom()) return "[]";
    int[] nivå = {0};
    String[] s = {null};
    Toveiskø<T> gren = new TabellToveiskø<>();
    lengstgren(rot,nivå,s,gren);
    return s[0];
  }

Oppgave 4A

Huffmantre med posisjonstall på bladnodene

A: posisjon: 15  bitkode: 111
B: posisjon: 28  bitkode: 1100
C: posisjon: 58  bitkode: 11010
D: posisjon:  4  bitkode: 00
E: posisjon:  6  bitkode: 10
F: posisjon: 10  bitkode: 010
G: posisjon: 59  bitkode: 11011
H: posisjon: 11  bitkode: 011

11001110010110011111011 = 1100 111 00 10 1100 111 11011 = BADEBAG

Oppgave 4B

I komparatoren blir først lengdene på de to tegnstrengene s og t sammenlignet i setningen int k = t.length() - s.length(); Det betyr at hvis lengden til s er større enn lengden til t, vil k bli negativ. Det betyr at den som er lengst av s og t blir sett på som «minst». Hvis de har samme lengde, sammenlignes s og t alfabetisk. Utskriften blir derfor: Asta Kari Ole Per