用JAVA实现从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。
时间: 2023-11-03 10:05:39 浏览: 43
好的,我可以为您解答这个问题。
实现思路如下:
1. 定义一个Node类,表示哈夫曼树中的节点,包含字符、权值和左右子节点。
```java
class Node {
char c;
int weight;
Node left;
Node right;
public Node(char c, int weight) {
this.c = c;
this.weight = weight;
left = null;
right = null;
}
}
```
2. 读入字符集大小n以及n个字符和n个权值,存储在两个数组中。
```java
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
char[] chars = new char[n];
int[] weights = new int[n];
for (int i = 0; i < n; i++) {
chars[i] = scanner.next().charAt(0);
weights[i] = scanner.nextInt();
}
```
3. 定义一个优先队列,将所有节点按照权值从小到大排序,每次取出两个权值最小的节点合并为一个新节点,直到队列中只剩下一个节点,这个节点就是哈夫曼树的根节点。
```java
PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.weight));
for (int i = 0; i < n; i++) {
queue.offer(new Node(chars[i], weights[i]));
}
while (queue.size() > 1) {
Node left = queue.poll();
Node right = queue.poll();
Node parent = new Node('\0', left.weight + right.weight);
parent.left = left;
parent.right = right;
queue.offer(parent);
}
Node root = queue.poll();
```
完整代码如下: