Oppgave 3

Bruk char[] verdi = "HBKADIOCFJMEGLN".toCharArray();

Oppgave 6

  private static <T> boolean inneholder(Node<T> p, T verdi)
  {
    if (p == null) return false;  // kan ikke ligge i et tomt tre
    return (verdi == null && p.verdi == null) ||
            (verdi != null && verdi.equals(p.verdi))
           || inneholder(p.venstre,verdi)
           || inneholder(p.høyre,verdi);
  }

  public boolean inneholder(T verdi)
  {
    return inneholder(rot,verdi); // kaller den private metoden
  }

Oppgave 7

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

    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
    }

    public InordenIterator()  // konstruktør
    {
      if (rot == null)
        return;         // treet er tomt
      s.leggInn(null);                 // legger null på bunnen av stakken
      p = først(rot);                  // bruker hjelpemetoden
    }

    public T next()
    {
      T verdi = p.verdi;               // tar vare på verdien i noden p

      if (p.høyre != null)
        p = først(p.høyre);  // p har høyre subtre
      else
        p = s.taUt();                        // p har ikke høyre subtre

      return verdi;                    // returnerer verdien
    }

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

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

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

Oppgave 8

  public T oppdater(int indeks, T nyverdi)
  {
    if (indeks < 0 || indeks >= antall)
       throw new IndexOutOfBoundsException("Ulovlig indeks!");

    Node<T> p = hentNode(indeks);
    T gammelverdi = p.verdi;
    p.verdi = nyverdi;

    return gammelverdi;
  }

Oppgave 9

  public T fjern(int indeks)
  {
    if (indeks < 0 || indeks >= antall)
      throw new IndexOutOfBoundsException("Ulovlig indeks!");

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

    while (true)
    {
      if (indeks < p.vantall)
      {
        q = p;
        p.vantall--;
        p = p.venstre;
      }
      else if (indeks > p.vantall)
      {
        q = p;
        indeks -= (p.vantall + 1);
        p = p.høyre;
      }
      else break;
    }

    T temp = p.verdi;

    if (p.venstre == null)
    {
      if (p == rot) rot = p.høyre;
      else if (p == q.høyre) q.høyre = p.høyre;
      else q.venstre = p.høyre;
    }
    else if (p.høyre == null)
    {
      if (p == rot) rot = p.venstre;
      else if (p == q.venstre) q.venstre = p.venstre;
      else q.høyre = p.venstre;
    }
    else  // p.venstre != null og p.høyre != null
    {
      p.vantall--;
      q = p;
      Node<T> r = p.venstre;
      while (r.høyre != null)
      {
        q = r;
        r = r.høyre;
      }
      p.verdi = r.verdi;
      if (r == p.venstre) p.venstre = r.venstre;
      else q.høyre = r.venstre;
    }

    antall--;
    return temp;
  }

Oppgave 10

  // rekursiv versjon
  private int indeksTil(Node<T> p, T verdi, int k)
  {
    if (p == null) return -1;
    int indeks = indeksTil(p.venstre, verdi, k);
    if (indeks >= 0) return indeks;
    if ((verdi != null && verdi.equals(p.verdi)) ||
        (verdi == null && p.verdi == null)) return k + p.vantall;
    return indeksTil(p.høyre,verdi,k+p.vantall+1);
  }

  public int indeksTil(T verdi)
  {
    return indeksTil(rot,verdi,0);
  }

  // iterativ versjon
  public int indeksTil(T verdi)
  {
    if (rot == null) return -1;      // tomt tre

    Stakk<Node<T>> s = new TabellStakk<>();
    s.leggInn(null);    // legger null på bunnen av stakken

    int indeks = 0;

    Node<T> p = rot;   // starter i roten og går til venstre
    for ( ; p.venstre != null; p = p.venstre) s.leggInn(p);

    while (p != null)
    {
      if ((verdi != null && verdi.equals(p.verdi)) ||
        (verdi == null && p.verdi == null)) return indeks;

      indeks++;

      if (p.høyre != null)          // til venstre i høyre subtre
      {
        for (p = p.høyre; p.venstre != null; p = p.venstre)
          s.leggInn(p);
      }
      else p = s.taUt();  // p.høyre == null, henter fra stakken
    }
    return -1;
  }

Oppgave 11

  public boolean fjern(T verdi)
  {
    int indeks = indeksTil(verdi);
    if (indeks == -1) return false;
    fjern(indeks);
    return true;
  }

Oppgave 12

  public void nullstill()
  {
    if (rot != null) nullstill(rot);
    rot = null;
    antall = 0;
  }

  private void nullstill(Node<T> p)
  {
    if (p.venstre != null) nullstill(p.venstre);
    if (p.høyre != null) nullstill(p.høyre);

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

Oppgave 13

Se Programkode 5.1.7 f).