Xinyi Dong

先前在亚马逊面试的第一道就碰到了哈弗曼树。虽然早有准备，不过匆忙之中写出的代码还是忽略了诸多要点。以下是鄙人对哈弗曼树的一些肤浅理解。诸君若要深入了解请务必亲自实践。 哈弗曼树主要应用于数据压缩、字符编码中。与大部分树的构建方式不同，哈弗曼树是自底而上构建的。算法的输入通常为字符串，根据字符出现的频率由小到大构建产生，其叶节点（且只有叶节点）为字符串的每一个字符。   其大致的原理是： 1. 在队列中输入一连串字符。此处假设所有字符为ASCII。（队列的节点结构可以是字符及其频率） 2. 从中选出并删除两个出现频率最小的节点（由此引出最小优先队列的应用） 3. 将以上两个节点看做两个叶节点，在两者顶部新建父节点。叶节点的值如先前定义的，包含字符的值及其频率；而父节点的值的字符部分为空，频率则是其两个子节点频率的和。 4. 将新的父节点加入队列。 5. 重复2-4 以下为部分代码： 树节点结构： ``` Java private class Node implements Comparable{ private char ch; private int freq;...