Oppgave 1

  private static <T> void preorden(Node<T> p, Oppgave<? super T> oppgave)
  {
    while (true)
    {
      oppgave.utførOppgave(p.verdi);
      if (p.venstre != null) preorden(p.venstre,oppgave);
      if (p.høyre == null) return;      // metodekallet er ferdig
      p = p.høyre;
    }
  }

Oppgave 4

  private static <T> void inorden(Node<T> p, Oppgave<? super T> oppgave)
  {
    while (true)
    {
      if (p.venstre != null) inorden(p.venstre,oppgave);
      oppgave.utførOppgave(p.verdi);
      if (p.høyre == null) return;      // metodekallet er ferdig
      p = p.høyre;
    }
  }

Oppgave 6

  public void preorden(Oppgave<? super T> oppgave)
  {
    Object[] a = new Object[10];
    int k = 0;
    a[k++] = null;

    Node<T> p = rot;    // starter i roten

    while (p != null)
    {
      oppgave.utførOppgave(p.verdi);

      if (p.venstre != null)
      {
        if (p.høyre != null)
        {
          if (k == a.length) a = Arrays.copyOf(a,2*k);
          a[k++] = p.høyre;
        }
        p = p.venstre;
      }
      else if (p.høyre != null)  // nå er p.venstre lik null
      {
        p = p.høyre;
      }
      else  // nå er både p.venstre og p.høyre lik null
      {
        p = (Node<T>)a[--k];
      }
    }
  }

Oppgave 7

Oppgave 8

Omvendt preorden er lik speilvendt postorden. Vi får iterativ speilvendt postorden ved å bruke den postorden-metoden og der bytte om høyre og venstre. For å øke lesbarheten lager vi en hjelpemetode som finner den siste i postorden i treet som har p som rot:

  private static <T> Node<T> sistPostorden(Node<T> p, Stakk<Node<T>> stakk)
  {
    while (true)
    {
      stakk.leggInn(p);
      if (p.høyre != null) p = p.høyre;
      else if (p.venstre != null) p = p.venstre;
      else return stakk.taUt();
    }
  }

  public void omvendtPreorden(Oppgave<? super T> oppgave)
  {
    if (tom()) return;
    Stakk<Node<T>> stakk = new TabellStakk<>();
    Node<T> p = sistPostorden(rot, stakk);              // hjelpemetoden

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

      if (stakk.tom()) return;                          // ferdig
      Node<T> f = stakk.kikk();                         // f for forelder

      if (f.venstre == null || p == f.venstre)
        p = stakk.taUt();                               // går oppover
      else p = sistPostorden(f.venstre, stakk);         // hjelpemetoden
    }
  }

Omvendt og speilvendt inorden er det samme. Vi får derfor omvendt inorden ved å bytte om høyre og venstre i den iterative inorden-metoden:

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

    Stakk<Node<T>> stakk = new TabellStakk<>();
    Node<T> p = rot;   // starter i roten og går til høyre
    for ( ; p.høyre != null; p = p.høyre) stakk.leggInn(p);

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

      if (p.venstre != null)          // til høyre i venstre subtre
      {
        for (p = p.venstre; p.høyre != null; p = p.høyre)
        {
          stakk.leggInn(p);
        }
      }
      else if (!stakk.tom())
      {
        p = stakk.taUt();   // p.høyre == null, henter fra stakken
      }
      else break;          // stakken er tom - vi er ferdig
    } // while
  }

Omvendt postorden er lik speilvendt preorden. Vi får iterativ speilvendt preorden ved å bruke den iterative preorden-metoden og der bytte om høyre og venstre:

  public void omvendtPostorden(Oppgave<? super T> oppgave)   // ny versjon
  {
    if (tom()) return;

    Stakk<Node<T>> stakk = new TabellStakk<>();
    Node<T> p = rot;    // starter i roten

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

      if (p.høyre != null)
      {
        if (p.venstre != null) stakk.leggInn(p.venstre);
        p = p.høyre;
      }
      else if (p.venstre != null)  // her er p.venstre lik null
      {
        p = p.venstre;
      }
      else if (!stakk.tom())     // her er p en bladnode
      {
        p = stakk.taUt();
      }
      else                       // p er en bladnode og stakken er tom
        break;                   // traverseringen er ferdig
    }
  }

Oppgave 9

  public void inorden(Oppgave<? super T> oppgave)
  {
    if (rot == null) return;    // tomt tre

    Node<T> p = rot;
    long k = 1;

    while (p.venstre != null)   // går til venstre
    {
      k <<= 1;
      p = p.venstre;
    }

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

      if (p.høyre != null)            // til venstre i høyre subtre
      {
        p = p.høyre;
        k <<= 1;
        k |= 1;                       // legger på 1 bakerst
        while (p.venstre != null)     // går til venstre
        {
          k <<= 1;
          p = p.venstre;
        }
      }
      else  // p.høyre == null
      {
        while ((k & 1) != 0) k >>= 1;
        k >>= 1;    // k er nå posisjonen til den neste
        if (k == 0) return;

        p = rot;  // starter i roten og nedover til k
        long n = Long.highestOneBit(k >> 1);
        while (n > 0)
        {
          p = (n & k) == 0 ? p.venstre : p.høyre;
          n >>= 1;  // bitforskyver n
        }
      }
    }
  }

Oppgave 10

  public void preorden(Oppgave<? super T> oppgave)    // iterativ versjon
  {
    if (rot == null) return;

    Node<T> p = rot;
    long k = 1;

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

      if (p.venstre != null)
      {
        p = p.venstre;
        k <<= 1;  // 0 bakerst
      }
      else if (p.høyre != null)
      {
        p = p.høyre;
        k <<= 1;
        k |= 1;  // 1 bakerst
      }
      else
      {
        Node<T> q = null;
        int k1 = 1;
        int k2 = 0;  // posisjonen til neste
        p = rot;
        long n = Long.highestOneBit(k >> 1);

        while (n > 0)
        {
          if ((n & k) == 0)
          {
            k1 <<= 1;  // 0 bakerst
            if (p.høyre != null)
            {
              q = p.høyre;
              k2 = k1 | 1;
            }
            p = p.venstre;
          }
          else
          {
            p = p.høyre;
            k1 <<= 1;
            k1 |= 1;  // 1 bakerst
          }
          n >>= 1;
        }
        if (q == null) return;
        p = q;
        k = k2;  // posisjonen til neste
      }
    }
  }