Oppgave 1

  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

    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

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

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

  public void fjernMin()  // hører til klassen SBinTre
  {
    if (tom()) throw new NoSuchElementException("Treet er tomt!");

    if (rot.venstre == null) rot = rot.høyre;  // rotverdien er minst
    else
    {
      Node<T> p = rot.venstre, q = rot;
      while (p.venstre != null)
      {
        q = p;  // q er forelder til p
        p = p.venstre;
      }
      // p er noden med minst verdi
      q.venstre = p.høyre;
    }

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

Oppgave 2

OBS: Hvis en bruker flg. enkle versjon, vil oppdateringen av endringer skje i fjernMin():

  public void nullstill()
  {
    while (!tom()) fjernMin();
  }

Hvis en bruker flg. versjon, holder det å gjøre en oppdatering i den offentlige metoden:

  public void nullstill()
  {
    if (!tom()) nullstill(rot);  // nullstiller
    rot = null; antall = 0;      // treet er nå tomt
    endringer++;   // treet er endret
  }

  private void nullstill(Node<T> p)
  {
    if (p.venstre != null)
    {
      nullstill(p.venstre);      // venstre subtre
      p.venstre = null;          // nuller peker
    }
    if (p.høyre != null)
    {
      nullstill(p.høyre);        // høyre subtre
      p.høyre = null;            // nuller peker
    }
    p.verdi = null;              // nuller verdien
  }

Oppgave 4

  // ny konstruktør i klassen InordenIterator

  public InordenIterator(T verdi)    // konstruktør
  {
    if (verdi == null)
      throw new IllegalArgumentException("Treet har ikke nullverdier!");

    Node<T> q = rot

    while (q != null)
    {
      int cmp = comp.compare(verdi, q.verdi);

      if (cmp < 0)
      {
        s.leggInn(q);
        q = q.venstre;
      }
      else if (cmp > 0)
      {
        q = q.høyre;
      }
      else break;
    }

    if (q != null) p = q;
    else if (!s.tom()) p = s.taUt();

    iteratorendringer = endringer;   // setter treets endringer
  }

  // metode i klassen SBinTre

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

Oppgave 5

  private class OmvendtInordenIterator 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 iteratorendringer;                   // iteratorendringer

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

    public OmvendtInordenIterator()  // konstruktør
    {
      if (rot == null) return;         // treet er tomt
      p = sist(rot);                   // bruker hjelpemetoden
      iteratorendringer = endringer;   // setter treets endringer
    }

    public OmvendtInordenIterator(T verdi)    // konstruktør
    {
      if (verdi == null)
        throw new IllegalArgumentException("Treet har ikke nullverdier!");

      Node<T> q = rot;

      while (q != null)
      {
        int cmp = comp.compare(verdi, q.verdi);

        if (cmp < 0)
        {
          q = q.venstre;
        }
        else
        {
          s.leggInn(q);
          q = q.høyre;
        }
      }
      if (!s.tom()) p = s.taUt();

      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 (p.venstre != null) p = sist(p.venstre);  // 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();
    }

  } // OmvendtInordenIterator

  public Iterator<T> riterator()
  {
    return new OmvendtInordenIterator();
  }

  public Iterator<T> riterator(T verdi)
  {
    return new OmvendtInordenIterator(verdi);
  }