Huffman-Baum mit gegebener Häufigkeit Wie beginnen? Java

Question

Ich versuche zu verstehen, was ich mit meinem Hausaufgabenproblem tun soll. Ich versuche, einen Huffman-Baum zu erstellen, der Nachrichten in Java codiert und dekodiert. Ich habe Strings und Frequency.

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

Ich weiß, dass mit Huffman-Baum Sie die beiden niedrigsten Frequenzen nehmen und sie in einen Baum mit der Summe ihrer Häufigkeit als Mutter zu machen. Ich verstehe, dass mit einer Prioritätswarteschlange kann ich die gesamte Frequenz einfügen und verwenden Sie die remove() Methode, um die 2 niedrigsten Frequenz. Dann fügen Sie sie zusammen, um das Gewicht von ihnen beide zu erhalten, dann fügen Sie dieses Gewicht wieder in die Warteschlange ein und wiederholen es.

Der letzte Baum soll Gewicht von

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

hält ich bin nicht sicher, wie man auch beginnen, einen Huffman-Baum-Code zu implementieren, die den Baum mit der Frequenz zu erzeugen in der Lage, und den Baum angezeigt werden soll. Ich habe mir andere Codes angeschaut und es sieht so aus, als würden sie allesamt aus Streaming Input Code erstellen.

Jede Hilfe wäre großartig, um mich in Gang zu bringen. Danke im Voraus!

Ich bin suppose mit einem Format auszudrucken, wie: (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, ""); 
    } 
} 

Dies wird für Sie arbeiten. Ich habe Ihr Beispiel hinzugefügt, aber es sollte für eine beliebige Anzahl von Frequenzen und Text funktionieren. Stellen Sie nur sicher, dass die Frequenzen und der Text die gleiche Größe haben, da ich keine Fehlerprüfung durchgeführt habe.