哈夫曼树的简单介绍

（数据结构 树的补充知识）

哈夫曼树的内容概述

哈夫曼树的定义

哈夫曼树其实的一个比较简单的知识点。那么哈夫曼树的树我们就应该知道这是一个树的结构，衍生出来的知识点。

哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，也称为最优二叉树。由美国计算机科学家David A. Huffman于1952年提出，主要用于数据压缩领域。其核心思想是通过赋予高频字符较短的编码、低频字符较长的编码，从而减少整体编码长度。

哈夫曼树的构建步骤

哈夫曼树的的构建其实用到了一种算法叫：贪心算法，每一次取数组里面最小的数值来构建二叉树，自下而上的构建二叉树，一步一步的构建，直到数组的内容都用完。

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（局部最优）的决策，从而希望导致全局最优解的算法策略。贪心算法通常用于解决最优化问题，例如最短路径、最小生成树、任务调度等。

1. 初始化节点集合
   将每个字符及其出现频率（权重）作为独立的叶子节点，构成一个森林。

2. 合并权重最小的节点
   每次从森林中选出两个权重最小的节点，合并为一个新节点，新节点的权重为两者之和，其左右子树分别为这两个节点。

3. 重复合并过程
   将新节点加入森林，重复上述合并步骤，直到森林中只剩一棵树，即哈夫曼树。

哈夫曼树的性质

• 带权路径长度最小：所有叶子节点的权重乘以其到根节点的路径长度之和最小。
• 前缀码特性：任何字符的编码都不是其他字符编码的前缀，避免解码歧义。
• 二叉树结构：只有度为0或2的节点，不存在度为1的节点。

哈夫曼编码的应用

• 数据压缩：如ZIP、JPEG、MP3等格式的压缩算法。
• 文件加密：通过动态编码提高安全性。
• 网络传输：减少传输数据量。

示例

图1 哈夫曼树的例题思路

图2 网上的哈夫曼树例题

解题过程：

所有元素 2、4、7、14、9、12、23。

从大到小或者从小到大排列:2、4、7、9、12、14、23

取最小两个：2、4 组成6

先数组最小：6、7、9、12、14、23

取最小两个：6、7 组成13

9、12、13、14、23

取最小两个：9、12组成21

……（以此类推）

最终构建哈夫曼树。

哈夫曼编码

学习了二叉树，有些人会想我们要确定一个二叉树中的某一个节点的位置，不可能只是通过前中后遍历或者层序遍历来确定一个树的位置，这就没办法统一 一定比较明确的位置，我们在整体观察二叉树的，每一个节点只有两个向下的节点，我们联想到这种其实就类似二进制代码一样，通过0表示下左节点，1表示下右节点，而这种就是二叉树编码，如果是在哈夫曼树中就叫哈夫曼编码。

哈夫曼树的特点： 权值越大的结点越靠近根；使用概率越大的字符编码越短， 使用概率越小的字符编码越长。

感谢观看！

悠仁さん