Huffman Ağacı Verilen Frekans ile Başlamak için nasıl karıştırın? Java

Question

Ödev sorunumla ne yapacağımı anlamaya çalışıyorum. Java'daki mesajları kodlayacak ve çözecek bir Huffman Ağacı oluşturmaya çalışıyorum. Dizeler ve Frekans verdim.

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

Ben Huffman Ağacı ile iki düşük Frekansları alıp ebeveyn olarak kendi Sıklığı toplamı ile bir ağaca bunları yapmak biliyoruz. Bir Öncelik Kuyruğu kullanarak, tüm Frekansı buna ekleyebileceğimi ve en düşük 2 Frekansı çıkarmak için remove() yöntemini kullanabileceğini anlıyorum. Daha sonra, her ikisinin de Ağırlığını almak için onları bir araya toplayın, ardından bu Ağırlık'yı Sıraya yerleştirin ve tekrarlayın.

son Ağacı Hatta Ağacı Frekans ağacı oluşturmak ve görüntülemek mümkün olacak bir Huffman Ağacı kod uygulamak başlamak için tam olarak nasıl emin değilim

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

ağırlığını tutmak gerekir. Diğer kodlara bakıyorum ve hepsinin Akışlı Giriş Kodu'ndan ya da benzerlerinden oluştuğu anlaşılıyor.

Gitmeme yardım etmek için herhangi bir yardım harika olurdu. Şimdiden teşekkürler! (Ön sipariş geçişi) Bu senin için

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, ""); 
    } 
} 

çalışacaktır:

Ben bir biçime gibi olan yazdırmak için varsayalım değilim. Örneğinizi ekledim, ancak herhangi bir sayıda frekans ve metin için çalışmalı. Sadece hataların ve metinlerin aynı boyutta olduğundan emin olun çünkü hata kontrolü yapmadım.