Oppgave 1a)

  public boolean leggInn(T verdi)
  {
    Node<T> p = rot, q = null;             // pekere
    int cmp = 0;                           // hjelpevariabel

    while (p != null)
    {
      q = p;                               // q er forelder til p
      cmp = comp.compare(verdi,p.verdi);   // sammenligner
      if (cmp < 0) p = p.venstre;          // går til venstre
      else if (cmp > 0) p = p.høyre;       // går til høyre
      else                                 // verdien finnes fra før
      {
        p.forekomster++;                   // øker antallet
        return true;
      }
    }

    p = new Node<>(verdi);                 // oppretter ny node

    if (q == null) rot = p;                // første node - rotnoden
    else if (cmp < 0) q.venstre = p;       // p blir venstre barn til q
    else q.høyre = p;                      // p blir høyre barn til q

    endringer++;                           // en endring i treet
    antall++;                              // en ny verdi i treet

    return true;                           // vellykket innlegging
  }

Oppgave 1b)

Hvis verdien som skal fjernes ligger i en node p med to barn, så går vi isteden til den neste noden r i inorden. Verdien i r kopieres inn i p og r fjernes. Nå kan det hende at det er flere forkomster av verdien i r. Dermed må en passe på at også forekomstantallet kopieres.

  public boolean fjern(T verdi)  // hører til klassen SBinTre
  {
    if (verdi == null) return false;  // treet har ingen nullverdier

    Node<T> p = rot, q = null;   // q skal være forelder til p

    while (p != null)            // leter etter verdi
    {
      int cmp = comp.compare(verdi,p.verdi);      // sammenligner
      if (cmp < 0) { q = p; p = p.venstre; }      // går til venstre
      else if (cmp > 0) { q = p; p = p.høyre; }   // går til høyre
      else break;    // den søkte verdien ligger i p
    }
    if (p == null) return false;   // finner ikke verdi

    p.forekomster--;               // reduserer antall forekomster

    if (p.forekomster > 0) return true;

    if (p.venstre == null || p.høyre == null)  // Tilfelle 1) og 2)
    {
      Node<T> b = p.venstre != null ? p.venstre : p.høyre;  // b for barn
      if (p == rot) rot = b;
      else if (p == q.venstre) q.venstre = b;
      else q.høyre = b;
    }
    else  // Tilfelle 3)
    {
      Node<T> s = p, r = p.høyre;   // finner neste i inorden
      while (r.venstre != null)
      {
        s = r;    // s er forelder til r
        r = r.venstre;
      }

      p.verdi = r.verdi;   // kopierer verdien i r til p
      p.forekomster = r.forekomster;  // kopierer forekomster

      if (s != p) s.venstre = r.høyre;
      else s.høyre = r.høyre;
    }

    endringer++;
    antall--;   // det er nå én node mindre i treet
    return true;
  }

Oppgave 1c)

  public boolean inneholder(T verdi)
  {
    if (verdi == null) return false;           // har ingen nullverdier

    Node<T> p = rot;
    while (p != null)
    {
      int cmp = comp.compare(verdi,p.verdi);   // sammenligner
      if (cmp < 0) p = p.venstre;              // går til venstre
      else if (cmp > 0) p = p.høyre;           // går til høyre
      else return true;                        // verdien er funnet
    }

    return false;                              // ukjent verdi
  }

Oppgave 1d)

  public String toString()
  {
    StringBuilder s = new StringBuilder();   // StringBuilder
    s.append('[');                           // starter med [
    if (!tom()) toString(rot,s);             // den rekursive metoden
    s.append(']');                           // avslutter med ]
    return s.toString();                     // returnerer
  }

  private static <T> void toString(Node<T> p, StringBuilder s)
  {
    if (p.venstre != null)                   // p har et venstre subtre
    {
      toString(p.venstre, s);                // komma og mellomrom etter
      s.append(',').append(' ');             // den siste i det venstre
    }                                        // subtreet til p

    s.append(p.verdi);                       // verdien i p
    int i = 1;
    while (i < p.forekomster)              // tar med duplikatene
    {
      s.append(',').append(' ').append(p.verdi);
      i++;
    }

    if (p.høyre != null)                     // p har et høyre subtre
    {
      s.append(',').append(' ');             // komma og mellomrom etter p
      toString(p.høyre, s);                  // siden p ikke er den siste
    }                                        // noden i inorden
  }

Oppgave 1e)

  @Override
  public Iterator<T> iterator()
  {
    return new InordenIterator();
  }

  private class InordenIterator implements Iterator<T>
  {
    private Stakk<Node<T>> s = new TabellStakk<>();  // for traversering
    private Node<T> p = null;                        // nodepeker
    private Node<T> q = null;                        // nodepeker
    private int iteratorforekomster;                 // forekomster
    private int iteratorendringer;                   // iteratorendringer

    private Node<T> først(Node<T> q)   // en hjelpemetode
    {
      while (q.venstre != null)        // starter i q
      {
        s.leggInn(q);                  // legger q på stakken
        q = q.venstre;                 // går videre mot venstre
      }
      return q;                        // q er lengst ned til venstre
    }

    public InordenIterator()  // konstruktør
    {
      if (rot == null) return;         // treet er tomt
      p = først(rot);                  // bruker hjelpemetoden
      iteratorforekomster = 1;         // første forekomst i p
      iteratorendringer = endringer;   // setter treets endringer
    }

    public T next()
    {
      if (iteratorendringer != endringer)
         throw new ConcurrentModificationException();

      if (!hasNext()) throw new NoSuchElementException();

      T verdi = p.verdi;               // tar vare på verdien i noden p
      q = p;                           // q oppdateres før p flyttes

      if (iteratorforekomster < p.forekomster)
      {
        iteratorforekomster++;
      }
      else
      {
        iteratorforekomster = 1;

        if (p.høyre != null)
        {
          p = først(p.høyre);    // p har høyre subtre
        }
        else if (!s.tom())
        {
          p = s.taUt();          // p har ikke høyre subtre
        }
        else p = null;           // stakken er tom
      }

      return verdi;              // returnerer verdien
    }

    public boolean hasNext()
    {
      return p != null;
    }

    public void remove()
    {
      throw new UnsupportedOperationException("Ikke laget!");
    }

  } //InordenIterator