最新华为OD机试真题-生成哈夫曼树(100分)
大家好这里是清隆学长 ，一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
感谢大家的订阅➕ 和 喜欢
在线评测链接
=> 生成哈夫曼树(100分) <=
评测功能需要 =>订阅专栏<= 后联系清隆解锁～
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,
right != null ? right.height() : 0);
}
@Override
public int compareTo(Node other) {
if (val != other.val) {
return Integer.compare(val, other.val);
}
if (height() != other.height()) {
return Integer.compare(height(), other.height());
}
return Integer.compare(left.val, other.left.val);
}
}
public class Main {
public static Node huffmanTree(int[] vals) {
PriorityQueue<Node> pq = new PriorityQueue<>();
for (int val : vals) {
pq.offer(new Node(val));
}
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
pq.offer(new Node(left.val + right.val, left, right));
}
return pq.poll();
}
public static List<Integer> inorderTraversal(Node root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
res.addAll(inorderTraversal(root.left));
res.add(root.val);
res.addAll(inorderTraversal(root.right));
return res;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] vals = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
Node root = huffmanTree(vals);
List<Integer> res = inorderTraversal(root);
System.out.println(String.join(" ", res.stream()
.map(String::valueOf)
.toArray(String[]::new)));
}
}
- Cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int val;
Node *left, *right;
Node(int v) : val(v), left(nullptr), right(nullptr) {}
Node(int v, Node *l, Node *r) : val(v), left(l), right(r) {}
int height() const {
return 1 + max(left ? left->height() : 0, right ? right->height() : 0);
}
bool operator<(const Node &other) const {
if (val != other.val) {
return val > other.val;
}
if (height() != other.height()) {
return height() > other.height();
}
return left->val > other.left->val;
}
};
Node* huffmanTree(const vector<int>& vals) {
priority_queue<Node*> pq;
for (int val : vals) {
pq.push(new Node(val));
}
while (pq.size() > 1) {
Node *left = pq.top(); pq.pop();
Node *right = pq.top(); pq.pop();
pq.push(new Node(left->val + right->val, left, right));
}
return pq.top();
}
void inorderTraversal(const Node *root, vector<int>& res) {
if (!root) {
return;
}
inorderTraversal(root->left, res);
res.push_back(root->val);
inorderTraversal(root->right, res);
}
int main() {
int n;
cin >> n;
vector<int> vals(n);
for (int i = 0; i < n; ++i) {
cin >> vals[i];
}
Node *root = huffmanTree(vals);
vector<int> res;
inorderTraversal(root, res);
for (int i = 0; i < res.size(); ++i) {
cout << res[i] << (i == res.size() - 1 ? "\n" : " ");
}
return 0;
}
类似资料：