Реализация

  // Узел дерева Хаффмана
static class Node implements Comparable<Node> {
    char symbol; // символ, хранящийся в узле; '\0' для внутренних узлов
    int freq; // частота (вес) этого узла/поддерева
    Node left; // указатель на левого потомка (бит '0')
    Node right; // указатель на правого потомка (бит '1')

    // Конструктор для листьев
    Node(char symbol, int freq) {
        this.symbol = symbol;
        this.freq = freq;
        this.left = this.right = null;
    }

    // Конструктор для внутренних узлов: объединяет два поддерева
    Node(Node left, Node right) {
        this.symbol = '\0';
        this.freq = left.freq + right.freq;
        this.left = left;
        this.right = right;
    }

    // Сравнение узлов по частоте
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.freq, other.freq);
    }
}
  

  static class Node implements Comparable<Node> {
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.freq, other.freq);
    }
}
  

  public static Node buildHuffmanTree(String data) {
    // 1) Подсчёт частот символов
    Map<Character, Integer> freq = new HashMap<>();
    for (char ch : data.toCharArray()) {
        freq.put(ch, freq.getOrDefault(ch, 0) + 1);
    }

    // 2) Инициализация мин-кучи деревьев-одиночек
    PriorityQueue<Node> pq = new PriorityQueue<>();
    for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
        pq.add(new Node(entry.getKey(), entry.getValue()));
    }

    // 3) Объединяем, пока в куче не останется одно дерево
    while (pq.size() > 1) {
        // Извлекаем два узла с наименьшими частотами
        Node left = pq.poll();
        Node right = pq.poll();

        // Создаём новый узел-родитель с суммарной частотой
        pq.add(new Node(left, right));
    }

    return pq.poll();
}
  

  public static void generateCodes(Node node, String prefix, Map<Character, String> codeboo) {
if (node == null) return;

    if (node.symbol != '\0') {
        // Лист: присваиваем накопленный префикс (или "0", если один символ)
        codebook.put(node.symbol, prefix.isEmpty() ? "0" : prefix);
    } else {
        // Внутренний узел: идём влево (добавляем '0') и вправо (добавляем '1')
        generateCodes(node.left, prefix + '0', codebook);
        generateCodes(node.right, prefix + '1', codebook);
    }
}
  

  public static void main(String[] args) {
    System.setOut(new PrintStream(System.out, true, StandardCharsets.UTF_8));

    // Пример строки для кодирования
    String text = "AAABBBBBAAABBDDCCCCCDDDDBBAAAAAAAAAAACCCCAAAEEEEAAADDDAADAAAABBAADDACCACAAAAEEEBBEEAAAADDDDAA";

    // Построение дерева Хаффмана
    Node root = buildHuffmanTree(text);

    // Генерация таблицы кодов
    Map<Character, String> codes = new HashMap<>();
    generateCodes(root, "", codes);

    // Вывод результатов
    System.out.println("Codewords:");
    for (Map.Entry<Character, String> entry : codes.entrySet()) {
        System.out.println("'" + entry.getKey() + "': " + entry.getValue());
    }
}