用java完成一个赫夫曼树
时间: 2023-07-01 13:10:09 浏览: 52
赫夫曼树(Huffman Tree)是一种特殊的二叉树,它的带权路径长度最小,常用于数据压缩。下面是用Java实现赫夫曼树的示例代码:
```java
import java.util.*;
class Node implements Comparable<Node> {
int weight;
Node left;
Node right;
public Node(int weight) {
this.weight = weight;
}
public Node(int weight, Node left, Node right) {
this.weight = weight;
this.left = left;
this.right = right;
}
public int compareTo(Node node) {
return this.weight - node.weight;
}
}
public class HuffmanTree {
public static void main(String[] args) {
int[] weights = {5, 7, 2, 13};
Node root = buildHuffmanTree(weights);
printHuffmanCode(root, "");
}
public static Node buildHuffmanTree(int[] weights) {
PriorityQueue<Node> queue = new PriorityQueue<>();
for (int weight : weights) {
queue.offer(new Node(weight));
}
while (queue.size() > 1) {
Node left = queue.poll();
Node right = queue.poll();
Node parent = new Node(left.weight + right.weight, left, right);
queue.offer(parent);
}
return queue.poll();
}
public static void printHuffmanCode(Node node, String code) {
if (node.left == null && node.right == null) {
System.out.println("Character: " + code + " Code: " + code);
return;
}
printHuffmanCode(node.left, code + "0");
printHuffmanCode(node.right, code + "1");
}
}
```
在这个例子中,我们定义了一个Node类表示树的节点。Node类实现了Comparable接口,因为我们需要将节点按权重从小到大插入到优先队列中。buildHuffmanTree方法接受一个整型数组weights,该数组表示每个字符的权重。我们使用一个优先队列来构建赫夫曼树。每次从队列中取出两个权重最小的节点,将它们合并成一个新节点,并将新节点插入到队列中。最终队列中只剩下一个节点,即为赫夫曼树的根节点。printHuffmanCode方法递归地遍历赫夫曼树,输出每个字符的编码。