创建赫夫曼树Java代码

以下是Java中创建赫夫曼树的示例代码：

import java.util.*;

class HuffmanNode implements Comparable<HuffmanNode> {
    int frequency;
    char character;
    HuffmanNode left, right;

    public HuffmanNode(int frequency, char character, HuffmanNode left, HuffmanNode right) {
        this.frequency = frequency;
        this.character = character;
        this.left = left;
        this.right = right;
    }

    public boolean isLeaf() {
        return left == null && right == null;
    }

    @Override
    public int compareTo(HuffmanNode o) {
        return this.frequency - o.frequency;
    }
}

public class HuffmanTree {
    private Map<Character, Integer> frequencyMap;
    private HuffmanNode root;

    public HuffmanTree(Map<Character, Integer> frequencyMap) {
        this.frequencyMap = frequencyMap;
        buildTree();
    }

    private void buildTree() {
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();
        for (Character c : frequencyMap.keySet()) {
            queue.add(new HuffmanNode(frequencyMap.get(c), c, null, null));
        }

        while (queue.size() > 1) {
            HuffmanNode left = queue.poll();
            HuffmanNode right = queue.poll();
            HuffmanNode parent = new HuffmanNode(left.frequency + right.frequency, '\0', left, right);
            queue.add(parent);
        }

        root = queue.poll();
    }

    public Map<Character, String> getCodeTable() {
        Map<Character, String> codeTable = new HashMap<>();
        getCodeTableHelper(codeTable, root, "");
        return codeTable;
    }

    private void getCodeTableHelper(Map<Character, String> codeTable, HuffmanNode node, String code) {
        if (node.isLeaf()) {
            codeTable.put(node.character, code);
            return;
        }
        getCodeTableHelper(codeTable, node.left, code + "0");
        getCodeTableHelper(codeTable, node.right, code + "1");
    }

    public static void main(String[] args) {
        Map<Character, Integer> frequencyMap = new HashMap<>();
        frequencyMap.put('A', 10);
        frequencyMap.put('B', 20);
        frequencyMap.put('C', 30);
        frequencyMap.put('D', 40);
        HuffmanTree huffmanTree = new HuffmanTree(frequencyMap);
        System.out.println(huffmanTree.getCodeTable());
    }
}

在这个示例中，我们定义了一个HuffmanNode类来表示Huffman树中的节点。HuffmanNode类实现了Comparable接口，以便我们可以将节点添加到优先队列中。我们还定义了一个HuffmanTree类，该类通过给定的频率映射来构建Huffman树。构建树的过程使用优先队列进行，队列中的元素按其频率排序。我们还实现了一个辅助函数，用于生成Huffman编码表。最后，我们在main方法中使用一个简单的示例来测试我们的Huffman树实现。