哈夫曼树贪心算法java

哈夫曼树是一种经典的贪心算法，用于数据压缩和编码。下面是一个使用Java实现的哈夫曼树贪心算法的示例：

import java.util.PriorityQueue;
import java.util.HashMap;

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

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

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

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

public class HuffmanTree {
    private HuffmanNode root;
    private HashMap<Character, String> encodingTable;

    public HuffmanTree(HashMap<Character, Integer> frequencyTable) {
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();

        for (char character : frequencyTable.keySet()) {
            int frequency = frequencyTable.get(character);
            HuffmanNode node = new HuffmanNode(character, frequency);
            queue.add(node);
        }

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

        root = queue.poll();
        encodingTable = new HashMap<>();
        buildEncodingTable(root, "");
    }

    private void buildEncodingTable(HuffmanNode node, String code) {
        if (node.left == null && node.right == null) {
            encodingTable.put(node.character, code);
            return;
        }

        buildEncodingTable(node.left, code + "0");
        buildEncodingTable(node.right, code + "1");
    }

    public void printHuffmanTree() {
        printHuffmanTree(root, 0);
    }

    private void printHuffmanTree(HuffmanNode node, int level) {
        if (node == null) {
            return;
        }

        printHuffmanTree(node.right, level + 1);

        for (int i = 0; i < level; i++) {
            System.out.print("    ");
        }

        if (node.character != '\0') {
            System.out.println(node.character + " (" + node.frequency + ")");
        } else {
            System.out.println("[" + node.frequency + "]");
        }

        printHuffmanTree(node.left, level + 1);
    }

    public void printEncodingTable() {
        for (char character : encodingTable.keySet()) {
            String code = encodingTable.get(character);
            System.out.println(character + ": " + code);
        }
    }

    public static void main(String[] args) {
        HashMap<Character, Integer> frequencyTable = new HashMap<>();
        frequencyTable.put('a', 5);
        frequencyTable.put('b', 9);
        frequencyTable.put('c', 12);
        frequencyTable.put('d', 13);
        frequencyTable.put('e', 16);
        frequencyTable.put('f', 45);

        HuffmanTree huffmanTree = new HuffmanTree(frequencyTable);
        huffmanTree.printHuffmanTree();
        huffmanTree.printEncodingTable();
    }
}

这个示例中，我们首先定义了一个`HuffmanNode`类来表示哈夫曼树的节点。然后，我们创建了一个`HuffmanTree`类来构建哈夫曼树并生成编码表。在构造函数中，我们使用优先队列来按照频次构建哈夫曼树。然后，我们使用递归的方式遍历哈夫曼树，生成每个字符对应的编码。最后，我们提供了两个方法来打印哈夫曼树和编码表。

在`main`方法中，我们创建了一个频次表，并使用它来构建哈夫曼树。然后，我们打印了哈夫曼树和编码表的内容。