Oppgave 2

  for (Iterator<Character> i = tre.iterator(); i.hasNext(); )
    System.out.print(i.next() + " ");

  // Utskrift: H D I B J E A F C G

Oppgave 3

  int antall = 0;
  for (char c : tre) antall++;
  System.out.println(antall);

Oppgave 4

Kjør flg. kode. Hva skjer?

  int[] p = {1,2,3,4,5,6,7,8,9,10};               // nodeposisjoner
  char[] v = "ABCDEFGHIJ".toCharArray();          // nodeverdier

  BinTre<Character> tre = new BinTre<>();         // et tomt binærtre
  for (int i = 0; i < p.length; i++) tre.leggInn(p[i],v[i]);

  Iterator<Character> i = tre.iterator();
  System.out.println(i.next());

  i.remove();

Oppgave 5

  char c = 'F';

  for (Iterator<Character> i = tre.iterator(); i.hasNext(); )
  {
    if (i.next() == c)
    {
      System.out.println("Fant " + c + "!" );
      break;
    }
  }

Oppgave 6

  private class OmvendtInordenIterator implements Iterator<T>
  {
    private final Stakk<Node<T>> s;    // hjelpestakk
    private Node<T> p;                 // hjelpepeker

    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
    {
      s = new TabellStakk<>();
      if (tom()) return;               // treet er tomt
      p = sist(rot);                   // bruker hjelpemetoden
    }

    @Override
    public T next()
    {
      if (!hasNext()) throw new NoSuchElementException();

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

      if (p.venstre != null)           // p har venstre subtre
        p = sist(p.venstre);
      else if (s.tom()) p = null;      // stakken er tom
      else  p = s.taUt();              // tar fra stakken       

      return verdi;                    // returnerer verdien
    }

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

  }  // OmvendtInordenIterator

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

} // class BinTre<T>

Oppgave 7

  private class PreordenIterator implements Iterator<T>
  {
    private final Stakk<Node<T>> s;
    private Node<T> p;

    // konstruktør
    private PreordenIterator()
    {
      s = new TabellStakk<>();
      p = rot;
    }

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

    @Override
    public T next()  // neste er med hensyn på preorden
    {
      if (!hasNext()) throw new NoSuchElementException();

      T verdi = p.verdi;

      if (p.venstre != null)                  // går til venstre
      {
        if (p.høyre != null) s.leggInn(p.høyre);
        p = p.venstre;
      }
      else if (p.høyre != null) p = p.høyre;  // går til høyre
      else if (s.tom()) p = null;             // ingen flere i treet
      else p = s.taUt();                      // tar fra satkken

      return verdi;
    }

  } // PreordenIterator

  public Iterator<T> preIterator()
  {
    return new PreordenIterator();
  }

Oppgave 8

Oppgave 9

  private class NivåordenIterator implements Iterator<T>
  {
    private final Kø<Node<T>> kø;
    private Node<T> p;

    // konstruktør
    private NivåordenIterator()
    {
      kø = new TabellKø<>();
      if (tom()) return;
      p = rot;
    }

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

    @Override
    public T next()  // neste med hensyn på nivåorden
    {
      if (!hasNext()) throw new NoSuchElementException();

      T verdi = p.verdi;

      if (p.venstre != null) kø.leggInn(p.venstre);
      if (p.høyre != null) kø.leggInn(p.høyre);
      p = kø.tom() ? null : kø.taUt();

      return verdi;
    }

  } // NivåordenIterator

  public Iterator<T> nivåIterator()
  {
    return new NivåordenIterator();
  }

Oppgave 10

  private static class InordenIterator<S> implements Iterator<S>
  {
    private final Stakk<Node<S>> s = new TabellStakk<>();
    private Node<S> p = null;

    private Node<S> først(Node<S> 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
    }

    private InordenIterator(Node<S> rot)  // konstruktør
    {
      if (rot == null) return;         // treet er tomt
      p = først(rot);                  // bruker hjelpemetoden
    }

    @Override
    public S next()
    {
      if (!hasNext()) throw new NoSuchElementException("Ingen verdier!");

      S verdi = p.verdi;                        // tar vare på verdien

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

      return verdi;                             // returnerer verdien
    }

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

  } // InordenIterator

  @Override
  public Iterator<T> iterator()     // skal ligge i class BinTre
  {
    return new InordenIterator<>(rot);
  }

Oppgave 11

  public Iterator<T> iterator()
  {
    return new Iterator<T> ()  // en anonym klasse
    {
      private final Stakk<Node<T>> stakk = new TabellStakk<>();
      private Node<T> p = tom() ? null : først(rot);

      private Node<T> først(Node<T> q)
      {
        while (q.venstre != null)
        {
          stakk.leggInn(q);
          q = q.venstre;
        }
        return q;
      }

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

      @Override
      public T next()
      {
        if (!hasNext()) throw
          new NoSuchElementException("Tomt eller ingen flere igjen!");

        T verdi = p.verdi;

        if (p.høyre != null) p = først(p.høyre);
        else if (stakk.tom()) p = null;
        else p = stakk.taUt();

        return verdi;
      }
    };
  }

