Oppgave 1

  int n = 3;
  int antall = 100, sum = 0;

  for (int i = 0; i < antall; i++)
  {
    BinTre<Object> tre = BinTre.random(n);
    sum += tre.høyde();
  }

  double høyde = (double)sum/antall;

  System.out.println("Gjennomsnittlig høyde: " + høyde);

Oppgave 2

  BinTre<Integer> tre = BinTre.random(10);

  int[] pos = tre.nodeposisjonerNivåorden();

  System.out.println(Arrays.toString(pos));

Oppgave 3

Hvis det er nodeposisjoner som er for store for talltypen int, vil vi få gale svar her.

  private static <T> Node<T> random(int v, int n, Random r, int[] p, int nr)
  {
    if (n == 0) return null;

    p[v] = nr;

    if (n == 1) return new Node<>(null);

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

    Node<T> venstre = random(v + 1, k, r, p, 2*nr);
    Node<T> høyre = random(v + k + 1, n - k - 1, r, p, 2*nr+1);

    return new Node<>(null,venstre,høyre);
  }

  public static <T> BinTre<T> random(int[] posisjoner)
  {
    int n = posisjoner.length;

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

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

    return tre;
  } 

Oppgave 4

  private static <T> Node<T> inrandom(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]);     // tre med en node

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

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

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

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

Oppgave 5

  private static <T> Node<T> postrandom(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]);     // tre med en node

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

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

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

  public static <T> BinTre<T> postrandom(T[] a)
  {
    BinTre<T> tre = new BinTre<>();
    tre.antall = a.length;
    tre.rot = postrandom(a.length-1, a.length, a, new Random());
    return tre;
  }  

Oppgave 6

  public static <T> BinTre<T> nivårandom(T[] a)
  {
    BinTre<T> tre = BinTre.random(a.length);

    if (a.length > 0)
    {
      Kø<Node<T>> kø = new TabellKø<>();
      kø.leggInn(tre.rot);

      for (int i = 0; i < a.length; i++)
      {
        Node<T> p = kø.taUt();
        p.verdi = a[i];
        if (p.venstre != null) kø.leggInn(p.venstre);
        if (p.høyre != null) kø.leggInn(p.høyre);
      }
    }
    return tre;
  } 

Oppgave 7

  BinTre<Integer> tre = BinTre.random(100000);  // tilfeldig binærtre
  System.out.println("Treets høyde: " + tre.høyde());

  class IngenOppgave implements Oppgave<Integer>  // en lokal klasse
  {
    public void utførOppgave(Integer s) {}        // ingenting utføres
  }

  IngenOppgave oppgave = new IngenOppgave();

  long t = System.currentTimeMillis();
  for (int i = 0; i < 1000; i++) tre.preorden(oppgave);
  System.out.println("Tid: " + (System.currentTimeMillis() - t));