Løsningsforslag - oppgaver i Avsnitt 5.1.12


Oppgave 1 

  int[] p = {1,2,3,4,5,6,7,8,9,10};  // nodeposisjoner
  char[] v = "ABCDEFGHIJ".toCharArray();  // nodeverdier

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

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

  System.out.println(tre.antall());
  System.out.println(tre.høyde());
  System.out.println(tre.inneholder('H'));
  System.out.println(tre.inneholder('K'));
  System.out.println(tre.posisjon('H'));

Oppgave 2 

  private static int antall(Node<?> p)
  {
    int v = p.venstre == null ? 0 : antall(p.venstre);
    int h = p.høyre == null ? 0 : antall(p.høyre);
    return 1 + v + h;
  }

  public int antall()
  {
    return rot == null ? 0 : antall(rot);
  }

Oppgave 3 

  private static int antall(Node<?> p)
  {
    int antall = 1;
    while (true)
    {
      if (p.venstre != null) antall += antall(p.venstre);
      p = p.høyre;
      if (p == null) return antall;
      antall++;
    }
  }

Oppgave 4 

  private static void antall(Node<?> p, IntObject o)
  {
    o.add(1);
    if (p.venstre != null) antall(p.venstre, o);
    if (p.høyre != null) antall(p.høyre, o);
  }

  public int antall()
  {
    if (rot == null) return 0;
    IntObject o = new IntObject(0);
    antall(rot, o);
    return o.get();
  }

Oppgave 5 

  private static int antallBladnoder(Node<?> p)
  {
    if (p.venstre == null && p.høyre == null) return 1;

    return (p.venstre == null ? 0 : antallBladnoder(p.venstre))
         + (p.høyre == null ? 0 : antallBladnoder(p.høyre));
  }

  public int antallBladnoder()
  {
    return rot == null ? 0 : antallBladnoder(rot);
  }

Oppgave 6 

  public int antallBladnoder()
  {
    if (tom()) return 0;

    Stakk<Node<T>> stakk = new TabellStakk<>();
    Node<T> p = rot;    // starter i roten
    int antallBladnoder = 0;

    while (true)
    {
      if (p.venstre == null && p.høyre == null) antallBladnoder++;

      if (p.venstre != null)
      {
        if (p.høyre != null) stakk.leggInn(p.høyre);
        p = p.venstre;
      }
      else if (p.høyre != null)  // her er p.venstre lik null
      {
        p = p.høyre;
      }
      else if (!stakk.tom())
      {
        p = stakk.taUt();
      }
      else
        break;                   // traverseringen er ferdig
    }

    return antallBladnoder;
  }

Oppgave 7

Vi kan løse det ved f.eks. å traversere i postorden eller i nivåorden. Metoden med nivåorden står lenger ned. I postorden «besøkes» nodene nedenifra og oppover. Vi bruker en stakk som hjelpemiddel. Når vi står på en bladnode, må derfor alle nodene oppover mot roten ligge på stakken. Dybden til en bladnode blir dermed lik antallet på stakken. Den største dybden er lik treets høyde. Bruker en hjelpemetode for å øke lesbarheten. Hjelpemetoden finner den første i postorden mhp. noden p som rotnode: 

  private static <T> Node<T> førstPostorden(Node<T> p, Stakk<Node<T>> stakk)
  {
    while (true)
    {
      stakk.leggInn(p);
      if (p.venstre != null) p = p.venstre;
      else if (p.høyre != null) p = p.høyre;
      else return stakk.taUt();
    }
  }

  public int høyde()  // iterativ versjon
  {
    if (tom()) return -1;  // et tomt tre har høyde -1

    Stakk<Node<T>> stakk = new TabellStakk<>();
    Node<T> p = førstPostorden(rot, stakk);  // p er en bladnode
    int dybde = stakk.antall();              // dybden til p

    while (true)
    {
      if (stakk.tom()) return dybde;  // maks dybde er lik treets høyde
      Node<T> f = stakk.kikk();       // f er forelder til p

      if (f.høyre == null || p == f.høyre) p = stakk.taUt();
      else
      {
        p = førstPostorden(f.høyre, stakk); // bruker hjelpemetoden      
        // sjekker dybden til bladnoden p
        if (stakk.antall() > dybde) dybde = stakk.antall();
      }
    }
  }

