算法面试题-美团点评2016研发工程师编程题(二)-字符编码（哈夫曼树）
题目：
解析：这个题目的关键问题是“最短的编码”，这里可以知道应该是Huffman编码了。
哈夫曼编码是一种可变字长编码，也就是说对于不同的字符的编码不是定长的，所以才能比定长编码要短。
哈夫曼树
哈夫曼编码依靠的就是哈夫曼树，根据每个字符出现的次数作为权重，生成对应的哈夫曼树，对应的编码长度即为最短。
哈夫曼树的构造很简单，每次从所有的权重中选出最小两个分别作为的作为子节点（一般左节点权重小于右节点），权重相加值为父节点权重，再把父节点代替两个子节点重新进入队列中，不断循环最后会得到一颗二叉树。
例子：以2,4,5,8,13为权构造哈夫曼树
① 选出最小两个数为2和4，以2为左节点，4为右节点构造二叉树，和为父节点的值，并且将父节点的权放回
完成后权值为：5,6,8,13
② 选出最小两个数5和6，操作同上
权值为：8,11,13
③ 选出8和11，操作同上
权值为：13,19
④ 最后剩下两个，分别作为左右节点
得到的二叉树就是哈夫曼树。
回到哈夫曼编码，哈夫曼编码对应的就是将每个字符出现的次数作为权，生成对应的哈夫曼树，然后以左子树为0，右子树为1，对每个字符进行编码。
所以对于题目中的例子，生成的哈夫曼树和对应的编码应该是这样的：
注意：二叉树的构造不一定相同，因为部子节点的权是相同的，构造的二叉树会有所不同。
代码：
① 定义哈夫曼树节点：
1 public class Node { 2 Character value; // 节点字符 3 int count = 1; // 深度（节点与根节点的距离） 4 int power = 1; // 权（出现次数） 5 Node left = null; // 左子节点 6 Node right = null; // 右子节点 7 8 /** 9 * 更新子节点的深度 10 */ 11 public void notifyChild() { 12 count += 1; 13 if (left != null) { 14 left.notifyChild(); 15 } 16 if (right != null) { 17 right.notifyChild(); 18 } 19 } 20 21 public Node(Character value) { 22 this.value = value; 23 } 24 25 public boolean sameValue(char c) { 26 return c == value; 27 } 28 29 /** 30 * 根据传入的节点作为此节点的子节点 31 * @param left 左节点 32 * @param right 右节点 33 */ 34 public void updateChild(Node left, Node right) { 35 this.left = left; 36 this.right = right; 37 this.power = left.power + right.power; 38 } 39 40 }
11-19行为更新操作，因为最后要得到每个字符的编码长度，这个长度实际上是在构造二叉树的时候可以确定的，因为如果父节点被选出，则其子节点的深度会增加1，这个方法用来通知子节点进行深度加一操作。
② 编写计算方法
1 void count(String s){ 2 // 计算每个字符出现的次数 3 ArrayList<Node> chars = new ArrayList<>(); 4 char[] StrChars = s.toCharArray(); 5 chars.add(new Node(StrChars[0])); 6 for (int j = 1; j < StrChars.length; j++) { 7 char c = StrChars[j]; 8 int size = chars.size(); 9 for (int i = 0; i < size; i++) { 10 if (chars.get(i).sameValue(c)) { 11 chars.get(i).power += 1; 12 break; 13 } 14 if (i == size - 1) { 15 chars.add(new Node(c)); 16 } 17 } 18 } 19 20 // 根据权值排序，从小到大，插入排序 21 ArrayList<Node> nodes = new ArrayList<>(); 22 nodes.add(chars.get(0)); 23 for (int i = 1; i < chars.size(); i++) { 24 int size = nodes.size(); 25 for (int j = 0; j < size; j++) { 26 Node c = chars.get(i); 27 if (c.power < nodes.get(j).power) { 28 nodes.add(j, c); 29 break; 30 } 31 if (j == size - 1) { 32 nodes.add(c); 33 } 34 } 35 } 36 chars = nodes; 37 38 // 构造哈夫曼树 39 while (chars.size() > 1) { 40 Node root = new Node(null); 41 Node left = chars.get(0); 42 Node right = chars.get(1); 43 root.updateChild(left, right); // 生成新节点 44 chars.remove(0); // 删除被选节点 45 chars.remove(0); // 删除被选节点 46 int size = chars.size(); 47 if (size == 0) { 48 chars.add(root); // 退出循环条件 49 } 50 for (int i = 0; i < size; i++) { 51 if (root.power < chars.get(i).power) { 52 chars.add(i, root); // 将新生成的节点插入到对应位置使得序列依然有序 53 root.notifyChild(); // 通知子节点更新深度 54 break; 55 } 56 if (i == size - 1) { 57 chars.add(root); 58 root.notifyChild(); 59 } 60 } 61 } 62 63 // 遍历二叉树，计算最短编码长度 64 int sum = 0; 65 Stack<Node> stack = new Stack<>(); 66 Node root = chars.get(0); 67 stack.add(root); 68 while (!stack.isEmpty()) { 69 root = stack.pop(); 70 if (root.value != null) { 71 sum += root.power * root.count; 72 } 73 if (root.right != null) { 74 stack.push(root.right); 75 } 76 if (root.left != null) { 77 stack.push(root.left); 78 } 79 } 80 System.out.println(sum); 81 }
注意：
① 这里排序使用了插入排序，时间复杂度较高，但是通过面试题是没问题的，考虑到sort方法不能用，就只能折中了。
② 这里的节点的深度是指子节点到根节点的距离，如例子中E到根节点距离为2
③ 深度的计算只有字符节点是正确的，因为方法中不加判断的对根节点和子节点都加一了，但是计算只要求子节点，所以忽略这个问题。
完整代码如下：
1 package com.fndroid; 2 3 import java.util.*; 4 5 public class Main { 6 7 public static void main(String[] args) { 8 Main solution = new Main(); 9 Scanner scanner = new Scanner(System.in); 10 while (scanner.hasNext()) { 11 solution.count(scanner.next()); 12 } 13 } 14 15 void count(String s){ 16 // 计算每个字符出现的次数 17 ArrayList<Node> chars = new ArrayList<>(); 18 char[] StrChars = s.toCharArray(); 19 chars.add(new Node(StrChars[0])); 20 for (int j = 1; j < StrChars.length; j++) { 21 char c = StrChars[j]; 22 int size = chars.size(); 23 for (int i = 0; i < size; i++) { 24 if (chars.get(i).sameValue(c)) { 25 chars.get(i).power += 1; 26 break; 27 } 28 if (i == size - 1) { 29 chars.add(new Node(c)); 30 } 31 } 32 } 33 34 // 根据权值排序，从小到大，插入排序 35 ArrayList<Node> nodes = new ArrayList<>(); 36 nodes.add(chars.get(0)); 37 for (int i = 1; i < chars.size(); i++) { 38 int size = nodes.size(); 39 for (int j = 0; j < size; j++) { 40 Node c = chars.get(i); 41 if (c.power < nodes.get(j).power) { 42 nodes.add(j, c); 43 break; 44 } 45 if (j == size - 1) { 46 nodes.add(c); 47 } 48 } 49 } 50 chars = nodes; 51 52 // 构造哈夫曼树 53 while (chars.size() > 1) { 54 Node root = new Node(null); 55 Node left = chars.get(0); 56 Node right = chars.get(1); 57 root.updateChild(left, right); // 生成新节点 58 chars.remove(0); // 删除被选节点 59 chars.remove(0); // 删除被选节点 60 int size = chars.size(); 61 if (size == 0) { 62 chars.add(root); // 退出循环条件 63 } 64 for (int i = 0; i < size; i++) { 65 if (root.power < chars.get(i).power) { 66 chars.add(i, root); // 将新生成的节点插入到对应位置使得序列依然有序 67 root.notifyChild(); // 通知子节点更新深度 68 break; 69 } 70 if (i == size - 1) { 71 chars.add(root); 72 root.notifyChild(); 73 } 74 } 75 } 76 77 // 遍历二叉树，计算最短编码长度 78 int sum = 0; 79 Stack<Node> stack = new Stack<>(); 80 Node root = chars.get(0); 81 stack.add(root); 82 while (!stack.isEmpty()) { 83 root = stack.pop(); 84 if (root.value != null) { 85 sum += root.power * root.count; 86 } 87 if (root.right != null) { 88 stack.push(root.right); 89 } 90 if (root.left != null) { 91 stack.push(root.left); 92 } 93 } 94 System.out.println(sum); 95 } 96 97 public class Node { 98 Character value; // 节点字符 99 int count = 1; // 深度（节点与根节点的距离） 100 int power = 1; // 权（出现次数） 101 Node left = null; // 左子节点 102 Node right = null; // 右子节点 103 104 /** 105 * 更新子节点的深度 106 */ 107 public void notifyChild() { 108 count += 1; 109 if (left != null) { 110 left.notifyChild(); 111 } 112 if (right != null) { 113 right.notifyChild(); 114 } 115 } 116 117 public Node(Character value) { 118 this.value = value; 119 } 120 121 public boolean sameValue(char c) { 122 return c == value; 123 } 124 125 /** 126 * 根据传入的节点作为此节点的子节点 127 * @param left 左节点 128 * @param right 右节点 129 */ 130 public void updateChild(Node left, Node right) { 131 this.left = left; 132 this.right = right; 133 this.power = left.power + right.power; 134 } 135 136 } 137 }