最新华为OD机试真题-生成哈夫曼树(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🍪 生成哈夫曼树
问题描述
LYA 是一名计算机专业的学生,最近她学习了哈夫曼编码。为了巩固知识,她决定写一个程序来生成哈夫曼树。
给定一个长度为 的正整数数组,每个数字代表二叉树叶子节点的权值。请你帮助 LYA 生成一棵哈夫曼树,并将其按中序遍历的顺序输出。
为了保证输出的哈夫曼树唯一,需要满足以下条件:
-
树中每个非叶子节点的权值等于其左右子节点权值之和。
-
对于权值相同的两个节点,左子树的高度应小于等于右子树的高度。
-
在满足上述条件的前提下,左子节点的权值应小于等于右子节点的权值。
输入格式
第一行包含一个正整数 ,表示叶子节点的个数。
第二行包含 个正整数,表示每个叶子节点的权值,数值之间用空格分隔。
输出格式
输出一行,包含若干个正整数,表示按中序遍历哈夫曼树得到的节点权值序列,数值之间用空格分隔。
样例输入
5
5 15 40 30 10
样例输出
40 100 30 60 15 30 5 15 10
数据范围
权值
题解
本题考查哈夫曼树的构建。哈夫曼树是一种带权最优二叉树,其特点是带权路径长度最短。
构建哈夫曼树的基本步骤如下:
-
将所有节点看成独立的树,并按照权值从小到大排序。
-
取出权值最小的两棵树,将它们作为一个新树的左右子树,新树的权值为两棵子树权值之和。
-
重复步骤 2,直到只剩下一棵树,即为所求的哈夫曼树。
在实现时,我们可以用优先队列来维护节点,每次取出权值最小的两个节点合并。为了保证输出的哈夫曼树唯一,在优先队列中比较两个节点时,先比较权值,权值相同再比较树高,树高也相同则比较左右子树的权值大小关系。
构建完哈夫曼树后,我们再进行一次中序遍历即可得到输出序列。
参考代码
- Python
import heapq
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __lt__(self, other):
if self.val != other.val:
return self.val < other.val
if self.height != other.height:
return self.height < other.height
return self.left.val <= other.left.val
@property
def height(self):
return max(self.left.height if self.left else 0,
self.right.height if self.right else 0) + 1
def huffman_tree(vals):
pq = [Node(val) for val in vals]
heapq.heapify(pq)
while len(pq) > 1:
left, right = heapq.heappop(pq), heapq.heappop(pq)
heapq.heappush(pq, Node(left.val + right.val, left, right))
return pq[0]
def inorder_traversal(root):
if not root:
return []
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
n = int(input())
vals = list(map(int, input().split()))
root = huffman_tree(vals)
print(*inorder_traversal(root))
- Java
import java.io.*;
import java.util.*;
class Node implements Comparable<Node> {
int val;
Node left, right;
Node(int val) {
this.val = val;
}
Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
int height() {
return 1 + Math.max(left != null ? left.height() : 0,
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测