Oppgave 2

  Integer[] a = {4,8,3,1,7,4,9,1,6,10,2,1,5,10,7,8};        // tabell
  SFBinTre<Integer> tre = SFBinTre.sfbintre(Stream.of(a));  // et tre

  System.out.println(tre);                        // bruker toString
  for (int k : tre) System.out.print(k + "  ");   // bruker iteratoren

Oppgave 3

  public String toString()
  {
    if (tom()) return "[]";
    StringBuilder s = new StringBuilder();   // StringBuilder
    s.append('[');                           // starter med [

    Node<T> p = rot;
    while (p.venstre != null) p = p.venstre;
    s.append(p.verdi);

    while (true)
    {
      if (p.høyre != null)
      {
        p = p.høyre;
        while (p.venstre != null) p = p.venstre;
      }
      else
      {
        while (p.forelder != null && p.forelder.høyre == p)
        {
          p = p.forelder;
        }
        p = p.forelder;
      }
      if (p == null) break;
      s.append(',').append(' ').append(p.verdi);
    }
    s.append(']');

    return s.toString();
  }

Oppgave 4

  public String omvendtString()
  {
    if (tom()) return "[]";
    StringBuilder s = new StringBuilder();   // StringBuilder
    s.append('[');                           // starter med [

    Node<T> p = rot;
    while (p.høyre != null) p = p.høyre;
    s.append(p.verdi);

    while (true)
    {
      if (p.venstre != null)
      {
        p = p.venstre;
        while (p.høyre != null) p = p.høyre;
      }
      else
      {
        while (p.forelder != null && p.forelder.venstre == p)
        {
          p = p.forelder;
        }
        p = p.forelder;
      }
      if (p == null) break;
      s.append(',').append(' ').append(p.verdi);
    }
    s.append(']');

    return s.toString();
  }

Oppgave 5

Oppgave 6

  /////////// class InordenIterator //////////////

  private class InordenIterator implements Iterator<T>
  {
    private Node<T> p = null;
    private Node<T> q = null;
    private int iteratorendringer;

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

    public InordenIterator()  // konstruktør
    {
      if (rot != null) p = først(rot);    // bruker hjelpemetoden
      iteratorendringer = endringer;
    }

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

      T verdi = p.verdi;             // tar vare på verdien i noden p
      q = p;                         // q er den forrige til p

      if (p.høyre != null)           // p har høyre subtre
      {
        p = først(p.høyre);          // går til venstre i subtreet
      }
      else                           // p har ikke høyre subtre
      {
        while (p.forelder != null && p.forelder.høyre == p)
        {
          p = p.forelder;            // fortsetter opp mot venstre
        }
        p = p.forelder;              // nå er p den neste (eller null)
      }
      return verdi;                  // returnerer verdien
    }

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

    @Override
    public void remove()
    {
      if (q == null) throw new IllegalStateException("Fjerning er ulovlig!");

      if (iteratorendringer != endringer)
                 throw new ConcurrentModificationException("Treet er endret!");

      if (q.høyre == null)                     // Tilfelle 1)
      {
        // hvis q har et venstre barn, vil det når q
        // fjernes få ny forelder 

        if (q.venstre != null)
        {
          q.venstre.forelder = q.forelder;     // ny forelder
        }

        if (p == null)                         // Tilfelle 1a)
        {
          if (q == rot)                        // q er lik roten
          {
            rot = q.venstre;                   // q fjernes
          }
          else                                 // q ligger nede i treet
          {
            q.forelder.høyre = q.venstre;      // q fjernes
          }
        }
        else // p != null                      // Tilfelle 1b)
        {
          if (q == p.venstre)                  // p.venstre har ikke høyre subtre
          {
            p.venstre = q.venstre;             // q fjernes
          }
          else                                 // q ligger i subtreet
          {
            q.forelder.høyre = q.venstre;      // q fjernes
          }
        }
      }
      else // q.høyre != null                  // Tilfelle 2)
      {
        q.verdi = p.verdi;                     // kopierer

        // hvis p har et høyre barn, vil det når p
        // fjernes få en ny forelder

        if (p.høyre != null)
        {
          p.høyre.forelder = p.forelder;       // ny forelder    
        }

        if (q.høyre == p)                      // q.høyre har ikke venstre barn
        {
          q.høyre = p.høyre;                   // fjerner p
        }
        else                                   // q.høyre har venstre barn
        {
          p.forelder.venstre = p.høyre;        // fjerner p
        }

        p = q;                                 // setter p tilbake til q
      }


      q = null;                // q settes til null
      iteratorendringer++;     // en endring i treet via iteratoren
      endringer++;             // en endring i treet
      antall--;                // en verdi mindre i treet
    }

  } // class InordenIterator

