Drzewo Huffmana z podaną częstotliwością Zdezorientować jak zacząć? Java

Question

Próbuję zrozumieć, co zrobić z moim problemem z pracy domowej. Próbuję utworzyć drzewo Huffman, które będzie kodować i dekodować wiadomości w Javie. Dostaję struny i częstotliwość.

[a=10, b=15, c=12, e=3, nl=4, sp=13, t=1]. 

wiem, że z Huffmana Drzewo wziąć dwóch najniższych częstotliwościach i uczynić je w drzewie z sumy ich częstotliwość jako rodzica. Rozumiem, że za pomocą kolejki priorytetowej mogę wstawić do niej całą częstotliwość i użyć metody remove(), aby usunąć 2 najniższe częstotliwości. Następnie dodaj je razem, aby uzyskać ich wagę, a następnie włóż ten ciężar z powrotem do kolejki i powtórz.

Ostateczna Drzewo powinien posiadać ciężar

[58=root, root.left = 33, root.right = 25] 
[33.left = 18, 18.left = 8, 8.left = 4] 

nie jestem pewien dokładnie, jak nawet zacząć realizować kodu Huffmana drzewo, które będzie w stanie stworzyć drzewo z częstotliwością i wyświetlanie drzewa. Przyjrzałem się innym kodom i wygląda na to, że wszyscy tworzą z kodu wejściowego przesyłania strumieniowego.

Każda pomoc byłaby wspaniała w doprowadzeniu mnie do pracy. Z góry dziękuję!

jestem przypuszczać, aby wydrukować w formacie takich jak: (pre-order traversal)

58 
- 33 
- - 18 
- - - 8 
- - - - 4 
- - - - - 1:t 
- - - - - 3:e 
- - - - 4:nl 
- - - 10:a 
- - 15:b 
- 25 
- - 12:c 
- - 13:sp 

Answer 1

import java.util.PriorityQueue; 

public class Node implements Comparable<Node> { 
    Node left; 
    Node right; 
    Node parent; 
    String text; 
    int frequency; 

    public Node(String textIn, int frequencyIn) { 
     text = textIn; 
     frequency = frequencyIn; 
    } 

    public Node(int frequencyIn) { 
     text = ""; 
     frequency = frequencyIn; 
    } 

    public int compareTo(Node n) { 
     if (frequency < n.frequency) { 
      return -1; 
     } 
     else if(frequency > n.frequency) { 
      return 1; 
     } 
     return 0; 
    } 

    public static void printFromPreOrder(Node n, String dashes) { 
     // print with colon if leaf node 
     if (n.text != "") { 
      System.out.println(dashes + n.frequency + ":" + n.text); 
     } 
     else { 
      System.out.println(dashes + n.frequency); 
     } 

     // Start recursive on left child then right 
     if (n.left != null) { 
      printFromPreOrder(n.left, dashes + "-"); 
     } 
     if (n.right != null) { 
      printFromPreOrder(n.right, dashes + "-"); 
     } 
    } 

    // Returns root node to pass to printFromPreOrder 
    public static Node makeHuffmanTree(int frequencies[], String text[]) { 
     PriorityQueue<Node> queue = new PriorityQueue<Node>(); 
     for (int i = 0; i < text.length; i++) { 
      Node n = new Node(text[i], frequencies[i]); 
      queue.add(n); 
     } 
     Node root = null; 
     while (queue.size() > 1) { 
      Node least1 = queue.poll(); 
      Node least2 = queue.poll(); 
      Node combined = new Node(least1.frequency + least2.frequency); 
      combined.right = least1; 
      combined.left = least2; 
      least1.parent = combined; 
      least2.parent = combined; 
      queue.add(combined); 
      // Keep track until we actually find the root 
      root = combined; 
     } 
     return root; 
    } 

    public static void main(String[] args) { 
     int frequencies[] = {10, 15, 12, 3, 4, 13, 1}; 
     String text[] = {"a", "b", "c", "e", "nl", "sp", "t"}; 
     Node root = Node.makeHuffmanTree(frequencies, text); 
     Node.printFromPreOrder(root, ""); 
    } 
} 

to będzie pracować dla Ciebie. Załączam twój przykład, ale powinien działać dla dowolnej liczby częstotliwości i tekstu. Upewnij się, że częstotliwości i tekst są tego samego rozmiaru, ponieważ nie sprawdzałem błędów.