哈夫曼树java实现

哈夫曼树是一种用于数据压缩的树形结构，它通过将出现频率较高的字符用较短的编码表示，从而实现数据的高效压缩。下面是哈夫曼树的Java实现：

import java.util.PriorityQueue;

class Node implements Comparable<Node> {
    char data;
    int frequency;
    Node left, right;

    public Node(char data, int frequency) {
        this.data = data;
        this.frequency = frequency;
        left = right = null;
    }

    @Override
    public int compareTo(Node node) {
        return this.frequency - node.frequency;
    }
}

public class HuffmanTree {
    public static void main(String[] args) {
        String text = "Hello, World!";
        Node root = buildHuffmanTree(text);
        String encodedText = encode(root, text);
        String decodedText = decode(root, encodedText);

        System.out.println("Original text: " + text);
        System.out.println("Encoded text: " + encodedText);
        System.out.println("Decoded text: " + decodedText);
    }

    public static Node buildHuffmanTree(String text) {
        int[] frequencies = new int[256];
        for (char c : text.toCharArray()) {
            frequencies[c]++;
        }

        PriorityQueue<Node> queue = new PriorityQueue<>();
        for (int i = 0; i < 256; i++) {
            if (frequencies[i] > 0) {
                queue.add(new Node((char) i, frequencies[i]));
            }
        }

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

        return queue.poll();
    }

    public static String encode(Node root, String text) {
        StringBuilder encodedText = new StringBuilder();
        encodeHelper(root, text, encodedText);
        return encodedText.toString();
    }

    private static void encodeHelper(Node node, String text, StringBuilder encodedText) {
        if (node == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            encodedText.append(node.data);
            return;
        }

        encodeHelper(node.left, text, encodedText);
        encodeHelper(node.right, text, encodedText);
    }

    public static String decode(Node root, String encodedText) {
        StringBuilder decodedText = new StringBuilder();
        Node current = root;
        for (char c : encodedText.toCharArray()) {
            if (c == '0') {
                current = current.left;
            } else if (c == '1') {
                current = current.right;
            }

            if (current.left == null && current.right == null) {
                decodedText.append(current.data);
                current = root;
            }
        }
        return decodedText.toString();
    }
}

以上是一个简单的哈夫曼树的Java实现。它包括了构建哈夫曼树、编码和解码的功能。你可以通过调用`buildHuffmanTree`方法来构建哈夫曼树，然后使用`encode`方法对文本进行编码，使用`decode`方法对编码后的文本进行解码。