Oppgave 1

  1, 3, 7
  1, 3, 6, 12
  1, 3, 6, 10, 14
  1, 3, 6, 10, 18
  1, 5, 8, 10
  1, 5, 11, 15, 15
  1, 5, 11, 15, 20

Oppgave 2

  12, 10, 8, 5
  12, 10, 8, 6
  12, 10, 7, 4
  12, 10, 7, 5
  12, 11, 9, 3
  12, 11, 9, 5
  12, 11, 8, 7

Oppgave 3

  1, 3, 6, 10, 14

Oppgave 4

  12, 11, 9, 5

Oppgave 6

  public boolean erMakstre(Comparator<? super T> c) // legges i BinTre
  {
    if (rot == null) return true;    // et tomt tre er et maksimumstre
    else return erMakstre(rot,c);    // kaller den private hjelpemetoden
  }

  private static <T> boolean erMakstre(Node<T> p, Comparator<? super T> c)
  {
    if (p.venstre != null)
    {
      if (c.compare(p.venstre.verdi,p.verdi) > 0) return false;
      if (!erMakstre(p.venstre,c)) return false;
    }
    if (p.høyre != null)
    {
      if (c.compare(p.høyre.verdi,p.verdi) > 0) return false;
      if (!erMakstre(p.høyre,c)) return false;
    }
    return true;
  }

Oppgave 7

  public boolean erMintre(Comparator<? super T> c)
  {
    if (rot == null) return true;  // et tomt tre er et mintre
    Kø<Node<T>> kø = new TabellKø<>();
    kø.leggInn(rot);

    while (!kø.tom())
    {
      Node<T> p = kø.taUt();
      if (p.venstre != null)
      {
        if (c.compare(p.venstre.verdi,p.verdi) < 0) return false;
        kø.leggInn(p.venstre);
      }
      if (p.høyre != null)
      {
        if (c.compare(p.høyre.verdi,p.verdi) < 0) return false;
        kø.leggInn(p.høyre);
      }
    }
    return true;
  }

Oppgave 8

  public String minimumsGrenen(Comparator<? super T> c)
  {
    StringJoiner s = new StringJoiner(", ", "[", "]");

    Node<T> p = rot;
    while (p != null)
    {
      s.add(p.verdi.toString());
      if (p.høyre == null)
        p = p.venstre;       // har ikke høyre barn
      else if (p.venstre == null)
        p = p.høyre;        // har ikke venstre barn
      else
      {
        int cmp = c.compare(p.venstre.verdi, p.høyre.verdi);
        p = cmp <= 0 ? p.venstre : p.høyre;
      }
    }
    return s.toString();
  }

Oppgave 9

Vi traverserer treet i preorden. Under traverseringen bruker vi en toveiskø til å holde rede på hvilke verdier som befinner seg på veien fra roten og ned til den noden vi er på. Fordelen med en toveiskø er at den har metoder som både legger inn og tar ut bakerst. Når vi kommer til en bladnode, kaller vi toveiskøens toString-metode og legger tegnstrengen over i en liste. To grener kan være like bortsett fra den siste verdien. Når vi kaller toveiskøens toString-metode vil likevel hele tegnstrengen bli konstruert på nytt. Dette kan unngås. Se versjon 2) av metoden lenger ned.

  // 1. versjon

  public String[] grener()
  {
    Liste<String> liste = new TabellListe<>();  // en liste
    Toveiskø<T> kø = new TabellToveiskø<>();    // en toveiskø
    if (!tom()) grener(rot, liste, kø);         // kaller rekursjonen

    String[] grener =
      new String[liste.antall()];           // oppretter tabell

    int i = 0;
    for (String gren : liste)
      grener[i++] = gren;                   // fra liste til tabell

    return grener;                          // returnerer tabellen
  }

  private void grener(Node<T> p, Liste<String> liste, Toveiskø<T> kø)
  {
    if (p.høyre == null && p.venstre == null)  // bladnode
    {
      kø.leggInnSist(p.verdi);        // legger inn bakerst
      liste.leggInn(kø.toString());   // gjør om til tegnstreng
      kø.taUtSist();                  // tar ut bakerst
    }
    else
    {
      kø.leggInnSist(p.verdi);        // legger inn bakerst

      if (p.venstre != null) grener(p.venstre, liste, kø);
      if (p.høyre != null) grener(p.høyre, liste, kø);

      kø.taUtSist();                  // tar ut bakerst
    }
  } 

Her bruker vi en StringBuilder istedenfor en toveiskø. Når vi skal fjerne siste innlegging i en StringBuilder, må vi vite lengden av verdien som sist ble lagt inn. Det er det mulig å finne:

  // 2. versjon - dobbelt så effektiv som 1. versjon

  public String[] grener()
  {
    Liste<String> liste = new TabellListe<>();
    StringBuilder s = new StringBuilder("[");
    if (!tom()) grener(rot, liste, s);

    String[] grener =
      new String[liste.antall()];           // oppretter tabell

    int i = 0;
    for (String gren : liste)
      grener[i++] = gren;                   // fra liste til tabell

    return grener;                          // returnerer tabellen
  }

  private void grener(Node<T> p, Liste<String> liste, StringBuilder s)
  {
    T verdi = p.verdi;
    int k = verdi.toString().length(); // lengden på verdi

    if (p.høyre == null && p.venstre == null)  // bladnode
    {
      liste.leggInn(s.append(verdi).append(']').toString());

      // må fjerne det som ble lagt inn sist - dvs. k + 1 tegn
      s.delete(s.length() - k - 1, s.length());
    }
    else
    {
      s.append(p.verdi).append(',').append(' ');  // legger inn k + 2 tegn
      if (p.venstre != null) grener(p.venstre, liste, s);
      if (p.høyre != null) grener(p.høyre, liste, s);
      s.delete(s.length() - k - 2, s.length());   // fjerner k + 2 tegn
    }
  }