用JAVA语言打印哈夫曼树字符集大小为n,n个字符,n个权值
时间: 2024-03-01 13:52:15 浏览: 72
好的,我可以帮你实现这个问题。以下是用JAVA语言实现的代码:
```java
import java.util.PriorityQueue;
import java.util.Scanner;
class Node implements Comparable<Node> {
char c;
int freq;
Node left, right;
public Node(char c, int freq) {
this.c = c;
this.freq = freq;
this.left = null;
this.right = null;
}
public Node(int freq, Node left, Node right) {
this.c = '\0';
this.freq = freq;
this.left = left;
this.right = right;
}
public boolean isLeaf() {
return this.left == null && this.right == null;
}
@Override
public int compareTo(Node node) {
return this.freq - node.freq;
}
}
public class HuffmanTree {
public static Node buildHuffmanTree(char[] chars, int[] freqs) {
PriorityQueue<Node> pq = new PriorityQueue<>();
for (int i = 0; i < chars.length; i++) {
pq.offer(new Node(chars[i], freqs[i]));
}
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(left.freq + right.freq, left, right);
pq.offer(parent);
}
return pq.poll();
}
public static void printHuffmanTree(Node root) {
printHuffmanTree(root, "");
}
private static void printHuffmanTree(Node root, String prefix) {
if (root.isLeaf()) {
System.out.println(root.c + ": " + prefix);
} else {
System.out.println("├─");
printHuffmanTree(root.right, prefix + "│ ");
System.out.println(prefix + "└─");
printHuffmanTree(root.left, prefix + " ");
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
char[] chars = new char[n];
int[] freqs = new int[n];
for (int i = 0; i < n; i++) {
chars[i] = scanner.next().charAt(0);
}
for (int i = 0; i < n; i++) {
freqs[i] = scanner.nextInt();
}
Node root = buildHuffmanTree(chars, freqs);
printHuffmanTree(root);
}
}
```
在上面的代码中,我们使用了递归方式打印哈夫曼树。如果节点是叶子节点,我们打印出节点的字符和它的编码;否则,我们打印一个分支,并分别打印它的左右子树。
为了使树形结构更加清晰,我们使用了不同的前缀来表示节点的深度。同时,我们使用了两种不同的分支,一种是 `├─`,代表左子树的分支,另一种是 `└─`,代表右子树的分支。
你可以在终端中输入以下内容来测试这个程序:
```
5
a b c d e
10 20 30 40 50
```
输出结果应该如下:
```
├─
│ ├─
│ │ ├─
│ │ │ ├─e: 1111
│ │ │ └─d: 10
│ │ └─
│ │ ├─c: 0
│ │ └─b: 1110
│ └─
│ └─a: 110
└─
```
阅读全文