Java实现哈夫曼树

以下是Java实现哈夫曼树的代码和详细步骤：

import java.util.PriorityQueue;

public class HuffmanTree {
    private Node root;

    private static class Node implements Comparable<Node> {
        private final char ch;
        private final int freq;
        private final Node left, right;

        Node(char ch, int freq, Node left, Node right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }

    public HuffmanTree(char[] chars, int[] freqs) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < chars.length; i++) {
            pq.offer(new Node(chars[i], freqs[i], null, null));
        }
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node('\0', left.freq + right.freq, left, right);
            pq.offer(parent);
        }
        root = pq.poll();
    }

    private void buildCode(String[] st, Node x, String s) {
        if (!x.isLeaf()) {
            buildCode(st, x.left, s + '0');
            buildCode(st, x.right, s + '1');
        } else {
            st[x.ch] = s;
        }
    }

    public String[] buildCode() {
        String[] st = new String[256];
        buildCode(st, root, "");
        return st;
    }

    public static void main(String[] args) {
        char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
        int[] freqs = {45, 13, 12, 16, 9, 5};
        HuffmanTree tree = new HuffmanTree(chars, freqs);
        String[] code = tree.buildCode();
        for (int i = 0; i < chars.length; i++) {
            System.out.println(chars[i] + ": " + code[chars[i]]);
        }
    }
}

步骤如下：

1.定义一个Node类，表示哈夫曼树的节点，包含字符、频率、左右子节点等信息。

2.定义HuffmanTree类，包含一个Node类型的根节点。

3.在HuffmanTree类中定义一个Node类的比较器，用于构建哈夫曼树时的优先队列排序。

4.在HuffmanTree类中定义一个构造函数，接收字符数组和频率数组作为参数，用于构建哈夫曼树。

5.在构造函数中，先将所有节点加入优先队列中。

6.然后不断从优先队列中取出两个频率最小的节点，合并成一个新的节点，再将新节点加入优先队列中，直到队列中只剩下一个节点，即为根节点。

7.在HuffmanTree类中定义一个buildCode方法，用于生成每个字符的哈夫曼编码。

8.在buildCode方法中，递归遍历哈夫曼树，生成每个字符的编码。

9.在HuffmanTree类中定义一个main方法，用于测试。

10.在main方法中，定义字符数组和频率数组，创建HuffmanTree对象，调用buildCode方法生成编码，输出每个字符的编码。