生成哈夫曼树 - 华为OD统一考试(C卷)
OD统一考试(C卷)
分值: 100分
题解: Java / Python / C++
题目描述
给定长度为 n
的无序的数字数组,每个数字代表二叉树的叶子节点的权值,数字数组的值均大于等于 1 。
请完成一个函数,根据输入的数字数组,生成哈夫曼树,并将哈夫曼树按照中序遍历输出。
为了保证输出的二叉树中序遍历结果统一,增加以下限制:
- 在树节点中,左节点权值小于等于右节点权值,根节点权值为左右节点权值之和。
- 当左右节点权值相同时,左子树高度高度小于等于右子树。
注意: 所有用例保证有效,并能生成哈夫曼树提醒:哈夫曼树又称最优二叉树,是一种带权路径长度最短的一叉树。
所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为 0 层,叶结点到根结点的路径长度为叶结点的层数)
输入描述
例如:由叶子节点 5 15 40 30 10 生成的最优二叉树如下图所示,该树的最短带权路径长度为 40∗1+30∗2+15∗3+5∗4+10∗4=205。
输出描述
输出一个哈夫曼的中序遍历数组,数值间以空格分隔
示例1
输入:
5
5 15 40 30 10
输出:
40 100 30 60 15 30 5 15 10
说明:
根据输入,生成哈夫曼树,按照中序遍历返回。所有节点中,左节点权值小于等于右节点权值之和。当左右节点权值相同时左子树高度小于右子树。结果如上图
题解
这是一个构建哈夫曼树并进行中序遍历的问题。下面是对解题思路和代码的一些解释:
- 定义了一个
Node
类(C++中是结构体),表示哈夫曼树的节点。其中,weight
表示权值,height
表示树的高度,left
和right
分别表示左子树和右子树。- 重载了
Node
的比较运算符,以便在优先队列(小顶堆)中按照规定的比较规则进行排序。比较规则是先按照权值升序排列,如果权值相同,则按照树高度升序排列。- 使用优先队列(小顶堆)来存储节点,确保每次取出的节点都是权值最小的节点。
- 通过输入构建节点,将节点加入优先队列。
- 使用优先队列构建哈夫曼树,每次取出两个最小的节点,合并为一个新节点,再放回队列,直到队列中只剩一个节点为止。
- 最终得到哈夫曼树的根节点,通过中序遍历输出结果。
对于时间复杂度和空间复杂度:
时间复杂度:构建哈夫曼树的过程中,每次取出两个最小节点,因此时间复杂度为 O(n log n),其中 n 为节点的个数。
空间复杂度:使用了优先队列来存储节点,空间复杂度为 O(n)。
哈夫曼树(Huffman Tree)是一种用于编码的二叉树,其中每个叶子节点表示一个字符,而每个内部节点包含一个权值,表示字符出现的频次。哈夫曼树的构建目标是最小化编码长度,使得出现频次较高的字符拥有较短的编码。
构建哈夫曼树的步骤如下:
- 给定一组字符及其频次,将每个字符视为一个权值为其频次的单节点树。
- 从这些单节点树中选择两个具有最小权值的树,合并成一个新的树,新树的权值为两个原树的权值之和。这一步骤称为构建哈夫曼树的一次合并操作。
- 重复步骤2,直到只剩下一个树,即哈夫曼树。
在构建的过程中,为了确保编码长度最短,频次越高的字符在树中的深度越浅。
哈夫曼树主要用于数据压缩,其中对字符进行编码时,频次高的字符用较短的二进制编码表示,频次低的字符用较长的编码表示,从而实现对数据的高效压缩。
Java
import java.util.PriorityQueue;
import java.util.Scanner;
class Node implements Comparable<Node> {
long weight; // 权值
int height; // 树高度
Node left, right; // 左右子树
public Node() {
this.height = 1;
this.left = null;
this.right = null;
}
// 重载小于运算符,用于定义小顶堆中的比较规则
@Override
public int compareTo(Node other) {
if (this.weight != other.weight) {
return Long.compare(this.weight, other.weight); // 小顶堆,按照权值升序排列
} else {
return Integer.compare(this.height, other.height); // 权值相同,则树高度升序排序
}
}
}
/**
* @author code5bug
*/
public class Main {
// 中序遍历
static void inorder(Node node) {
if (node == null) return;
inorder(node.left);
System.out.print(node.weight + " ");
inorder(node.right);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答