Oppgave 7

  /////////// class InordenIterator //////////////

  private class InordenIterator implements Iterator<T>
  {
    private Node<T> p = null;
    private int iteratorendringer;
    private boolean removeOK = false;

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

    public InordenIterator()  // konstruktør
    {
      if (rot != null) p = først(rot);    // bruker hjelpemetoden
      iteratorendringer = endringer;
    }

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

      T verdi = p.verdi;             // tar vare på verdien i noden p

      if (p.høyre != null)           // p har høyre subtre
      {
        p = først(p.høyre);          // går til venstre i subtreet
      }
      else                           // p har ikke høyre subtre
      {
        while (p.forelder != null && p.forelder.høyre == p)
        {
          p = p.forelder;            // fortsetter opp mot venstre
        }
        p = p.forelder;              // nå er p den neste (eller null)
      }

      removeOK = true;

      return verdi;                  // returnerer verdien
    }

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

    @Override
    public void remove()
    {
      if (!removeOK)
        throw new IllegalStateException("Fjerning er ulovlig!");

      if (iteratorendringer != endringer)
        throw new ConcurrentModificationException("Treet er endret!");

      if (p == null)  // den siste skal fjernes
      {
        Node<T> q = rot;
        while (q.høyre != null) q = q.høyre;

        // q skal fjernes - har ikke høyre barn

        if (q.venstre != null)
        {
          q.venstre.forelder = q.forelder;  // oppdaterer forelder
        }

        if (q == rot)
        {
          rot = q.venstre;
        }
        else
        {
          q.forelder.høyre = q.venstre;
        }
      }
      else if (p.venstre != null)
      {
        Node<T> q = p.venstre;
        while (q.høyre != null) q = q.høyre;

        // q skal fjernes - har ikke høyre barn

        if (q.venstre != null)
        {
          q.venstre.forelder = q.forelder;  // oppdaterer forelder
        }

        if (q == p.venstre)
        {
          p.venstre = q.venstre;
        }
        else
        {
          q.forelder.høyre = q.venstre;
        }
      }
      else  // p.venstre == null
      {
        // vi må oppover mot roten

        Node<T> q = p;

        while (q.forelder.venstre == q)
        {
          q = q.forelder;            // fortsetter opp mot høyre
        }

        q = q.forelder;              // nå er q den forrige  

        // q skal fjernes

        if (q.venstre == null)  // q har kun ett barn
        {
          Node<T> f = q.forelder;

          q.høyre.forelder = f;  // oppdaterer forelder

          if (f == null)  // q er roten
          {
            rot = q.høyre;
          }
          else if (q == f.venstre)  // q er et venstre barn
          {
            f.venstre = q.høyre;
          }
          else                      // q er et høyre barn
          {
            f.høyre = q.høyre;
          }
        }
        else  // q har to barn
        {
          // verdien til p kopieres inn i q og p fjernes

          q.verdi = p.verdi;

          if (p.høyre != null)
          {
            p.høyre.forelder = p.forelder;
          }

          if (p == q.høyre)
          {
            q.høyre = p.høyre;
          }
          else
          {
            p.forelder.venstre = p.høyre;
          }

          p = q;
        }
      }

      removeOK = false;

      iteratorendringer++;     // en endring i treet via iteratoren
      endringer++;             // en endring i treet
      antall--;                // en verdi mindre i treet
    }

  } // class InordenIterator