最新华为OD机试真题-生成哈夫曼树(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 生成哈夫曼树(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🍪 生成哈夫曼树

问题描述

LYA 是一名计算机专业的学生,最近她学习了哈夫曼编码。为了巩固知识,她决定写一个程序来生成哈夫曼树。

给定一个长度为 的正整数数组,每个数字代表二叉树叶子节点的权值。请你帮助 LYA 生成一棵哈夫曼树,并将其按中序遍历的顺序输出。

为了保证输出的哈夫曼树唯一,需要满足以下条件:

1. 树中每个非叶子节点的权值等于其左右子节点权值之和。

2. 对于权值相同的两个节点,左子树的高度应小于等于右子树的高度。

3. 在满足上述条件的前提下,左子节点的权值应小于等于右子节点的权值。

输入格式

第一行包含一个正整数 ,表示叶子节点的个数。

第二行包含 个正整数,表示每个叶子节点的权值,数值之间用空格分隔。

输出格式

输出一行,包含若干个正整数,表示按中序遍历哈夫曼树得到的节点权值序列,数值之间用空格分隔。

样例输入

5
5 15 40 30 10

样例输出

40 100 30 60 15 30 5 15 10

数据范围

权值

题解

本题考查哈夫曼树的构建。哈夫曼树是一种带权最优二叉树,其特点是带权路径长度最短。

构建哈夫曼树的基本步骤如下:

1. 将所有节点看成独立的树,并按照权值从小到大排序。

2. 取出权值最小的两棵树,将它们作为一个新树的左右子树,新树的权值为两棵子树权值之和。

3. 重复步骤 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,