概叙
科普文：算法和数据结构系列【算法和数据结构概叙】-CSDN博客
科普文：算法和数据结构系列【非线性数据结构：树Tree和堆Heap的原理、应用、以及java实现】-CSDN博客
科普文：算法和数据结构系列【树：4叉树、N叉树】-CSDN博客
科普文：算法和数据结构系列【二叉树总结-上篇：满二叉树、完全二叉树、大顶堆/小顶堆、二叉搜索树、自平衡二叉树、红黑树总结】-CSDN博客
科普文：算法和数据结构系列【二叉树总结-下篇：满二叉树、完全二叉树、大顶堆/小顶堆、二叉搜索树、自平衡二叉树、红黑树总结】-CSDN博客
科普文：算法和数据结构系列【数据库喜欢的数据结构：B-树、B+树原理、应用、以及java实现示例】-CSDN博客
科普文：算法和数据结构系列【B+树java示例代码解读】-CSDN博客
常见树形结构梳理的七七八八了，我们再看看哈夫曼树（Huffman Tree），是一种高效的二叉树，用于实现最优的无歧义前缀编码，在数据压缩、网络通信、信息编码等领域有着很重要的应用。
哈夫曼树（Huffman Tree）
哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度最短的二叉树。
它通过一种贪心算法构造而成，目的是使得树的带权路径长度（WPL）最小，即所有叶子节点的权值乘以它们到根节点的路径长度之和最小。
它由美国计算机科学家大卫·哈夫曼（David Huffman）于1953年提出，主要用于数据压缩和编码。
工作原理
哈夫曼树的构建过程如下：
1. 统计频率：统计所有字符出现的频率。
2. 初始化节点：将每个待编码的元素作为单独的叶子节点，每个节点的权值代表该元素的频率。
3. 构建树：重复选择两个权值最小的节点合并成一个新的内部节点，这个新节点的权值是两个子节点权值之和。这个过程直到只剩下一个节点，即为树的根节点。
- 从森林中选择两个权重最小的节点，构造一个新的二叉树，新树的根节点权重为这两个节点权重之和。
- 将新树加入森林，删除原来的两个节点。
- 重复上述步骤，直到森林中只剩下一棵树，这棵树就是哈夫曼树。
4. 编码生成：从根到每个叶子节点的路径可以定义为一个编码，左分支代表0，右分支代表1，这样每个叶子节点就有了一个唯一的二进制编码。
时间复杂度与空间复杂度
- 时间复杂度：O(n log n)，其中n是叶子节点的数量。这是因为构建过程中涉及了多次最小值的选取和合并操作，最坏情况下接近于排序的时间复杂度。
- 空间复杂度：O(n)，主要消耗在于存储树的结构，包括每个节点和它们的权值、子节点指针。
哈夫曼树的时间复杂度：
哈夫曼树的构建时间复杂度主要取决于优先队列（最小堆）的操作。一般情况下，使用二叉堆实现的优先队列，其插入和删除操作的时间复杂度均为O(log n)，因此构建哈夫曼树的时间复杂度为O(n log n)，其中n为字符的数量。
哈夫曼树的空间复杂度：
哈夫曼树的空间复杂度主要取决于节点的存储。在最坏情况下，即所有字符的频率都相同，哈夫曼树将退化为一颗满二叉树，此时空间复杂度为O(n)，其中n为字符的数量。一般情况下，空间复杂度也接近于O(n)。
优缺点和应用场景
优点：
- 高效编码：能够为频繁出现的元素分配较短的编码，减少数据存储和传输的大小。
- 无歧义性：哈夫曼编码保证了编码的唯一性，没有前缀相同的编码，适合数据压缩。
- 最优性：通过贪心算法构造，保证了编码的最优性。
- 前缀无歧义性：编码中没有任何一个符号的编码是其他符号编码的前缀。
- 自适应性：基于字符出现的频率动态生成树，更适合频率分布不均的数据。
缺点：
- 构建过程需要时间：虽然不是非常耗时，但对于大规模数据集，构建过程可能相对慢。
- 编码依赖于频率：如果数据的频率分布发生变化，需要重新构建哈夫曼树，编码也会改变。
- 构建哈夫曼树需要一定的计算成本，特别是在字符集很大或频率分布变化频繁时。
- 哈夫曼树对频率非常敏感，频率的微小变化可能导致树结构的显著变化。
应用场景：
哈夫曼树广泛应用于数据压缩领域，如文件压缩、图像压缩、通信中的数据传输等。通过对数据频率的分析，生成更短的编码以减少存储和传输成本。
- 数据压缩：如文件压缩中的Huffman编码。
- 网络通信：优化传输数据的编码，减少带宽使用。
- 信息编码：在数据库索引、文件系统等领域优化存储结构。
哈夫曼树的注意事项
- 动态变化的频率：如果数据的频率频繁变化，维护哈夫曼树的成本会增加。
- 编码的生成：编码应确保所有叶子节点的路径不相同，避免解码时的混淆。
- 平衡性：虽然哈夫曼树不是严格平衡的，但它自然地趋向于平衡，有助于提高查找效率。
- 编码效率：在设计编码时，应确保编码规则的高效实现，避免编码过长导致的解析效率下降。
- 在构建哈夫曼树时，需要确保输入的字符及其频率是准确的，因为这将直接影响编码的效率和效果。
- 哈夫曼树对频率非常敏感，因此在处理频率分布变化较大的数据时，可能需要重新构建树以适应新的频率分布。
- 在实际应用中，还需要考虑哈夫曼树的构建和编码解码过程的计算成本，以及与其他压缩算法的比较和选择。
哈夫曼树（Huffman Tree）java示例代码解读
如上测试用例
char[] chars = {'A', 'B', 'C', 'D', 'E', 'F'};
int[] freq = {5, 9, 12, 13, 16, 45};
表示如下：
- A: 5次
- B: 9次
- C: 12次
- D: 13次
- E: 16次
- F: 45次
接下来，我们按照哈夫曼树的构建步骤来操作：
-
初始化优先队列：将字符及其频率作为节点加入优先队列（最小堆）：(A,5), (B,9), (C,12), (D,13), (E,16), (F,45)。
-
构建哈夫曼树：
- 取出频率最小的两个节点 A 和 B，合并为新节点（频率 14），放回队列。
- 取出频率最小的两个节点 C 和 D，合并为新节点（频率 25），放回队列。
- 取出频率最小的两个节点（新节点 14 和 E16），合并为新节点（频率 30），放回队列。
- 取出频率最小的两个节点（新节点 25 和新节点 30），合并为新节点（频率 55）。
- 最后取出频率最小的两个节点（新节点 55和 F45），合并成根节点（频率 100）。
- 代码打印结果与之一致：[100] F(45) [55] [25] [30] C(12) D(13) [14] E(16) A(5) B(9)
-
生成哈夫曼编码：从根节点开始，为每条到叶子节点的路径生成编码。
- 字符 'F' 的频率最高，因此它很可能是第一个被单独分配编码的节点（在最顶层），并且得到了最短的编码 '0'。
- 字符 'A' 到 'E' 的频率较低，它们会被分配到更深的层次，因此编码会更长。
- 编码中的每一位都表示了从根节点到叶子节点（代表字符）的路径上的选择：'0' 表示走左子树，'1' 表示走右子树。
- 代码打印的哈夫曼编码：Huffman Codes are: {A=1100, B=1101, C=100, D=101, E=111, F=0}
-
验证编码：确保每个字符的编码都是唯一的，并且没有一个是其他编码的前缀。验证编码的总长度是否最小化（这是哈夫曼树的一个关键性质）。
大概了解哈夫曼树生成过程，我们再来看看代码
节点定义：HuffmanNode 类
这个类代表哈夫曼树中的一个节点，它包含频率 freq、字符 c（仅对叶子节点有意义），以及左右子节点的引用 left 和 right。构造函数用于初始化这些属性。
//HuffmanNode类：定义哈夫曼树的节点，包含字符数据c、权重data、左子节点left和右子节点right。
class HuffmanNode {
int freq;// 频率
char c; // 字符（仅对叶子节点有效）
HuffmanNode left;
HuffmanNode right;
HuffmanNode(int freq, char c) {
this.freq = freq;
this.c = c;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder("{");
stringBuilder.append("c=").append(c).append(",");
stringBuilder.append("freq=").append(freq).append(",");
stringBuilder.append("left=").append(left == null ? "" : left).append(",");
stringBuilder.append("leftNode=").append(right == null ? "" : right).append(",");
stringBuilder.append("}");
return stringBuilder.toString();
//return value.toString();
}
}树定义：HuffmanTree类
public class HuffmanTree {
// 构建哈夫曼树：根据字符及其频率构建哈夫曼树。使用优先队列（最小堆）来选择权重最小的两个节点进行合并，直到队列中只剩下一个节点，即哈夫曼树的根节点。
public static HuffmanNode buildHuffmanTree(char[] data, int[] freq, int size) {
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(size, Comparator.comparingInt(a -> a.freq));
for (int i = 0; i < size; i++) {
pq.add(new HuffmanNode(freq[i], data[i]));
}
HuffmanNode root = null;
while (pq.size() > 1) {
HuffmanNode left = pq.poll();
HuffmanNode right = pq.poll();
HuffmanNode newNode = new HuffmanNode(left.freq + right.freq, '\0');
newNode.left = left;
newNode.right = right;
pq.add(newNode);
}
root = pq.peek();
return root;
}
// 生成哈夫曼编码：递归地生成每个字符的哈夫曼编码。左子树路径为"0"，右子树路径为"1"。
public static void generateCodes(HuffmanNode root, String code, Map<Character, String> huffmanCode) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
huffmanCode.put(root.c, code);
}
generateCodes(root.left, code + "0", huffmanCode);
generateCodes(root.right, code + "1", huffmanCode);
}
// 解码：根据哈夫曼树解码编码字符串。从根节点开始，根据编码的每一位选择左子节点或右子节点，直到到达叶子节点，然后输出对应的字符并回到根节点。
public static String decode(HuffmanNode root, String encodedStr) {
StringBuilder decodedStr = new StringBuilder();
HuffmanNode current = root;
for (char bit : encodedStr.toCharArray()) {
if (bit == '0') {
current = current.left;
} else {
current = current.right;
}
if (current.left == null && current.right == null) {
decodedStr.append(current.c);
current = root;
}
}
return decodedStr.toString();
}
// 层次遍历打印哈夫曼树
public void levelOrderTraversal(HuffmanNode root) {
if (root == null) {
return;
}
Queue<HuffmanNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点加入队列
while (!queue.isEmpty()) {
HuffmanNode node = queue.poll(); // 从队列中取出节点
// 打印节点信息（对于内部节点，可以只打印频率）
if (node.c != '\0') { // 假设'\0'表示非叶子节点的字符
System.out.print(node.c + "(" + node.freq + ") ");
} else {
System.out.print("[" + node.freq + "] ");
}
//System.out.println("[" + node + "] ");
// 将子节点加入队列
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
public static void main(String[] args) {
char[] chars = {'A', 'B', 'C', 'D', 'E', 'F'};
int[] freq = {5, 9, 12, 13, 16, 45};
int size = chars.length;
HuffmanNode root = buildHuffmanTree(chars, freq, size);
Map<Character, String> huffmanCode = new HashMap<>();
generateCodes(root, "", huffmanCode);
System.out.println("Huffman Codes are: " + huffmanCode);
new HuffmanTree().levelOrderTraversal(root); // 层次遍历打印哈夫曼树
String encodedStr = "11010110111011011110110111101111";
String decodedStr = decode(root, encodedStr);
System.out.println("Encoded string is: " + encodedStr);
System.out.println("Decoded string is: " + decodedStr);
}
}构建哈夫曼树 (buildHuffmanTree)
构建哈夫曼树：根据字符及其频率构建哈夫曼树。使用优先队列（最小堆）来选择权重最小的两个节点进行合并，直到队列中只剩下一个节点，即哈夫曼树的根节点。
-
优先队列：使用
PriorityQueue来存储哈夫曼树的节点，并根据节点的频率进行排序。这是一个最小堆，因此频率最小的节点会首先被移除。 -
初始化：遍历
data和freq数组，为每个字符和对应的频率创建一个HuffmanNode，并将其添加到优先队列中。 -
构建树：当优先队列中的节点数大于1时，不断从队列中移除两个频率最小的节点，将它们合并为一个新的节点（其频率为两个节点频率之和，字符设为
'\0'表示非叶子节点），然后将新节点添加回队列中。 -
返回根节点：最后，当队列中只剩下一个节点时，这个节点就是哈夫曼树的根节点，将其返回。
生成哈夫曼编码 (generateCodes)
-
递归遍历：方法使用递归遍历哈夫曼树。对于每个节点，如果它是叶子节点（即没有左右子节点），则将其字符和对应的编码添加到
huffmanCode映射中。 -
编码生成：对于左子节点，编码追加
"0"；对于右子节点，编码追加"1"。这样，从根节点到叶子节点的路径就形成了该字符的哈夫曼编码。
哈夫曼编码解码(decode )
这个方法遍历编码字符串中的每一位（'0' 或 '1'），根据这一位是 '0' 还是 '1'，在哈夫曼树中向左或向右移动，直到到达一个叶子节点。当到达叶子节点时，它将节点对应的字符添加到解码后的字符串中，并将当前节点重置为根节点，以便继续解码下一个字符。
-
初始化：创建一个
StringBuilder对象decodedStr用于构建解码后的字符串，并将当前节点current初始化为哈夫曼树的根节点。 -
遍历编码字符串：使用增强的
for循环遍历编码字符串encodedStr的每一个字符（这里假设编码只包含 '0' 和 '1'）。 -
移动节点：根据当前字符是 '0' 还是 '1'，将当前节点
current移动到其左子节点或右子节点。 -
检查叶子节点：如果当前节点没有左右子节点（即它是叶子节点），则将节点对应的字符添加到
decodedStr中，并将当前节点重置为根节点，以便从根节点开始解码下一个字符。 -
返回结果：遍历完成后，返回
decodedStr的字符串表示形式，即解码后的字符串。
层次遍历：层次遍历打印哈夫曼树levelOrderTraversal
levelOrderTraversal 方法实现了哈夫曼树的层序遍历（也称为广度优先遍历）。这个方法使用一个队列来按层次访问树中的每个节点，从根节点开始，然后依次访问每一层的节点。对于每个访问的节点，它会打印出节点的信息；对于叶子节点，打印字符和频率，对于内部节点（非叶子节点），只打印频率。
-
检查根节点：首先检查根节点是否为空。如果为空，则直接返回，不进行任何操作。
-
初始化队列：创建一个
Queue<HuffmanNode>类型的队列，并将根节点加入队列。这里使用了LinkedList作为队列的实现。 -
层序遍历：使用一个
while循环来遍历队列，直到队列为空。在每次循环中，从队列中取出一个节点，并打印该节点的信息。 -
打印节点信息：根据节点是叶子节点还是内部节点，打印不同的信息。这里假设内部节点的字符被设置为
'\0'，因此可以通过检查字符是否等于'\0'来区分叶子节点和内部节点。 -
加入子节点：如果当前节点有左子节点或右子节点，则将它们加入队列中，以便在后续的循环中访问。