哈夫曼代码数据结构java

以下是Java中哈夫曼编码的实现：

1. 定义节点类HuffmanNode，包含字符、权重、左右子节点等属性：

class HuffmanNode {
    char c;
    int freq;
    HuffmanNode left;
    HuffmanNode right;
}

2. 定义比较器类HuffmanComparator，用于按照节点的权重大小进行比较：

class HuffmanComparator implements Comparator<HuffmanNode> {
    public int compare(HuffmanNode x, HuffmanNode y) {
        return x.freq - y.freq;
    }
}

3. 定义哈夫曼编码类HuffmanCode，包含字符频率统计、构建哈夫曼树、生成哈夫曼编码等方法：

import java.util.*;

class HuffmanCode {
    // 统计字符频率
    public static Map<Character, Integer> getFrequencies(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        return freq;
    }

    // 构建哈夫曼树
    public static HuffmanNode buildTree(Map<Character, Integer> freq) {
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(new HuffmanComparator());
        for (char c : freq.keySet()) {
            HuffmanNode node = new HuffmanNode();
            node.c = c;
            node.freq = freq.get(c);
            pq.add(node);
        }
        while (pq.size() > 1) {
            HuffmanNode x = pq.poll();
            HuffmanNode y = pq.poll();
            HuffmanNode z = new HuffmanNode();
            z.freq = x.freq + y.freq;
            z.left = x;
            z.right = y;
            pq.add(z);
        }
        return pq.poll();
    }

    // 生成哈夫曼编码
    public static Map<Character, String> getCodes(HuffmanNode root) {
        Map<Character, String> codes = new HashMap<>();
        getCode(root, "", codes);
        return codes;
    }

    private static void getCode(HuffmanNode node, String code, Map<Character, String> codes) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            codes.put(node.c, code);
        }
        getCode(node.left, code + "0", codes);
        getCode(node.right, code + "1", codes);
    }
}

4. 在主函数中调用以上方法，实现哈夫曼编码的功能：

public static void main(String[] args) {
    String s = "hello world";
    Map<Character, Integer> freq = HuffmanCode.getFrequencies(s);
    HuffmanNode root = HuffmanCode.buildTree(freq);
    Map<Character, String> codes = HuffmanCode.getCodes(root);
    for (char c : codes.keySet()) {
        System.out.println(c + ": " + codes.get(c));
    }
}