Oppgave 2

  Character[] a = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'};
  SBinTre<Character> tre = SBinTre.balansert(a);

  System.out.println(tre.antall() + "\n" + tre.høyde() + "\n" + tre);

Oppgave 3

  Integer[] a = new Integer[31];
  for (int i = 0; i < 31; i++) a[i] = i + 1;

  SBinTre<Integer> tre = SBinTre.balansert(a);

  System.out.println(tre.antall() + "\n" + tre.høyde() + "\n" + tre);

Oppgave 4

Oppgave 5

Oppgave 6

Oppgave 7

Resultatet blir et ekstremt høyreskjevt tre, dvs. ingen noder har venstre barn.

Oppgave 8

  public boolean erSortertInorden()  // iterativ inorden
  {
    if (antall() < 2) return true;   // er sortert

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

    T denneverdi = p.verdi;
    T nesteverdi = null;

    while (true) // flytter på til neste node
    {

      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 if (!s.tom())
      {
        p = s.taUt();    // p.høyre == null, henter fra stakken
      }
      else break;        // stakken er tom - vi er ferdig

      nesteverdi = p.verdi;

      if (comp.compare(denneverdi,nesteverdi) > 0) return false;

      denneverdi = nesteverdi;

    } // while

    return true;
  }

Oppgave 9

Et binærtre er et binært søketre hvis hvert av subtrærne er binære søketrær, hvis den største verdien i venstre subtre (hvis det er et ikke-tomt venstre subtre) er mindre enn rotverdien og hvis rotverdien er mindre enn eller lik den minste verdien i høyre subtre (hvis det er et ikke-tomt høyre subtre). Spesielt kan vi si at et tomt tre er et binært søketre.

1. versjon er nærmest en direkte oversettelse av beskrivelsen over. For hver node letes det etter største verdi i venstre subtre og minste verdi i høyre subtre vha. løkker. Men algoritmen er likevel av orden n.

  public boolean erSøketre()
  {
    return rot == null ? true : erSøketre(rot,comp);
  }

  private static <T> boolean erSøketre(Node<T> p, Comparator<? super T> c)
  {
    // finner den største i p sitt venstre subtre
    if (p.venstre != null)
    {
      if (erSøketre(p.venstre,c) == false) return false;
      Node<T> r = p.venstre;
      while (r.høyre != null) r = r.høyre;
      if (c.compare(r.verdi,p.verdi) >= 0) return false;
    }
    // finner den minste i p sitt høyre subtre
    if (p.høyre != null)
    {
      if (erSøketre(p.høyre,c) == false) return false;
      Node<T> r = p.høyre;
      while (r.venstre != null) r = r.venstre;
      if (c.compare(r.verdi,p.verdi) < 0) return false;
    }
    return true;
  } 

2. versjon er en liten forbedring av 1. versjon. Vi kan la den private hjelpemetoden erSøketre returnere treets største verdi, dvs. den verdien som ligger lengst ned til høyre. Da trenger vi bare en løkke, dvs. en løkke til å finne minste verdi i et subtre:

  public boolean erSøketre()  // 2. versjon
  {
    if (rot == null) return true;
    return erSøketre(rot,comp) == null ? false : true;
  }

  private static <T> T erSøketre(Node<T> p, Comparator<? super T> c)
  {
    if (p.venstre != null)
    {
      // erSøketre(p.venstre,c) returnerer den største verdien
      // i det venstre subtreet til p
      T v = erSøketre(p.venstre,c);
      if (v == null) return null; // venstre subtre er ikke et søketre

      // verdi v må være mindre enn p.verdi
      if (c.compare(v,p.verdi) >= 0) return null;
    }
    if (p.høyre != null)
    {
      T h = erSøketre(p.høyre,c);
      if (h == null) return null;
      // finner den minste i p sitt høyre subtre
      Node<T> r = p.høyre;
      while (r.venstre != null) r = r.venstre;
      if (c.compare(r.verdi,p.verdi) < 0) return null;
      return h;  // returnerer treets største verdi
    }
    return p.verdi; // hvis p ikke har høyre subtre
  } 

3. versjon: Vi kan la metoden returnere både treets minste og største verdi. Det kan vi få til ved å la returverdien være en T-tabell med med to verdier. Hvis treet ikke er et binært søketre returneres null. Denne metoden er av samme orden som versjon 1 og 2, men skulle teoretisk være litt mer effektiv siden vi ikke lenger har noen løkker som leter etter verdier. Men i praksis er den heller mindre effektiv pga. all den kostbare tabellhåndteringen:

  public boolean erSøketre()  // 3. versjon
  {
    if (rot == null) return true;
    return erSøketre(rot,comp) == null ? false : true;
  }

  private static <T> T[] erSøketre(Node<T> p, Comparator<? super T> c)
  {
    T[] a = (T[])new Object[2];
    // den minste verdien skal ligge i a[0] og den største i a[1]

    if (p.venstre != null)
    {
      T[] v = erSøketre(p.venstre,c);
      if (v == null) return null;
      if (c.compare(v[1],p.verdi) >= 0) return null;
      a[0] = v[0];
    }
    else a[0] = p.verdi;

    if (p.høyre != null)
    {
      T[] h = erSøketre(p.høyre,c);
      if (h == null) return null;
      if (c.compare(h[0],p.verdi) < 0) return null;
      a[1] = h[1];
    }
    else a[1] = p.verdi;
    return a;
  } 

Oppgave 10

Løsningsforslag mangler!