Oppgave 1

7, 4, 9, 2, 6, 8, 10, 1, 3, 5

13, 8, 17, 4, 11, 15, 19, 2, 6, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9

Oppgave 2

  public static <T> BinTre<T> komplettInorden(T[] a)
  {
    BinTre<T> tre = new BinTre<>();
    if (a.length == 0) return tre;   // returnerer et tomt tre

    tre.antall = a.length;

    tre.rot = komplett(a.length,1);  // kaller metoden som lager treet

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

    int i = 0;  // tellevariabel for tabellen

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

    while (p != null)
    {
      p.verdi = a[i++];        // legger inn a[i] og øker i

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

  public static void main(String[] args)
  {
    Integer[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    BinTre<Integer> tre = BinTre.komplettInorden(a);

    tre.traverserInorden(new KonsollUtskrift<>());

    // Utskrift: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
  }

Oppgave 3

Antall noder n	n − k/2	k − 1	Venstre subtre
18	10	15	10
19	11	15	11
20	12	15	12
21	13	15	13
22	14	15	14
23	15	15	15
24	16	15	15
25	17	15	15
26	18	15	15

Oppgave 4

I et komplett binærtre med 20 noder vil rotnodens høyre subtre være perfekt. Hvis treet har 23 noder, vil begge subtrærne være perfekte. Hvis treet har 25 noder, vil venstre subtre være perfekt.

Oppgave 5

  private static <T> Node<T> komplett(T[] a, int v, int h)
  {
    if (v > h) return null;             // tomt intervall

    int n = h - v + 1;                  // antallet i intervallet
    int k = Integer.highestOneBit(n);   // stripper n

    int m = n - (k >> 1);               // k >> 1 svarer til k/2

    Node<T> venstre, høyre;

    if (m < k)
    {
      m += v;
      venstre = komplett(a, v, m - 1);   // venstre subtre
      høyre = balansert(a, m + 1, h);    // høyre subtre
    }
    else
    {
      m = k - 1 + v;
      venstre = balansert(a, v, m - 1);  // venstre subtre
      høyre   = komplett(a, m + 1, h);   // høyre subtre
    }

    return new Node<>(a[m], venstre, høyre);
  }