408数据结构考点：哈夫曼树和哈夫曼编码 前置知识 优先队列 优先队列(priority queue)：也称优先级队列，相比普通队列，每个素增加了属性优先级，优先级高的素排在前面，优先级低的素排在后面。 最大优先队列(max-priority queue)：素的值越大，素的优先级越高。 最小优先队列(min-priority queue)：素的值越小，素的优先级越高。 优先队列的出队操作和普通队列的出队操作一样，队头素，即当前队列中优先级最高的素，直接从队列中移除。 给定一个最小优先队列，从队头到队尾为 1, 3, 5, 7, 9。执行出队操作，1出队，变为 3, 5, 7, 9。 优先队列的出队操作和普通队列的出队操作有区别，该素入队后可以进行插队，插入到所有优先级比该素低的素之前。 给定一个最小优先队列，从队头到队尾为 3, 5, 7, 9。插入素 6，执行入队操作，变为 3, 5, 6, 7, 9。 优先队列有很多实现方式，最简单的就是使用二叉堆。相比排序，使用优先队列大大降低了时间复杂度。 构造哈夫曼树需要用到最小优先队列。 操作系统中的优先级调度算法也使用了优先队列这一数据结构。 哈夫曼树 结点的带权路径长度：从一个结点到树的根节点之间的路径长度与该结点权值的乘积。 树的带权路径长度：一棵树中所有叶结点的带权路径长度之和，记作
，其中叶结点编号为 ，叶结点 的权值为 ，路径长度为 。 最优二叉树：假设有 个权值 ，试构造一个有 个叶结点的二叉树，叶结点 的权值为 ，带权路径长度最小的二叉树为最优二叉树，也称哈夫曼树(Huffman tree)。 假设字符集 包含 个字符，每个字符 的频率为 ，采用自底向上方法构造哈夫曼树，该算法使用了最小优先队列 。HUFFMAN 伪代码如下： 每次迭代将优先队列中权值最小的两个结点出队，构造一个新结点，将出队的两个结点作为该新结点的两个孩子结点。然后将新结点入队。重复迭代操作，直到优先队列中只有一个结点。 哈夫曼编码 前缀编码(prefix codes)：也称前缀无关编码(prefix-free codes)，任何一个码字都不是其它码字的前缀的编码。 哈夫曼编码(Huffman code)：构造一个带权字符集的哈夫曼树，每个左分支标记字符 0，每个右分支标记字符 1，则从根结点到叶结点的路径上所有分支字符组成的字符串为该结点的哈夫曼编码。哈夫曼编码是一种最优前缀编码。 真题考点 哈夫曼树的性质 哈夫曼树每个结点的度只能为 0 或 2。每个非叶结点的权值等于其两个孩子结点的权值之和。哈夫曼树是最优二叉树。 哈夫曼编码的性质 哈夫曼编码是一种最优前缀编码。 构造哈夫曼树和哈夫曼编码 例题 已知某系统在通信联络中只可能出现 6 种字符，字符和频率分别为：a : 45, b : 13, c : 12, d : 16, e : 9, f : 5，求出每个字符的哈夫曼编码。 解答：
可得编码 a : 0, b : 101, c : 100, d : 111, e : 1101, f : 1100。 历年真题 2010年第6题 考察哈夫曼树的性质。 2012年第41题 考察哈夫曼树的构造。 2014年第6题 考察前缀编码的定义。 2015年第3题 考察哈夫曼树的性质。 2018年第5题 考察哈夫曼编码的性质。 2019年第3题 考察哈夫曼树的性质。 2021年第5题 考察哈夫曼树的构造。 2022年第5题 考察哈夫曼树的性质。 2023年第4题 考察哈夫曼树的构造。 解析详见 千葉原：408历年真题解析数据结构篇 哈夫曼树和哈夫曼编码在历年真题中几乎每年一考。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/73086.html
