面试官：给我手写一个哈夫曼编码（使用java语言实现）

哈弗曼树往往都会根据哈夫曼编码结合着来说，因此这篇文章，主要结合着面试问题来说明。

一、基本概念

哈夫曼树的目的是找出存放一串字符所需的最少的二进制编码，原理是通过统计出每种字符出现的频率！不断地对其合并。

举个例子：有一串字符，现在把这些字符进行统计，频率表 A：60, B:45, C:13 D:69 E:14 F:5 G:3。现在要对这些字符进行编码，但是前提是使用最少的二进制编码。这时候怎么办呢？这就用到了我们的哈弗曼树。

我们需要构造一个哈弗曼树，构造赫夫曼树的算法是一个贪心算法，贪心的地方在于：总是选取当前频率(权值)最低的两个结点来进行合并，构造新结点。

现在我们就来构造一颗哈弗曼树。

二、构造哈弗曼树

刚刚我们已经说了，构造哈夫曼树是每次选取当前频率最低的两个节点来进行合并就好了。

1、原始序列

2、选取最小的F和G节点合并

3、选取目前最小的C节点与8合并

4、继续重复以上步骤进行合并

到此为止，我们的哈弗曼树就已经构造出来了。接下来我们添加01规则，进行哈夫曼编码。

三、哈夫曼编码

哈夫曼编码的规则是，左边添加0，右边添加1。看下图就明白了。

OK，也就是在每一条边上添加了01。此时我们来看每一个字符的编码。

A：10 B：01 C：0011 D：11 E：000 F：00101 G：00100

四、java实现哈夫曼编码

我们直接给出一个整体的哈夫曼编码的java实现。

第一步：定义一个节点

 1private class Node implements Comparable<Node> {
 2        char ch;
 3        int freq;
 4        boolean isLeaf;
 5        Node left, right;
 6        public Node(char ch, int freq) {
 7            this.ch = ch;
 8            this.freq = freq;
 9            isLeaf = true;
10        }
11        public Node(Node left, Node right, int freq) {
12            this.left = left;
13            this.right = right;
14            this.freq = freq;
15            isLeaf = false;
16        }
17        @Override
18        public int compareTo(Node o) {
19            return this.freq - o.freq;
20        }
21}

第二步：实现哈夫曼编码

 1public class HuffmanTree {
 2    public Map<Character, String> encode(Map<Character, Integer> frequencyForChar) {
 3        //1、优先级队列添加所有的元素
 4        PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
 5        for (Character c : frequencyForChar.keySet()) {
 6            priorityQueue.add(new Node(c, frequencyForChar.get(c)));
 7        }
 8        //2、选取最小的俩节点并移除
 9        while (priorityQueue.size() != 1) {
10            Node node1 = priorityQueue.poll();
11            Node node2 = priorityQueue.poll();
12            //3、合并之后把合并之后的放到队列里面
13            priorityQueue.add(new Node(node1, node2, node1.freq + node2.freq));
14        }
15        //4、选取一个最小的，进行编码
16        return encodeReal(priorityQueue.poll());
17    }
18
19    //5、实现编码的方法
20    private Map<Character, String> encodeReal(Node root) {
21        Map<Character, String> encodingForChar = new HashMap<>();
22        encodeChar(root, "", encodingForChar);
23        return encodingForChar;
24    }
25    private void encodeChar(Node node, String encoding, 
26                            Map<Character, String> encodingChar) {
27        //6、如果是叶子，放进来字符还有相应的编码
28        if (node.isLeaf) {
29            encodingChar.put(node.ch, encoding);
30            return;
31        }
32        //7、左右递归编码
33        encodeChar(node.left, encoding + '0', encodingChar);
34        encodeChar(node.right, encoding + '1', encodingChar);
35    }
36}

更多相关文章

随机推荐