Oppgave 1

  public static void main(String[] args) throws IOException
  {
    BinTre<Integer> tre = BinTre.random(100000);    // 100000 noder

    class IngenOppgave implements Oppgave<Integer>  // en lokal klasse
    {
      public void utførOppgave(Integer s) {}        // ingenting utføres
    }

    IngenOppgave oppgave = new IngenOppgave();

    long t = System.currentTimeMillis();
    for (int i = 0; i < 1000; i++) tre.inordenMorris(oppgave);
    System.out.println("Tid: " + (System.currentTimeMillis() - t));
  }

Oppgave 2

  private static <T> Node<T> trekkTråderOmvendtInorden(Node<T> p)
  {
    while (p.høyre != null)
    {
      Node<T> q = p.høyre;
      while (q.venstre != null)
        q = q.venstre;
      q.venstre = p;  // q er forgjengeren til p
      p = p.høyre;
    }
    return p;
  }

  private static <T> boolean fraTilOmvendtInorden(Node<T> r, Node<T> q)
  {
    while (r != null && r != q)
      r = r.venstre;
    return r != null;
  }

  public void omvendtInordenMorris(Oppgave<? super T> oppgave)
  {
    if (rot == null) return;

    for (Node<T> p = trekkTråderOmvendtInorden(rot);;)
    {
      oppgave.utførOppgave(p.verdi);

      Node<T> q = p;
      if ((p = p.venstre) == null) return;

      if (p.høyre != null)
      {
        if (fraTilOmvendtInorden(p.høyre,q))
          q.venstre = null;  // kutter tråden
        else p = trekkTråderOmvendtInorden(p);
      }
    }
  }

Oppgave 3

  private void trekkTrådPreorden(Node<T> p, Node<T> tråd)
  {
    Node q = p.venstre;
    while (q.høyre != null || q.venstre != null)
      if (q.høyre != null) q = q.høyre;
    else q = q.venstre;

    while (true)
      if (q.høyre != null) q = q.høyre;
      else if (q.venstre != null) q = q.venstre;
      else break;

    q.høyre = p.høyre;
    q.venstre = tråd;
  }

  public void preordenMorris(Oppgave<? super T> oppgave)
  {
    if (rot == null) return;
    Node<T> tråd = new Node<>(null);

    Node<T> p = rot, q;

    while (true)
    {
      q = p.venstre;
      if (q != null && q != tråd && p.høyre != null)
         trekkTrådPreorden(p,tråd);

      oppgave.utførOppgave(p.verdi);

      if (q == tråd)   // p-noden har en tråd
      {
        Node r = p; p = p.høyre;     // flytter p
        r.venstre = r.høyre = null;  // kutter tråden
      }
      else if (q != null) p = q;
      else if (p.høyre != null) p = p.høyre;
      else return;
    }
  }