I nivåorden kan vi hele tiden vite på hvilket nivå vi er på. Høyden til treet er lik siste nivå. Vi kan bearbeide metoden i Programkode 5.1.6 k): 

  public int høyde()
  {
    if (tom()) return -1;  // et tomt tre har høyde -1

    Kø<Node<T>> kø = new TabellKø<>();  // hjelpekø
    int nivå = 0;                       // hjelpevariabel

    kø.leggInn(rot);    // legger roten i køen

    while (!kø.tom())   // så lenge som køen ikke er tom
    {
      int k = kø.antall();  // antallet på dette nivået

      for (int i = 0; i < k; i++)  // alle på nivået
      {
        Node<T> p = kø.taUt();

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

      nivå++;  // fortsetter på neste nivå
    }

    return nivå - 1;   // -1 pga. nivå++ ovenfor
  }

Oppgave 8

I flg. versjon er det mulig å søke etter eventuelle null-verdier: 

  private static <T> boolean inneholder(Node<T> p, T verdi)
  {
    if (p == null) return false;  // kan ikke ligge i et tomt tre

    return (verdi == null && p.verdi == null)
      || (verdi != null && verdi.equals(p.verdi))
      || inneholder(p.venstre,verdi)
      || inneholder(p.høyre,verdi);
  }

Metoden kan kodes iterativt på mange måter. Vi kan bruke en eller annen iterativ traversering. Bruker her inorden: 

 public boolean inneholder(T verdi)
  {
    if (tom()) return false;      // tomt tre

    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);

    while (true)
    {
      if ((verdi == null && p.verdi == null)
        || (verdi != null && verdi.equals(p.verdi))) return true;

      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()) return false;
      else p = s.taUt();  // p.høyre == null, henter fra stakken
    }
  }

Oppgave 9

Metoden posisjon() skal finne posisjonen til oppgitt verdi. Da kan vi bruke en traversering i postorden. Hvis verdien forekommer flere ganger, er det normalt ikke den av dem som har minst posisjonstall vi finner. Til det kan en å bruke en traversering i nivåorden. Se nedenfor. Når vi i postorden kommer til en node p som inneholder den verdien vi søker etter, så vil alle nodene på veien fra p opp til roten ligge på stakken. Ta forelder f til p. Hvis p er venstre barn til f, så vil siste binære siffer til posisjonstallet til p være 0 og ellers 1. Osv. oppover mot roten. Vi lager en hjelpemetode som konstruerer posisjonstallet ved hjelp av stakken: 

  private static <T> int posisjon(Node<T> p, Stakk<Node<T>> stakk)
  {
    int pos = 0, k = 1;
    while (!stakk.tom())
    {
      Node<T> f = stakk.taUt();     // forelder til p
      if (p == f.høyre) pos |= k;   // legger siffer 1 på plass k
      p = f;                        // forsetter oppover
      k <<= 1;                      // flytter 1-tallet
    }
    return pos | k;                 // siffer 1 aller først
  }

Det er mulig å bygge opp en tegnstreng isteden. Da bruker vi en StringBuilder og bygger opp tegnstrengen motsatt vei. Til slutt konverterer vi fra en tegnstreng til et tall: 

  private static <T> int posisjon(Node<T> p, Stakk<Node<T>> stakk)
  {
    StringBuilder s = new StringBuilder();

    while (!stakk.tom())  // bygger opp posisjonstallet motsatt vei
    {
      Node<T> f = stakk.taUt();
      if (p == f.venstre) s.append("0"); else s.append("1");
      p = f;
    }
    s.append("1");

    return Integer.parseInt(s.reverse().toString(), 2);
  }

Dette settes sammen til flg. metode: 

  public int posisjon(T verdi)
  {
    if (tom()) return -1;
    Stakk<Node<T>> stakk = new TabellStakk<>();
    Node<T> p = førstPostorden(rot, stakk);                   // hjelpemetoden

    while (true)                                              // fortsetter
    {
      if ((verdi == null && p.verdi == null)
        || (verdi != null && verdi.equals(p.verdi)))
      {
        return posisjon(p, stakk);                            // posisjonen til verdi
      }

      if (stakk.tom()) return -1;                             // fant ikke verdi
      Node<T> f = stakk.kikk();                               // f for forelder

      if (f.høyre == null || p == f.høyre) p = stakk.taUt();  // går oppover
      else p = førstPostorden(f.høyre, stakk);                // hjelpemetoden
    }
  }

