java程序输出huffman树的结点数组
时间: 2024-05-11 13:15:49 浏览: 14
以下是一个Java程序,可用于输出Huffman树的结点数组:
```java
import java.util.*;
class Node {
char data;
int frequency;
Node left, right;
Node(char data, int frequency) {
this.data = data;
this.frequency = frequency;
left = right = null;
}
}
class Huffman {
// 建立Huffman树
Node buildTree(char[] data, int[] frequency) {
PriorityQueue<Node> pq = new PriorityQueue<Node>(new Comparator<Node>() {
public int compare(Node a, Node b) {
return a.frequency - b.frequency;
}
});
for (int i = 0; i < data.length; i++) {
pq.add(new Node(data[i], frequency[i]));
}
while (pq.size() > 1) {
Node a = pq.poll();
Node b = pq.poll();
Node c = new Node('$', a.frequency + b.frequency);
c.left = a;
c.right = b;
pq.add(c);
}
return pq.poll();
}
// 打印Huffman树的结点数组
void printTree(Node root) {
Queue<Node> q = new LinkedList<>();
q.add(root);
List<Integer> list = new ArrayList<Integer>();
while (!q.isEmpty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
Node node = q.poll();
list.add(node.frequency);
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
}
}
System.out.println(list);
}
public static void main(String[] args) {
char[] data = {'a', 'b', 'c', 'd', 'e', 'f'};
int[] frequency = {5, 9, 12, 13, 16, 45};
Huffman huffman = new Huffman();
Node root = huffman.buildTree(data, frequency);
huffman.printTree(root);
}
}
```
这个程序使用字符数组和频率数组作为输入,可以生成Huffman树,并输出其结点数组。