Løsningsforslag - oppgaver i Avsnitt 5.4.5


Oppgave 2

  private static Node byggHuffmanTre(int[] frekvens)
  {
    PriorityQueue<Node> kø =
      new PriorityQueue<>((p,q) -> p.frekvens - q.frekvens);

    for (int i = 0; i < frekvens.length; i++)
      if (frekvens[i] > 0)          // dette tegnet skal være med
        kø.offer(new BladNode((char)i,frekvens[i]));

    if (kø.size() < 2)            // må ha minst to noder
      throw new IllegalArgumentException("Det er for få tegn!");

    for (Node rot = null;;)
    {
      Node v = kø.poll();           // blir venstre barn
      Node h = kø.poll();           // blir høyre barn

      rot = new Node(v.frekvens + h.frekvens, v, h);

      if (kø.isEmpty()) return rot;     // treet er ferdig - roten returneres
      else kø.offer(rot);         // legger noden inn i køen
    }
  }