Question

用java写。已知四个带权的结点：(A,1),(B,2),(C,2),(D,3)，构造Huffman数，并给出每个结点的编码。

跪求！

Answer 1

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;
    }

}