Oppgave 1

  public void postorden(Oppgave<? super T> oppgave)
  {
    if (tom()) return;  // tomt tre

    Node<T> p = rot;

    while (true) // flytter p til den første i postorden
    {
      if (p.venstre != null) p = p.venstre;
      else if (p.høyre != null) p = p.høyre;
      else break;
    }

    oppgave.utførOppgave(p.verdi);

    while (true)
    {
      if (p == rot) break;  // den siste i postorden

      Node<T> f = p.forelder;
      if (f.høyre == null || p == f.høyre) p = f;
      else
      {
        p = f.høyre;
        while (true)
        {
          if (p.venstre != null) p = p.venstre;
          else if (p.høyre != null) p = p.høyre;
          else break;
        }
      }
      oppgave.utførOppgave(p.verdi);
    }
  }

Oppgave 2

  public void omvendtInorden(Oppgave<? super T> oppgave)
  {
    if (tom()) return;  // tomt tre

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

    while (true)
    {
      oppgave.utførOppgave(p.verdi);

      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;
      }
    }
  }

Oppgave 3

Husk at omvendt preorden er det samme som speilvendt postorden. Dermed kan vi lage metoden omvendtPreorden ved å ta utgangspunkt i koden til metoden postorden og der bytte om venstre og høyre:

  public void omvendtPreorden(Oppgave<? super T> oppgave)
  {
    if (tom()) return;  // tomt tre

    Node<T> p = rot;

    while (true) // flytter p til den siste i postorden
    {
      if (p.høyre != null) p = p.høyre;
      else if (p.venstre != null) p = p.venstre;
      else break;
    }

    oppgave.utførOppgave(p.verdi);

    while (true)
    {
      if (p == rot) break;  // den siste i postorden

      Node<T> f = p.forelder;
      if (f.venstre == null || p == f.venstre) p = f;
      else
      {
        for (p = f.venstre; true; )
        {
          if (p.høyre != null) p = p.høyre;
          else if (p.venstre != null) p = p.venstre;
          else break;
        }
      }
      oppgave.utførOppgave(p.verdi);
    }
  }

Oppgave 4

Husk at omvendt postorden er det samme som speilvendt preorden. Dermed kan vi lage metoden omvendtPostorden ved å ta utgangspunkt i koden til metoden preorden og der bytte om venstre og høyre:

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

    Node<T> p = rot;
    while (true)
    {
      oppgave.utførOppgave(p.verdi);

      if (p.høyre != null) p = p.høyre;
      else if (p.venstre != null) p = p.venstre;
      else
      {
        Node<T> f = p.forelder;   // vi må oppover i treet
        while (f != null && (f.høyre != p || f.venstre == null))
        {
          p = f;
          f = f.forelder;
        }
        if (f == null) return;
        else p = f.venstre;
      }
    }
  }

Oppgave 5

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

    public InordenIterator()  // konstruktør
    {
      if (rot != null) p = førsteInorden(rot);
    }

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

      T verdi = p.verdi;
      p = nesteInorden(p);
      return verdi;
    }

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

    public void remove()
    {
      throw new UnsupportedOperationException();
    }

  } // InordenIterator

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

Oppgave 6

  private class PreordenIterator implements Iterator<T>
  {
    private Node<T> p = null;

    public PreordenIterator()  // konstruktør
    {
      p = rot;
    }

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

      T verdi = p.verdi;

      if (p.venstre != null) p = p.venstre;
      else if (p.høyre != null) p = p.høyre;
      else
      {
        Node<T> f = p.forelder;   // vi må oppover i treet
        while (f != null && (f.venstre != p || f.høyre == null))
        {
          p = f;
          f = f.forelder;
        }
        p = f == null ? null : f.høyre;
      }

      return verdi;
    }

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

    public void remove()
    {
      throw new UnsupportedOperationException();
    }

  } // PreordenIterator

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

Oppgave 7

  private class PostordenIterator implements Iterator<T>
  {
    private Node<T> p = null;

    public PostordenIterator()  // konstruktør
    {
      if (rot == null) return;

      p = rot;

      // finner den første i postorden
      while (true)
        if (p.venstre != null) p = p.venstre;
        else if (p.høyre != null) p = p.høyre;
        else break;
    }

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

      T verdi = p.verdi;

      if (p == rot) p = null;
      else
      {
        Node<T> f = p.forelder;
        if (f.høyre == null || p == f.høyre) p = f;
        else
        {
          for (p = f.høyre; true; )
          {
            if (p.venstre != null) p = p.venstre;
            else if (p.høyre != null) p = p.høyre;
            else break;
          }
        }
      }
      return verdi;
    }

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

    public void remove()
    {
      throw new UnsupportedOperationException();
    }

  } // PostordenIterator

  public Iterator<T> postiterator()
  {
    return new PostordenIterator();
  }