Oppgave 10

Det er noden lengst til høyre på nederste rad som har størst posisjonstall. 

  public int makspos()
  {
    IntObject o = new IntObject(-1);
    if (!tom()) makspos(rot, 1, o);
    return o.get();
  }

  private static void makspos(Node<?> p, int pos, IntObject o)
  {
    if (pos > o.get()) o.set(pos);
    if (p.venstre != null) makspos(p.venstre, 2*pos, o);
    if (p.høyre != null) makspos(p.høyre, 2*pos + 1, o);
  }

Dette kan også løses iterativt - f.eks. ved en traversering i nivåorden ved hjelp av en kø. En enkel måte å holde orden på posisjonene til nodene er å bruke en hjelpekø: 

  public int makspos()
  {
    if (tom()) return 0;

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

    Kø<Integer> nr = new TabellKø<>();
    nr.leggInn(1);

    int pos = 1;

    while (!kø.tom())
    {
      Node<T> p = kø.taUt(); pos = nr.taUt();

      if (p.venstre != null)
      {
        kø.leggInn(p.venstre); nr.leggInn(2*pos);
      }
      if (p.høyre != null)
      {
        kø.leggInn(p.høyre); nr.leggInn(2*pos + 1);
      }
    }
    return pos;
  }

Oppgave 11

i)

Høyden til et perfekt binærtre med n noder er lik: log2(n + 1) − 1. I et slikt tre er alltid diameteren lik det dobbelte av høyden, dvs. lik: 2·log2(n + 1) − 2. Et slik tre med f.eks. 15 noder, vil ha diameter lik 2·log2(15 + 1) − 2 = 2·4 − 2 = 6.

Høyden til et perfekt binærtre med n noder er lik: ⌈log2(n+1)⌉ – 1. Hvis det er noder på mer enn halvparten av nederste nivå, så vil diameteren være det dobbelte av høyden. Hvis ikke, vil diameteren være lik 2·høyden − 1.

ii)

Diameteren er et mål på hvor «tett» treet er. Har vi n noder, får et tre med minst mulig diameter hvis treet er komplett.

iii)

La p og q være to noder med maksimal innbyrdes avstand. Anta først at de ligger på samme gren. La f.eks. p være den som er nærmest roten og q den av dem som er lengst ned. Hvis p ikke er roten, vil avstand(rot,q) være større enn avstand(p,q). Det er umulig siden den var størst mulig. Altså må p være lik roten. Hvis q ikke er en bladnode, så må q ha et barn. Men da må avstanden mellom det barnet og p være større enn avstand(p,q). Umulig. Altså må q være en bladnode.

Hvis p og q ikke ligger på samme gren, så har de en nærmeste felles forgjenger f. Da er avstand(p,q) lik avstand(p,f) + avstand(q,f). Hvis f.eks. p ikke er bladnode, vil avstanden fra et barn (til p) til q være en mer enn avstand(p,q). Men det er umulig siden avstand(p,q) var maksimal.

Anta at dybden til q er større enn eller lik dybden til p. Hvis q ikke ligger på nederste nivå, må det finnes en node r som ligger dypere enn q. Da kan ikke r ligge på samme gren som q. I så fall hadde avstand(p,r) vært større enn avstand(p,q). La g være næremste felles forgjenger for q og r. Da kan ikke g være lik eller ligge lenger ned enn f. I så fall ville avstand(p,r) = avstand(p,f) + avstand(f,g) + avstand(g,r) vært større enn avstand(p,q). Den kan heller ikke ligge høyre enn f. I så fall ville avstand(r,q) blitt større enn avstand(p,q). Konklusjon: q må ligge på nederste nivå.

Samme type argumentasjon som over, viser at det må finnes et nodepar p og q som har størst avstand der q ligger lengst til høyre på nederste nivå.