具有给定频率的霍夫曼树如何混淆如何开始？ Java的
发布时间：2020-12-14 19:32:45 所属栏目：Java 来源：网络整理
导读：我想知道如何处理我的作业问题.我正在尝试创建一个将用 Java编码和解码消息的霍夫曼树.我有字符串和频率. [a=10,b=15,c=12,e=3,nl=4,sp=13,t=1]. 我知道,对于霍夫曼树,你可以选择两个最低的频率,然后将它们变成一棵树,其频率为总和. 我知道使用优先级队列我
|
我想知道如何处理我的作业问题.我正在尝试创建一个将用
Java编码和解码消息的霍夫曼树.我有字符串和频率.
[a=10,b=15,c=12,e=3,nl=4,sp=13,t=1]. 我知道,对于霍夫曼树,你可以选择两个最低的频率,然后将它们变成一棵树,其频率为总和. 最终的树应该保持重量 [58=root,root.left = 33,root.right = 25] [33.left = 18,18.left = 8,8.left = 4] 我不确定如何开始实现一个能够用频率创建树并显示树的霍夫曼树代码.我看看其他代码,似乎他们都是从Streaming Input Code创建的. 让我走的任何帮助都会很棒.提前致谢！ 我想用以下格式打印出来:(预订遍历) 58 - 33 - - 18 - - - 8 - - - - 4 - - - - - 1:t - - - - - 3:e - - - - 4:nl - - - 10:a - - 15:b - 25 - - 12:c - - 13:sp 解决方法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,"");
}
}
这对你有用.我已经包含了您的示例,但它应该适用于任意数量的频率和文本.只需确保频率和文本大小相同,因为我没有进行错误检查. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |