2024年10月30日总结

今天下午对上午学习的哈夫曼树进行了复习，自己结合ai尝试进行了哈夫曼树的构建
class HuffmanNode implements Comparable {
char data; // 节点的数据（字符）
int frequency; // 节点的频率
HuffmanNode left, right; // 左右子节点

HuffmanNode(char data, int frequency) {
    this.data = data;
    this.frequency = frequency;
}

// 实现节点的比较方法，按频率排序
@Override
public int compareTo(HuffmanNode other) {
    return this.frequency - other.frequency;
}

}

// 哈夫曼树类
public class HuffmanTree {
// 构建哈夫曼树
public static HuffmanNode buildHuffmanTree(char[] data, int[] frequency) {
PriorityQueue queue = new PriorityQueue<>();

    // 将每个字符和对应频率作为叶子节点加入队列
    for (int i = 0; i < data.length; i++) {
        queue.add(new HuffmanNode(data[i], frequency[i]));
    }
    
    // 合并节点直到队列中只剩一个根节点
    while (queue.size() > 1) {
        HuffmanNode left = queue.poll();
        HuffmanNode right = queue.poll();
        int sum = left.frequency + right.frequency;
        HuffmanNode parent = new HuffmanNode('-', sum);
        parent.left = left;
        parent.right = right;
        queue.add(parent);
    }
    
    return queue.poll();  // 返回根节点
}

// 打印哈夫曼编码
public static void printHuffmanCodes(HuffmanNode root, String code) {
    if (root == null) return;

    // 如果是叶子节点，打印编码
    if (root.left == null && root.right == null) {
        System.out.println(root.data + ": " + code);
        return;
    }

    // 递归生成编码
    printHuffmanCodes(root.left, code + "0");
    printHuffmanCodes(root.right, code + "1");
}

public static void main(String[] args) {
    char[] data = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int[] frequency = { 5, 9, 12, 13, 16, 45 };
    HuffmanNode root = buildHuffmanTree(data, frequency);
}

}