Oppgave 12

import java.util.*;

public class BinTre<T> implements Iterable<T>
{
  private static final class Node<T> // en indre nodeklasse
  {
    private T verdi;            // nodens verdi
    private Node<T> venstre;    // peker til venstre barn/subtre
    private Node<T> høyre;      // peker til høyre barn/subtre

    private Node(T verdi, Node<T> v, Node<T> h) // konstruktør
    {
      this.verdi = verdi;
      venstre = v;
      høyre = h;
    }

    private Node(T verdi)  // konstruktør
    {
      this.verdi = verdi;
    }
  } // class Node<T>

  private Node<T> rot;            // peker til rotnoden
  private int antall;             // antall noder i treet
  private int endringer;    // antall endringer i treet

  private Node<T> finnNode(int k)    // finner noden i posisjon k
  {
    if (k < 1) return null;

    Node<T> p = rot;                         // hjelpepeker
    int n = Integer.highestOneBit(k >> 1);   // n = 100...00

    for (; p != null && n > 0; n >>= 1)
      p = (k & n) == 0 ? p.venstre : p.høyre;

    return p;   // p blir null hvis k ikke er i treet
  }

  public BinTre() // konstruktør
  {
    rot = null;
    antall = 0;
    endringer = 0;
  }

  public BinTre(int[] p, T[] v) // konstruktør
  {
    if (p.length > v.length) throw new
      IllegalArgumentException("Tabell v har for få verdier");

    for (int i = 0; i < p.length; i++) leggInn(p[i],v[i]);
  }

  public int antall()
  {
    return antall;  // returnerer antallet
  }

  public boolean tom()
  {
    return antall == 0;  // tomt tre?
  }

  public final void leggInn(int k, T verdi)
  {
    if (k < 1) throw new
      IllegalArgumentException("Posisjonstallet k(" + k + ") < 1!");

    Node<T> p = rot, q = null;               // hjelpepekere

    int n = Integer.highestOneBit(k >> 1);   // n = 100...00

    while (p != null && n > 0)
    {
      q = p;
      p = (n & k) == 0 ? p.venstre : p.høyre;
      n >>= 1;  // bitforskyver n
    }

    if (n > 0) throw new
      IllegalArgumentException("Posisjonen k(" + k + ") er for stor!");
    else if (p != null) throw new
      IllegalArgumentException("Posisjonen k(" + k + ") finnes fra før!");

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

    if (q == null) rot = p;   // tomt tre - ny rot
    else if ((k & 1) == 0)    // sjekker siste siffer i k
      q.venstre = p;
    else
      q.høyre = p;

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

  public boolean finnes(int k)
  {
    return finnNode(k) != null;
  }

  public T hent(int k)
  {
    Node<T> p = finnNode(k);

    if (p == null) throw new
      IllegalArgumentException("Posisjon k(" + k + ") er ukjent!");

    return p.verdi;
  }

  public T oppdater(int k, T nyverdi)
  {
    Node<T> p = finnNode(k);

    if (p == null) throw new
      IllegalArgumentException("Posisjon k(" + k + ") er ukjent!");

    T gammelverdi = p.verdi;  // tar vare på gammel verdi
    p.verdi = nyverdi;        // oppdaterer
    endringer++;        // en endring
    return gammelverdi;       // returnerer gammel verdi
  }

  public T fjern(int k)  // k må representere en bladnode
  {
    if (k < 1) throw new
      IllegalArgumentException("Posisjon k(" + k + ") < 1!");

    Node<T> p = rot, q = null;               // hjelpepekere
    int n = Integer.highestOneBit(k >> 1);   // binært siffer

    while (p != null && n > 0)
    {
      q = p;
      p = (n & k) == 0 ? p.venstre : p.høyre;
      n >>= 1;
    }

    if (p == null) throw new
      IllegalArgumentException("Posisjon k(" + k + ") er utenfor treet!");

    if (p.venstre != null || p.høyre != null) throw new
      IllegalArgumentException("Posisjon k(" + k + ") er ingen bladnode!");

    if (p == rot) rot = null;
    else if (p == q.venstre) q.venstre = null;
    else q.høyre = null;

    antall--;           // en verdi mindre
    endringer++;  // en endring
    return p.verdi;
  }

  private class InordenIterator implements Iterator<T>
  {
    private Stakk<Node<T>> s;
    private Node<T> p;
    private int 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
    }

    private InordenIterator()          // konstruktør
    {
      s = new TabellStakk<>();         // en hjelpestakk
      p = null;
      if (tom()) return;               // treet er tomt
      p = først(rot);                  // bruker hjelpemetoden
      iteratorendringer = endringer;
    }

    @Override
    public T next()
    {
      if (!hasNext()) throw new NoSuchElementException("Ingen verdier!");

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

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

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

      return verdi;                             // returnerer verdien
    }

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

  @Override
  public Iterator<T> iterator()     // skal ligge i class BinTre
  {
    return new InordenIterator();
  }

} // class BinTre<T>