Oppgave 8

  private class OmvendtInordenIterator implements Iterator<T>
  {
    private Node<T> p = null;

    public OmvendtInordenIterator()  // konstruktør
    {
      if (rot == null) return;

      p = rot;
      while (p.høyre != null) p = p.høyre;

    }

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

      T verdi = p.verdi;

      if (p.venstre != null)  // p har høyre barn
      {
        p = p.venstre;
        while (p.høyre != null) p = p.høyre;
      }
      else  // må gå oppover i treet
      {
        while (p.forelder != null && p.forelder.venstre == p)
        {
          p = p.forelder;
        }

        p = p.forelder;
      }
      return verdi;
    }

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

    public void remove()
    {
      throw new UnsupportedOperationException();
    }

  } // OmvendtInordenIterator

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

Oppgave 9

OBS: Denne metoden kan gi gale resultater hvis treet har nodeposisjoner som er for store for datatypen int. En mulighet er å gå over til long.

  public int[] nodeposisjoner()
  {
    int[] a = new int[antall];

    if (rot == null) return a;

    Node<T> p = rot;          // roten er første i preorden
    int k = 1, i = 0;

    while (true)
    {
      a[i++] = k;

      if (p.venstre != null)
      {
        p = p.venstre;
        k <<= 1;  // k = 2*k
      }
      else if (p.høyre != null)
      {
        p = p.høyre;
        k <<= 1; k |= 1;  // k = 2*k + 1
      }
      else
      {
        Node<T> f = p.forelder;   // vi må oppover i treet
        while (f != null && (f.venstre != p || f.høyre == null))
        {
          p = f;
          f = f.forelder;
          k >>= 1;  // k = k / 2;
        }
        if (f == null)
          return a;
        else
        {
          p = f.høyre;
          k |= 1;  // k = k + 1
        }
      }
    }
  }

Oppgave 10

  public Object[] tilTabell()
  {
    Object[] a = new Object[antall];
    if (tom()) return a;

    int i = 0;
    Node<T> p = rot;

    while (true)
    {
      a[i++] = p.verdi;

      if (p.venstre != null) p = p.venstre;
      else if (p.høyre != null) p = p.høyre;
      else
      {
        Node<T> f = p.forelder;   // vi må oppover i treet
        while (f != null && (f.venstre != p || f.høyre == null))
        {
          p = f;
          f = f.forelder;
        }
        if (f == null) return a;
        else p = f.høyre;
      }
    }
  }

Oppgave 11

  private static <T> Node<T> random(int n, Random r)
  {
    if (n == 0) return null;                      // et tomt tre
    else if (n == 1) return new Node<>(null,null);     // tre med en node

    int k = r.nextInt(n);    // k velges tilfeldig fra [0,n>

    Node<T> v = random(k,r);       // et tilfeldig tre med k noder
    Node<T> h = random(n-k-1,r);   // et tilfeldig tre med n-k-1 noder

    Node<T> p = new Node<>(null,v,h,null);

    if (v != null) v.forelder = p;
    if (h != null) h.forelder = p;

    return p;
  }

  public static <T> FBinTre<T> random(int n)
  {
    if (n < 0) throw new IllegalArgumentException("Må ha n >= 0!");

    FBinTre<T> tre = new FBinTre<>();
    tre.antall = n;

    tre.rot = random(n,new Random());   // kaller den private metoden

    return tre;
  }

  private static <T> Node<T> prerandom(int v, int n, T[] a, Random r)
  {
    if (n == 0) return null;                      // et tomt tre
    else if (n == 1) return new Node<>(a[v],null);     // tre med en node

    int k = r.nextInt(n);  // k velges tilfeldig fra [0,n>

    Node<T> venstre = prerandom(v + 1, k, a, r);
    Node<T> høyre = prerandom(v + k + 1, n - k - 1, a, r);

    Node<T> p = new Node<>(a[v], venstre, høyre, null);

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

    return p;
  }

  public static <T> FBinTre<T> prerandom(T[] a)
  {
    FBinTre<T> tre = new FBinTre<>();
    tre.antall = a.length;
    tre.rot = prerandom(0, a.length ,a ,new Random());
    return tre;
  }