Løsningsforslag - oppgaver i Avsnitt 5.1.6


Oppgave 1

Det første treet: D I H L O B A E N G K M J F C
Det andre treet: E I B G A H K L O D N M C J F

Oppgave 2

Det første treet: O G B K R E L I A N H J D P C Q M F
Det andre treet: 10 3 7 13 2 1 5 15 19 10 10 8 5 6 9 11

Oppgave 4

  BinTre<Character> tre = new BinTre<>();             // et tomt tre

  int[] p = {1,2,3,4,5,6,7,10,11,13,14,22,23,28,29};  // posisjoner i nivåorden
  String v = "EIBGAHKLODNMCJF";                       // verdier i nivåorden
  for (int i = 0; i < p.length; i++) tre.leggInn(p[i],v.charAt(i));

  StringJoiner s = new StringJoiner(", ", "[", "]");

  tre.nivåorden(c -> s.add(c.toString()));

  String verdier = s.toString();
  System.out.println(verdier);

Oppgave 5

Her må det være { foran if-setningen og } etter. Setningen må også avsluttes med semikolon.

  tre.nivåorden(c -> { if (c > 'D') s.add(c.toString()); } );

Det kan også settes opp slik. Da blir det litt mer generelt:

  char d = 'D';
  tre.nivåorden(c -> { if (c > d) s.add(c.toString()); } );

Oppgave 6

  public void nivåorden(Consumer<? super T> oppgave)    // ny versjon
  {
    if (tom()) return;  // tomt tre

    Kø<Node<T>> kø = new TabellKø<>();   // Se Avsnitt 4.2.3
    kø.leggInn(rot);

    while (!kø.tom())
    {
      Node<T> p = kø.taUt();
      oppgave.accept(p.verdi);   // den generiske oppgaven

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

Oppgave 7

Flg. metode må inn i Oppgave:

  public static <T> Oppgave<T> konsollutskrift(String format)
  {
    return t -> System.out.printf(format, t);
  }

En anvendelse av konsollutskrift(String format):

  public static void main(String... args)
  {
    BinTre<Character> tre = new BinTre<>();             // et tomt tre

    int[] p = {1,2,3,4,5,6,7,10,11,13,14,22,23,28,29};  // posisjoner i nivåorden
    String v = "EIBGAHKLODNMCJF";                       // verdier i nivåorden

    for (int i = 0; i < p.length; i++) tre.leggInn(p[i],v.charAt(i));

    tre.nivåorden(Oppgave.konsollutskrift("%-3c"));
    System.out.println();
    tre.nivåorden(Oppgave.konsollutskrift().ogSå(c -> System.out.print(' ')));
  }

Oppgave 8

Bruk f.eks. flg. kode:

  char[] d = {(char)0};  // (char)0 er minste mulige tegn
  tre.nivåorden(c -> { if (c > d[0]) d[0] = c;});
  System.out.println(d[0]);

Oppgave 9

Klassen ToString<T> som generisk klasse:

  public class ToString<T> implements Oppgave<T>
  {
    private final StringBuilder s = new StringBuilder("[");

    @Override
    public void utførOppgave(T t)
    {
      s.append(t).append(',').append(' ');
    }

    @Override
    public String toString()
    {
      int n = s.length();
      if (n == 1) s.append(']'); // tom mengde
      else s.replace(n - 2, n, "]");

      return s.toString();
    }

  } // ToString<T>

Et eksempel på bruk av klassen ToString<T>:

  public static void main(String... args)
  {
    BinTre<Integer> tre = new BinTre<>();

    int[] a = Tabell.randPerm(10);
    for (int i = 0; i < a.length; i++)
    {
      tre.leggInn(i + 1, a[i]);  // legger inn i nivåorden
    }

    ToString<Integer> oppgave = new ToString<>();  // en Oppgave
    tre.nivåorden(oppgave);
    System.out.println(oppgave);
  }

Klassen ToString som konkret klasse:

public class ToString implements Oppgave<Object>
{
  private final StringBuilder s = new StringBuilder("[");

  @Override
  public void utførOppgave(Object t)
  {
    s.append(t).append(',').append(' ');
  }

  @Override
  public String toString()
  {
    int n = s.length();
    if (n == 1) s.append(']'); // tom mengde
    else s.replace(n - 2, n, "]");

    return s.toString();
  }

} // ToString

En instans av den konkrete ToString-klassen opprettes slik:

  ToString oppgave = new ToString();  // en Oppgave

Oppgave 10

Flg. kode bruker treet i Figur 5.1.1 a):

  BinTre<Character> tre = new BinTre<>();    //et tomt tre

  int[] p = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,17,18,19,21,23,26,27,29};
  for (int i = 0; i < p.length; i++) tre.leggInn(p[i],(char)('A' + i));

  int[] nivåer = tre.nivåer();

  System.out.println(Arrays.toString(nivåer));
  System.out.println("Treets bredde: " + nivåer[Tabell.maks(nivåer)]);
  System.out.println("Treets høyde: " + (nivåer.length - 1));

  // Utskrift:
  // [1, 2, 4, 7, 8]
  // Treets bredde: 8
  // Treets høyde: 4