用java写.已知四个带权的结点:(A,1),(B,2),(C,2),(D,3),构造Huffman数,并给出每个结点的编码.
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/15 05:46:35
![用java写.已知四个带权的结点:(A,1),(B,2),(C,2),(D,3),构造Huffman数,并给出每个结点的编码.](/uploads/image/z/11676609-9-9.jpg?t=%E7%94%A8java%E5%86%99.%E5%B7%B2%E7%9F%A5%E5%9B%9B%E4%B8%AA%E5%B8%A6%E6%9D%83%E7%9A%84%E7%BB%93%E7%82%B9%EF%BC%9A%28A%2C1%29%2C%28B%2C2%29%2C%28C%2C2%29%2C%28D%2C3%29%2C%E6%9E%84%E9%80%A0Huffman%E6%95%B0%2C%E5%B9%B6%E7%BB%99%E5%87%BA%E6%AF%8F%E4%B8%AA%E7%BB%93%E7%82%B9%E7%9A%84%E7%BC%96%E7%A0%81.)
用java写.已知四个带权的结点:(A,1),(B,2),(C,2),(D,3),构造Huffman数,并给出每个结点的编码.
用java写.已知四个带权的结点:(A,1),(B,2),(C,2),(D,3),构造Huffman数,并给出每个结点的编码.
用java写.已知四个带权的结点:(A,1),(B,2),(C,2),(D,3),构造Huffman数,并给出每个结点的编码.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Huffman {
public static void main(String[] args) {
Huffman huff = new Huffman();
//准备数据
Node node_a = new Node("A", 1);
Node node_b = new Node("B", 2);
Node node_c = new Node("C", 2);
Node node_d = new Node("D", 3);
ArrayList<Node> list = new ArrayList<Node>();
list.add(node_a);
list.add(node_b);
list.add(node_c);
list.add(node_d);
//建树
huff.build(list);
//根
Node root = list.get(0);
//编码
huff.setHuffmanCode(root);
//
System.out.println(node_a.getName()+":"+node_a.huffmanCodeString);
System.out.println(node_b.getName()+":"+node_b.huffmanCodeString);
System.out.println(node_c.getName()+":"+node_c.huffmanCodeString);
System.out.println(node_d.getName()+":"+node_d.huffmanCodeString);
}
private void setHuffmanCode(Node huff) {
Node left = huff.getNodeLeft();
// 左节点追加"0"
if (left != null) {
left.huffmanCodeString = huff.huffmanCodeString + "0";
setHuffmanCode(left);
}
Node right = huff.getNodeRight();
// 右节点追加"1"
if (right != null) {
right.huffmanCodeString = huff.huffmanCodeString + "1";
setHuffmanCode(right);
}
}
public void build(List<Node> list) {
// 按权值从小到大排序
if (list.size() > 2)
Collections.sort(list, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.getWeight() - o2.getWeight();
}
});
//移除最小的2个
Node l = list.get(0);
Node r = list.get(1);
list.remove(l);
list.remove(r);
//生成一个新的,并设置左右子节点
Node newNode = new Node(l.getName() + r.getName(), l.getWeight() + r.getWeight());
newNode.setNodeLeft(l);
newNode.setNodeRight(r);
if (list.isEmpty()) {// 根节点
list.add(newNode);
return;
} else {
list.add(newNode);
build(list);
}
}
}
class Node {
//存储编码
public String huffmanCodeString = "";
private String name; // 名称
private int weight; // 权值
private Node nodeLeft; // 左节点
private Node nodeRight;// 右节点
public Node(String name, int weight) {
this.name = name;
this.weight = weight;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public Node getNodeLeft() {
return nodeLeft;
}
public void setNodeLeft(Node nodeLeft) {
this.nodeLeft = nodeLeft;
}
public Node getNodeRight() {
return nodeRight;
}
public void setNodeRight(Node nodeRight) {
this.nodeRight = nodeRight;
}
}